O(log(N)) な フィボナッチ数の計算方法ベンチマーク

fibimpl.scala

object FibImpModule {
  /** リファレンス実装 */
  val fibRef: Stream[BigInt] = 
    BigInt(0) #:: fibRef.scanLeft(BigInt(1)){_ + _}
  
  /** 逐次平方変換系の実装 */
  // Generic な実装 (しかし、JVMの型消去のため、実力よりずいぶん遅くなったため
  // 公正なベンチマークにならないのでボツ。。。)
  def fibSqr[IntT](n: Int)(implicit num: Integral[IntT]): IntT = {
    import num._
    @scala.annotation.tailrec // 末尾再帰最適化を保証するためのアノーテーション
    def rec(a: IntT, b: IntT, p: IntT, q: IntT, count: Int): IntT = {
      if (count == 0) b
      else (count % 2) match {
        case 0 => rec(a, b, p*p+q*q, num.fromInt(2)*p*q+q*q, count / 2)
        case 1 => rec(b*q+a*q+a*p, b*p+a*q, p, q, count - 1)
      }
    }
    rec(one, one, zero, one, n)
  }
  
  // Int 専用
  def fibSqrInt(n: Int): Int = {
    @scala.annotation.tailrec // 末尾再帰最適化を保証するためのアノーテーション
    def rec(a: Int, b: Int, p: Int, q: Int, count: Int): Int = {
      if (count == 0) b
      else (count % 2) match {
        case 0 => rec(a, b, p*p+q*q, 2*p*q+q*q, count / 2)
        case 1 => rec(b*q+a*q+a*p, b*p+a*q, p, q, count - 1)
      }
    }
    rec(1, 1, 0, 1, n)
  }
  
  // Long 専用
  def fibSqrLong(n: Int): Long = {
    @scala.annotation.tailrec // 末尾再帰最適化を保証するためのアノーテーション
    def rec(a: Long, b: Long, p: Long, q: Long, count: Long): Long = {
      if (count == 0) b
      else (count % 2) match {
        case 0 => rec(a, b, p*p+q*q, 2*p*q+q*q, count / 2)
        case 1 => rec(b*q+a*q+a*p, b*p+a*q, p, q, count - 1)
      }
    }
    rec(1, 1, 0, 1, n)
  }
  
  // BigInt 専用
  def fibSqrBigInt(n: Int): BigInt = {
    @scala.annotation.tailrec // 末尾再帰最適化を保証するためのアノーテーション
    def rec(a: BigInt, b: BigInt, p: BigInt, q: BigInt, count: Int): BigInt = {
      if (count == 0) b
      else (count % 2) match {
        case 0 => rec(a, b, p*p+q*q, p*q*2+q*q, count / 2)
        case 1 => rec(b*q+a*q+a*p, b*p+a*q, p, q, count - 1)
      }
    }
    rec(1, 1, 0, 1, n)
  }
  
  /** 対角要素冪の実装 */
  // pow を使った
  def fibDigDoublePow(n: Int): Long = 
    math.round(0.4472135954999579 * math.pow(1.618033988749895, n))
  // exp を使った
  def fibDigDoubleExp(n: Int): Long = 
    (0.4472135954999579 * math.exp(0.48121182505960347 * n) + 0.5).asInstanceOf[Long]
  
  /** LF 系 */
  // Luca number & Fibonacci number
  // http://en.wikipedia.org/wiki/Lucas_number
  def fibLucaInt(n: Int): Int =  {
    @annotation.tailrec
    def rec(l: Int, f: Int, bitmask: Int): Int =
      if (bitmask == 0) f
      else {
        val ll = (l * l + 5 * f * f) >> 1
        val ff = l * f
        if ((n & bitmask) == 0) rec(ll, ff, bitmask >> 1)
        else rec((ll + 5 * ff) >> 1, (ll + ff) >> 1, bitmask >> 1)
      }
    rec(1, 1, Integer.highestOneBit(n) >> 1)
  }  
}