scala - 在 Scala 中编写斐波那契函数的最快方法是什么？

Question

我从 very simple one 开始研究了 Scala 中斐波那契函数的一些实现。 ，到more complicated ones .

我不完全确定哪一个最快。我倾向于认为使用记忆化的速度更快，但是我想知道为什么 Scala 没有原生记忆化。

任何人都可以启发我编写斐波那契函数的最佳、最快(且最干净)的方法吗？

Answer 1

最快的版本是在某种程度上偏离通常的添加方案的版本。计算速度非常快，在某种程度上类似于基于以下公式的快速二进制求幂:

F(2n-1) = F(n)² + F(n-1)²
F(2n) = (2F(n-1) + F(n))*F(n)

这是一些使用它的代码:

def fib(n:Int):BigInt = {
   def fibs(n:Int):(BigInt,BigInt) = if (n == 1) (1,0) else {
     val (a,b) = fibs(n/2)
     val p = (2*b+a)*a
     val q = a*a + b*b
     if(n % 2 == 0) (p,q) else (p+q,p)
   }
   fibs(n)._1
}

尽管这不是很优化(例如内部循环不是尾递归)，但它会击败通常的附加实现。