所述n第Fibonacci數(shù)由下式給出

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

哪里

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

假設(shè)原始數(shù)學(xué)運算（+，-，*和/）是O(1)可以使用該結(jié)果來計算n在第Fibonacci數(shù)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);}

根據(jù)Pillsy對矩陣求冪的引用，對于矩陣

M = [1 1]
    [1 0]

然后

fib（n）= M n 1,2

使用重復(fù)乘法將矩陣提升到冪并不是非常有效。

矩陣求冪的兩種方法是分而治之，其在O（ln n）步驟中產(chǎn)生M ⁿ，或者是恒定時間的特征值分解，但是由于有限的浮點精度可能引入誤差。

如果希望精確值大于浮點實現(xiàn)的精度，則必須使用基于此關(guān)系的O（ln n）方法：

如果n even，則M n =（M n / 2）2如果n是奇數(shù)， 則
   = M · M n -1

M上的特征值分解找到兩個矩陣U和Λ，使得Λ是對角線和

 中號   = ?  Λ  ù -1  
 中號? =（?  Λ  ú -1）? 
    = ü  Λ  ù -1  ù  Λ  ù -1  ù  Λ  ù -1 ... n次
    = ü  Λ  Λ  Λ ... ü -1  
    = ü  Λ  ?  ü -1

養(yǎng)對角矩陣Λ的?次方是在提高各個元件的一個簡單的事情 Λ到?個，所以這給出了提高的O（1）方法中號至?次方。但是，Λ中的值不可能是整數(shù)，因此會出現(xiàn)一些錯誤。

為我們的2x2矩陣定義Λ

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

為了找到每個λ，我們解決了

| 中號 - λ 我 | = 0

這使

| 中號 - λ 我 | =-λ（1  - λ） -  1λ2 - λ -  1 = 0

使用二次方程式

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

如果您已經(jīng)閱讀了杰森的答案，您可以看到這將會發(fā)生什么。

求解特征向量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]

使用反轉(zhuǎn)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的根 所以-ΨΦ=Φ2-Φ= 1和Ψ+Φ= 1UΛU -1 =（√5）-1 [ ΦΨ ]。[Φ0]。[1-Ψ]
                 [1 1] [0Ψ] [-1Φ]
       =（√5）-1 [ΦΨ]。[Φ-ΨΦ]
                 [1 1] [-ΨΨΦ]
       =（√5）-1 [ΦΨ]。[Φ1]
                 [1 1] [-Ψ-1]
       =（√5）-1 [Φ2-Ψ2Φ-Ψ]
                  [Φ-Ψ0]
       = [Φ+Ψ1]    
         [1 0]
       = [1 1] 
         [1 0]
       = M.

所以理智檢查成立。

現(xiàn)在我們有了計算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

這與其他地方給出的公式一致。

您可以從重復(fù)關(guān)系推導(dǎo)出它，但在工程計算和模擬中計算大矩陣的特征值和特征向量是一項重要的活動，因為它給出了方程組的穩(wěn)定性和諧波，并允許有效地將矩陣提高到高功率。

如果你想要確切的數(shù)字（這是一個“bignum”，而不是一個int / float），那我恐怕

不可能！

如上所述，斐波納契數(shù)的公式為：

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

fib n~ = phi ⁿ /√5

多少位數(shù)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）

由于請求的結(jié)果是O（n），因此不能在小于O（n）的時間內(nèi)計算。

如果您只想要答案的低位數(shù)，則可以使用矩陣求冪方法在子線性時間內(nèi)計算。