第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] 

然后

  fibn )= M n 1,2 

使用重复乘法将matrix提升到功率并不是非常有效。

matrix求幂的两种方法是分而治之,它们在Oln n )步中产生M n ,或者是恒定时间的特征值分解,但由于浮点精度有限可能引入误差。

如果你想要一个精确的值大于你的浮点实现的精度,你必须使用基于这个关系的O(ln n)方法:

 如果n偶数,则M n =( M n / 22
    = M · M n -1如果n是奇数

M上的特征值分解find两个matrixUΛ ,使得Λ是对angular的

  M = UΛU -1 
  M n =( UΛU -1n
     = 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 1X 2

如果X 1 = [ X 1,1X 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,1X 2,2 ]
     [ X 1,1X 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 ]

所以

  fibn )= 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

它是On

由于要求的结果是On ),所以不能在小于On )的时间内计算。

如果您只需要答案的低位数字,那么可以使用matrix求幂方法在亚线性时间内进行计算。

SICP中的一个练习是关于这个的,这里有这个答案。

在必要的风格,程序会看起来像

 function Fib计数一个 ←1
     b ←0
     p ←0
     q ←1

     count > 0时
         如果偶( 然后
              p ←p²+ 
              q ←2 pq + 
              计数计数 ÷2
         其他
              abq + aq + ap
              bbp + 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/有一个交互式控制台&#x3002; 复制并粘贴此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