第n次斐波纳契数在次线性时间
有没有algorithm来计算次线性时间的第n个斐波纳契数？
第n个斐波纳契数由下式给出
f(n) = Floor(phi^n / sqrt(5) + 1/2)
哪里
phi = (1 + sqrt(5)) / 2
假设原始math运算（ + ， - ， *和/ ）为O(1) ，则可以使用此结果计算O(log n)时间（ O(log n)中的第n个斐波那契数，因为公式）。
在C＃中：
static double inverseSqrt5 = 1 / Math.Sqrt(5); static double phi = (1 + Math.Sqrt(5)) / 2; /* should use const double inverseSqrt5 = 0.44721359549995793928183473374626 const double phi = 1.6180339887498948482045868343656 */ static int Fibonacci(int n) { return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5); }
从Pillsy提到的matrix幂运算之后，这样的matrix
M = [11]
[1 0]
然后
fib （ n ）= M n 1,2
使用重复乘法将matrix提升到功率并不是非常有效。
matrix求幂的两种方法是分而治之，它们在O （ ln n ）步中产生M n ，或者是恒定时间的特征值分解，但由于浮点精度有限可能引入误差。
如果你想要一个精确的值大于你的浮点实现的精度，你必须使用基于这个关系的O（ln n）方法：
如果n偶数，则M n =（ M n / 2 ） 2
= M · M n -1如果n是奇数
M上的特征值分解find两个matrixU和Λ ，使得Λ是对angular的
M = UΛU -1
M n =（ UΛU -1 ） n
= UΛU -1 UΛU -1 UΛU -1 ... n次
= UΛΛΛ ... U -1
= UΛn U -1
将对angularmatrixΛ提高到第n次幂是将∧中的每个元素都提高到第n次的简单事情，因此这给出了将M提高到第n次幂的O（1）方法。 然而， Λ中的值不可能是整数，所以会出现一些错误。
定义Λ为我们的2x2matrix
Λ = [λ1 0] = [0λ2]
为了find每个λ ，我们解决
| M - λI | = 0
这使
| M - λI | =-λ（1-λ）-1 λ2 - λ - 1 = 0
使用二次公式
λ=（ - b±√（b 2 -4ac））/ 2a
=（1±√5）/ 2
{λ1，λ2} = {Φ，1-Φ}其中Φ=（1 +√5）/ 2
如果你已经读过杰森的答案，你可以看到这个将要去的地方。
求解特征向量X 1和X 2 ：
如果X 1 = [ X 1,1 ， X 1,2 ] M。 X 1 1 =λ1 X 1 X 1,1 + X 1,2 =λ1 X 1,1 X 1,1 =λ1 X 1,2 => X 1 = [Φ，1] X 2 = [1-Φ，1]
这些载体给U ：
U = [ X 1,1 ， X 2,2 ]
[ X 1,1 ， X 2,2 ]
= [Φ，1-Φ]
[1,1]
倒U使用
A = [ab]
[cd]
=>
A -1 =（1 / | A |）[d -b]
[-ca]
所以U -1是由
U -1 =（1 /（Φ-（1-Φ））[1Φ-1]
[-1Φ]
U -1 =（√5） -1 [1Φ-1]
[-1Φ]
完整性检查：
UΛU -1 =（√5） -1 [ Φ1 -Φ]。 [Φ0]。 [1Φ-1]
[1 1] [0 1-Φ] [-1Φ]
令Ψ= 1-Φ，另一个特征值
因为Φ是λ2-λ-1 = 0的根
so-ΨΦ=Φ2-Φ= 1
和Ψ+Φ= 1
UΛU -1 =（√5） -1 [ ΦΨ ]。 [Φ0]。 [1-Ψ]
[1 1] [0Ψ] [-1Φ]
=（√5） -1 [ΦΨ]。 [Φ-ΨΦ]
[1 1] [-ΨΨΦ]
=（√5） -1 [ΦΨ]。 [Φ1]
[1 1] [-Ψ-1]
=（√5） -1 [Φ²-Ψ²Φ-Ψ]
[Φ-Ψ0]
= [Φ+Ψ1]
[1 0]
= [1 1]
[1 0]
= M
所以，理智检查成立。
现在我们有我们需要的一切来计算M n 1,2 ：
M n = UΛn U -1
=（√5） -1 [ΦΨ]。 [Φn 0]。 [1-Ψ]
[1 1] [0Ψn] [-1Φ]
=（√5） -1 [ΦΨ]。 [Φn - ΨΦn]
[1 1] [-ΨnΨnΦ]
=（√5） -1 [ΦΨ]。 [ΦnΦn -1 ]
[1 1] [-Ψn - Ψn - 1 ]为ΨΦ= -1
=（√5） -1 [Φn +1 - Ψn + 1Φn - Ψn]
[Φn - ΨnΦn -1 - Ψn -1 ]
所以
fib （ n ）= M n 1,2
=（Φn - （1-Φ） n ）/√5
这与其他地方给出的公式一致。
你可以从一个recursion关系推导出来，但是在工程计算和模拟中，计算大matrix的特征值和特征向量是一个重要的活动，因为它给出了方程组的稳定性和谐波，并且允许matrix有效地提高到高功率。
如果你想确切的数字（这是一个“bignum”，而不是一个整数/浮点数），那么我恐怕
不可能！
如上所述，斐波那契数的公式是：
fib n = floor（phi n /√5+ 1/2 ）
fib n〜= phi n /√5
fib n有多less个数字？
numDigits（fib n）= log（fib n）= log（phi n /√5）= log phi n -log√5= n * log phi -log√5
numDigits（fib n）= n * const + const
它是O （ n ）
由于要求的结果是O （ n ），所以不能在小于O （ n ）的时间内计算。
如果您只需要答案的低位数字，那么可以使用matrix求幂方法在亚线性时间内进行计算。
SICP中的一个练习是关于这个的，这里有这个答案。
在必要的风格，程序会看起来像
function Fib （ 计数 ）
一个 ←1
b ←0
p ←0
q ←1
count > 0时
如果偶（ 数 ） 然后
p ←p²+ q²
q ←2 pq + q²
计数 ← 计数 ÷2
其他
a ← bq + aq + ap
b ← bp + aq
计数 ← count - 1
万一
结束时
退货 b
结束function
您也可以通过指数整数matrix来完成。 如果你有matrix
/ 1 1 \ M = | | \ 1 0 /
那么(M^n)[1, 2]将等于第n个斐波那契数，如果[]是matrix下标，并且^是matrix求幂。 对于一个固定大小的matrix，可以按照与实数相同的方式在O（log n）时间内完成对正整数功率的求幂。
编辑：当然，根据你想要的答案的types，你可能能够逃脱恒定时间的algorithm。 像其他公式所示，第n个斐波那契数与n指数关系地增长。 即使使用64位无符号整数，您也只需要一个94条目的查找表来覆盖整个范围。
第二次编辑：matrix指数与本征分解首先完全等同于JDunkerly的解决scheme。 这个matrix的特征值是(1 + sqrt(5))/2和(1 - sqrt(5))/2 。
维基百科有一个封闭的forms解决schemehttp://en.wikipedia.org/wiki/Fibonacci_number
或在C＃中：
public static int Fibonacci(int N) { double sqrt5 = Math.Sqrt(5); double phi = (1 + sqrt5) / 2.0; double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5; return (int)fn; }
对于真正大的，这个recursion函数起作用。 它使用以下等式：
F(2n-1) = F(n-1)^2 + F(n)^2 F(2n) = (2*F(n-1) + F(n)) * F(n)
你需要一个图书馆，让你用大整数工作。 我使用https://mattmccutchen.net/bigint/中的BigInteger库。;
从一组斐波那契数字开始。 使用fibs [0] = 0，fibs [1] = 1，fibs [2] = 1，fibs [3] = 2，fibs [4] = 3等。在这个例子中，我使用了第一个501 （数0）。 你可以在这里find前500个非零斐波那契数字： http : //home.hiwaay.net/~jalison/Fib500.html 。 它需要一点编辑，以正确的格式，但这并不难。
那么你可以find任何使用这个函数的斐波那契数（在C中）：
BigUnsigned GetFib(int numfib) { int n; BigUnsigned x, y, fib; if (numfib < 501) // Just get the Fibonacci number from the fibs array { fib=(stringToBigUnsigned(fibs[numfib])); } else if (numfib%2) // numfib is odd { n=(numfib+1)/2; x=GetFib(n-1); y=GetFib(n); fib=((x*x)+(y*y)); } else // numfib is even { n=numfib/2; x=GetFib(n-1); y=GetFib(n); fib=(((big2*x)+y)*y); } return(fib); }
我已经testing了第25,000个斐波纳契数字之类的东西。
这是recursionlog（n）次的recursion版本。 我认为最简单的recursionforms是：
def my_fib(x): if x < 2: return x else: return my_fib_helper(x)[0] def my_fib_helper(x): if x == 1: return (1, 0) if x % 2 == 1: (p,q) = my_fib_helper(x-1) return (p+q,p) else: (p,q) = my_fib_helper(x/2) return (p*p+2*p*q,p*p+q*q)
因为如果n是奇数，并且如果n是偶数，则可以使用fib(n-1),fib(n-2)来计算fib(n),fib(n-1) fib(n),fib(n-1)使用fib(n/2),fib(n/2-1) 。
基本情况和奇怪的情况很简单。 为了导出偶数情况，以a，b，c作为连续的斐波那契数值（例如8,5,3），并将它们写成matrix，其中a = b + c。 注意：
[1 1] * [ab] = [a+ba] [1 0] [bc] [ab]
由此我们可以看到，前三个斐波纳契数的matrix是任意三个连续斐波那契数的matrix，等于下一个matrix。 所以我们知道：
n [1 1] = [fib(n+1) fib(n) ] [1 0] [fib(n) fib(n-1)]
所以：
2n 2 [1 1] = [fib(n+1) fib(n) ] [1 0] [fib(n) fib(n-1)]
简化右侧导致甚至情况。
使用R
l1 <- (1+sqrt(5))/2 l2 <- (1-sqrt(5))/2 P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix S <- matrix(c(l1,1,l2,1),nrow=2) L <- matrix(c(l1,0,0,l2),nrow=2) C <- c(-1/(l2-l1),1/(l2-l1)) k<-20 ; (S %*% L^k %*% C)[2] [1] 6765
这里看分治法
在这个问题的一些其他答案中提到的链接有matrix求幂的伪代码。
定点算术是不准确的。 Jason的C＃代码给出了n = 71（308061521170130而不是308061521170129）及以后的不正确答案。
要得到正确答案，请使用计算代数系统。 Sympy就是这样一个Python库。 在http://live.sympy.org/有一个交互式控制台。; 复制并粘贴此function
phi = (1 + sqrt(5)) / 2 def f(n): return floor(phi**n / sqrt(5) + 1/2)
然后计算
>>> f(10) 55 >>> f(71) 308061521170129
你可能想尝试检查phi 。
你可以使用奇怪的平方根方程得到一个确切的答案。 原因是$ \ sqrt（5）$最后会掉出来，你只需要用自己的乘法格式来跟踪系数。
def rootiply(a1,b1,a2,b2,c): ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b''' return a1*a2 + b1*b2*c, a1*b2 + a2*b1 def rootipower(a,b,c,n): ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format''' ar,br = 1,0 while n != 0: if n%2: ar,br = rootiply(ar,br,a,b,c) a,b = rootiply(a,b,a,b,c) n /= 2 return ar,br def fib(k): ''' the kth fibonacci number''' a1,b1 = rootipower(1,1,5,k) a2,b2 = rootipower(1,-1,5,k) a = a1-a2 b = b1-b2 a,b = rootiply(0,1,a,b,5) # b should be 0! assert b == 0 return a/2**k/5 if __name__ == "__main__": assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3) assert fib(10)==55
