fork download

copy

// Calculate Nth Fibbionacci number in O(log N)
object Milk{
	// Matrix multiplication
	def matmul(mat1 : Array[ Array [Int] ], mat2 : Array[ Array [Int] ]): Array[ Array [Int] ] = {
		val n = mat.size;
		var res : Array[ Array [Int](n) ](n);
		for(i <- 0 until n){
			for(j <- 0 until n){
				res(i)(j) = 0;
				for(k <- k until n){
					res(i)(j) += mat1(i)(k) * mat2(k)(j);
				}
			}
		}
		return res;
	}
	// Matrix powering
	def matpow(mat : Array[ Array [Int] ], pow : Int): Array[ Array [Int] ] = {
		val n = mat.size;
		var res : Array[ Array [Int](n) ](n);
		for(i <- 0 until n){
			for(j <- 0 until n){
				if(i == j) res(i)(j) = 1;
				else res(i)(j) = 0;
			}
		}
		while(pow > 0){
			if(pow % 2){
				res = matmul(res, mat);
			}
			mat = matmul(mat, mat);
		}
		return res;
	}
	// Calculate sum of a
	def fibb(n) : Int = {
		var mat Array[ Array [Int](2) ](2);
		mat(0)(0) = 1; mat(0)(1) = 1; mat(1)(0) = 1; mat(1)(1) = 0;
		mat = matpow(mat, n);
		return mat(1)(0);
	}
	// Main function
	def main(args : Array[ String ]) = {
		val n = args.size;
		for( i <- 0 until n) a(i) = println(fibb(args(i).toInt));
	}
}
 

Main.scala:6: error: ']' expected but '(' found.
		var res : Array[ Array [Int](n) ](n);
                                            ^
Main.scala:6: error: ';' expected but '(' found.
		var res : Array[ Array [Int](n) ](n);
                                                 ^
Main.scala:20: error: ']' expected but '(' found.
		var res : Array[ Array [Int](n) ](n);
                                            ^
Main.scala:20: error: ';' expected but '(' found.
		var res : Array[ Array [Int](n) ](n);
                                                 ^
Main.scala:36: error: ':' expected but ')' found.
	def fibb(n) : Int = {
                  ^
Main.scala:47: error: identifier expected but '}' found.
}
^
6 errors found

Standard output is empty