Find Fibonacci Numbers Using Matrix Multiplication

FibonacciMatrix.scala

// 行列累乗を使ってフィボナッチ数列を求めてみる
// 参考
// http://blog.scala4java.com/2011/12/matrix-multiplication-in-scala-single.html

import annotation.tailrec
import scala.util.control.Exception._

object FibonacciMatrix {
  type Matrix = Array[Array[BigInt]]
  def mul(m1: Matrix, m2: Matrix) = {
    val res = Array.fill(m1.length, m2(0).length)(BigInt(0))
    for (row <- (0 until m1.length).par;
         col <- (0 until m2(0).length).par;
         i <- 0 until m1(0).length) {
      res(row)(col) += m1(row)(i) * m2(i)(col)
    }
    res
  }
  def pow(a : Matrix, n : Int) = {
    @tailrec
    def powLocal(a: Matrix, b: Matrix, n: Int): Matrix = n match {
      case 0 => b
      case x if (x & 1) == 1 => powLocal(mul(a, a), mul(a, b), x >> 1)
      case x => powLocal(mul(a, a), b, x >> 1)
    }
    val unit = Array(Array(BigInt(1), BigInt(0)), Array(BigInt(0), BigInt(1)))  // 単位行列
    if (n < 0) throw new IllegalArgumentException
    powLocal(a, unit, n)
  }
  def fibo(n: Int) = {
    val m = Array(Array(BigInt(1), BigInt(1)), Array(BigInt(1), BigInt(0)))
    pow(m, n)(1)(0)
  }
  def main(args: Array[String]) {
    allCatch.either{ args(0).toInt } match {
      case Left(e) => println(e.printStackTrace())
      case Right(n) => (1 to n).foreach{ i => println(i + ": " + fibo(i)) }
    }
// 時間計測用
//    val start = System.currentTimeMillis()
//    println(100000 + ": " + fibo(100000))
//    println((System.currentTimeMillis() - start) + " msec")
  }
}