几周前我在Google+上看到了一条评论,其中有人展示了斐波那契数字的直接计算,这些数字并非基于递归而且没有使用记忆.他实际上只记得最后两个数字并不断添加它们.这是一个O(n)算法,但他非常干净地实现了它.所以我很快指出,更快的方法是利用它们可以被计算为[[0,1],[1,1]]矩阵的幂的事实,它只需要一个O(log(N))计算.
问题当然是,这远远超过某一点.只要数字不是太大就有效,但它们以N*log(phi)/ log(10)的速率增长,其中N是第N个斐波那契数,phi是黄金比((1) + sqrt(5))/ 2~1.6).事实证明,log(phi)/ log(10)非常接近1/5.因此,预计Nth Fibonacci数字大约为N/5位数.
当数字开始有数百万或数十亿的数字时,矩阵乘法,即使偶数乘法,也会非常慢.因此,F(100,000)计算大约0.03秒(在Python中),而F(1000,000)大约需要5秒钟.这几乎不是O(log(N))增长.我的估计是这种方法没有改进,只是将计算优化为O((log(N))^(2.5))左右.
以这个速率计算第十亿个Fibonacci数将会非常慢(即使它只有〜1,000,000,000/5位数,因此它很容易适合32位内存).
有谁知道一个允许更快计算的实现或算法？也许某些东西可以计算出万亿的斐波纳契数.
而且要清楚,我不是在寻找近似值.我正在寻找精确的计算(到最后一位数).
编辑1: 我正在添加Python代码以显示我认为的O((log N)^ 2.5))算法.
from operator import mul as mul
from time import clock
class TwoByTwoMatrix:
__slots__ = "rows"
def __init__(self, m):
self.rows = m
def __imul__(self, other):
self.rows = [[sum(map(mul, my_row, oth_col)) for oth_col in zip(*other.rows)] for my_row in self.rows]
return self
def intpow(self, i):
i = int(i)
result = TwoByTwoMatrix([[long(1),long(0)],[long(0),long(1)]])
if i <= 0:
return result
k = 0
while i % 2 == …