次线性时间的第n个斐波纳契数

Question

次线性时间的第n个斐波纳契数是否有任何算法来计算子线性时间内的第n个斐波纳契数？

Answer 1

所述n第Fibonacci数由下式给出

f(n) = Floor(phi^n / sqrt(5) + 1/2)

哪里

phi = (1 + sqrt(5)) / 2

假设原始数学运算（+，-，*和/）是O(1)可以使用该结果来计算n在第Fibonacci数O(log n)时间（O(log 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);}

Answer 2

根据Pillsy对矩阵求幂的引用，对于矩阵

M = [1 1]
    [1 0]

然后

fib（n）= M n 1,2

使用重复乘法将矩阵提升到幂并不是非常有效。

矩阵求幂的两种方法是分而治之，其在O（ln n）步骤中产生M ⁿ，或者是恒定时间的特征值分解，但是由于有限的浮点精度可能引入误差。

如果希望精确值大于浮点实现的精度，则必须使用基于此关系的O（ln n）方法：

如果n even，则M n =（M n / 2）2如果n是奇数， 则
   = M · M n -1

M上的特征值分解找到两个矩阵U和Λ，使得Λ是对角线和

 中号   = û  Λ  ù -1  
 中号Ñ =（û  Λ  Ú -1）ñ 
    = Ü  Λ  ù -1  ù  Λ  ù -1  ù  Λ  ù -1 ... n次
    = ü  Λ  Λ  Λ ... ü -1  
    = ü  Λ  ñ  ü -1

养对角矩阵Λ的Ñ次方是在提高各个元件的一个简单的事情 Λ到Ñ个，所以这给出了提高的O（1）方法中号至Ñ次方。但是，Λ中的值不可能是整数，因此会出现一些错误。

为我们的2x2矩阵定义Λ

Λ = [λ 1 0]
  = [0λ 2 ]

为了找到每个λ，我们解决了

| 中号 - λ 我 | = 0

这使

| 中号 - λ 我 | =-λ（1  - λ） -  1λ² - λ -  1 = 0

使用二次方程式

λ=（ -  b±√（b²-4ac））/ 2a
     =（1±√5）/ 2
 {λ 1，λ 2 } = {Φ，1-Φ}其中Φ=（1 +√5）/ 2

如果您已经阅读了杰森的答案，您可以看到这将会发生什么。

求解特征向量X ₁和X ₂：

如果X 1 = [ X 1,1，X 1,2 ]
 中号。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-Φ，另一个特征值因为Φ是λ²-λ-1 = 0的根 所以-ΨΦ=Φ²-Φ= 1和Ψ+Φ= 1UΛ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 ⁿ _1,2所需的一切：

中号Ñ = û Λ Ñ ù -1 
   =（√5）-1 [ΦΨ]。[Φ Ñ   0]。[1-Ψ]
              [1 1] [0Ψ Ñ ] [-1Φ]
   =（√5）-1 [ΦΨ]。[Φ Ñ   -ΨΦ Ñ ]
              [11] [-Ψ Ñ    Ψ Ñ Φ]
   =（√5）-1 [ΦΨ]。[Φ Ñ    Φ Ñ -1 ]
              [1 1] [-Ψn -   Ψn - 1 ]为ΨΦ= -1
   =（√5）-1 [Φ Ñ 1 -Ψ Ñ 1       Φ Ñ -Ψ Ñ ]
              [Φ Ñ -Ψ Ñ       Φ Ñ -1 -Ψ Ñ -1 ]

所以

 FIB（Ñ）= 中号Ñ 1,2 
        =（Φ ñ - （1-Φ）ñ）/√5

这与其他地方给出的公式一致。

您可以从重复关系推导出它，但在工程计算和模拟中计算大矩阵的特征值和特征向量是一项重要的活动，因为它给出了方程组的稳定性和谐波，并允许有效地将矩阵提高到高功率。

Answer 3

如果你想要确切的数字（这是一个“bignum”，而不是一个int / float），那我恐怕

不可能！

如上所述，斐波纳契数的公式为：

FIB N =地板（PHI ^ñ /√5+ ¹ / ₂）

fib n~ = phi ⁿ /√5

多少位数fib n？

numDigits（fib n）= log（fib n）= log（phi ⁿ /√5）= log phi ⁿ - log√5= n * log phi - log√5

numDigits（fib n）= n * const + const

这是O（n）

由于请求的结果是O（n），因此不能在小于O（n）的时间内计算。

如果您只想要答案的低位数，则可以使用矩阵求幂方法在子线性时间内计算。