энное число Фибоначчи в подлинейное время

В Википедии есть решение для закрытой формы http://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;
    }

You can do it by exponentiating a matrix of integers as well. If you have the matrix

    / 1  1 \
M = |      |
    \ 1  0 /

then (M^n)[1, 2] is going to be equal to the nth Fibonacci number, if [] is a matrix subscript and ^ is matrix exponentiation. For a fixed-size matrix, exponentiation to an positive integral power can be done in O(log n) time in the same way as with real numbers.

EDIT: Of course, depending on the type of answer you want, you may be able to get away with a constant-time algorithm. Like the other formulas show, the nth Fibonacci number grows exponentially with n. Even with 64-bit unsigned integers, you'll only need a 94-entry lookup table in order to cover the entire range.

SECOND EDIT: Doing the matrix exponential with an eigendecomposition first is exactly equivalent to JDunkerly's solution below. The eigenvalues of this matrix are the (1 + sqrt(5))/2 and (1 - sqrt(5))/2.

Одно из упражнений в SICP посвящено этому, ответ на который описан здесь.

В императивном стиле программа будет выглядеть примерно так.

Function Fib(count)
    a ← 1
    b ← 0
    p ← 0
    q ← 1

    While count > 0 Do
        If Even(count) Then
             p ← p² + q²
             q ← 2pq + q²
             count ← count ÷ 2
        Else
             a ← bq + aq + ap
             b ← bp + aq
             count ← count - 1
        End If
    End While

    Return b
End Function

При доступе к значению поля передайте экземпляр, а не null.

Почему бы здесь не использовать генерацию кода? Eclipse, например, сгенерирует для вас реальную реализацию toString.

Mn = (Mn/2)2 if n even
   = M·Mn-1 if n is odd

Разложение по собственным значениям на M находит две матрицы U и Λ такие, что Λ диагонально и

 M  = U Λ U-1 
 Mn = ( U Λ U-1) n
    = U Λ U-1 U Λ U-1 U Λ U-1 ... n times
    = U Λ Λ Λ ... U-1 
    = U Λ n U-1 

диагональная матрица Λ в n -й степени - это простой вопрос возведения каждого элемента в Λ до n -й степени, так что это дает O (1) метод возведения M в степень n . Однако значения в Λ вряд ли будут целыми числами, поэтому произойдет некоторая ошибка.

Определение Λ для нашей матрицы 2x2 как

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

Чтобы найти каждое λ , мы решаем

 |M - λI| = 0

, что дает

 |M - λI| = -λ ( 1 - λ ) - 1

λ² - λ - 1 = 0

, используя формулу корней квадратного уравнения

λ    = ( -b ± √ ( b² - 4ac ) ) / 2a
     = ( 1 ± √5 ) / 2
 { λ1, λ2 } = { Φ, 1-Φ } where Φ = ( 1 + √5 ) / 2

Если вы ' Прочитав ответ Джейсона, вы можете увидеть, к чему это приведет.

Решение для собственных векторов X ₁ и X ₂ :

if X1 = [ X1,1, X1,2 ]

 M.X1 1 = λ1X1

 X1,1 + X1,2 = λ1 X1,1
 X1,1      = λ1 X1,2

=>
 X1 = [ Φ,   1 ]
 X2 = [ 1-Φ, 1 ]

Эти векторы дают U :

U = [ X1,1, X2,2 ]
    [ X1,1, X2,2 ]

  = [ Φ,   1-Φ ]
    [ 1,   1   ]

Инвертирование U с использованием

A   = [  a   b ]
      [  c   d ]
=>
A-1 = ( 1 / |A| )  [  d  -b ]
                   [ -c   a ]

, поэтому 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   Φ ]

let Ψ = 1-Φ, the other eigenvalue

as Φ is a root of λ²-λ-1=0 
so  -ΨΦ = Φ²-Φ = 1
and Ψ+Φ = 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 ⁿ _1,2 :

Mn = UΛnU-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 ] as ΨΦ = -1

   = ( √5 )-1 [ Φn+1-Ψn+1      Φn-Ψn ]
              [ Φn-Ψn      Φn-1-Ψn-1 ]

so

 fib(n) = Mn1,2
        = ( Φn - (1-Φ)n ) / √5

Что согласуется с формулой, приведенной в другом месте.

Вы можете получить это из рекуррентного отношения,но в инженерных вычислениях и моделировании вычисление собственных значений и собственных векторов больших матриц является важным видом деятельности, так как это дает стабильность и гармоники систем уравнений, а также позволяет эффективно возводить матрицы в высокие степени.

Если вам нужно точное число (которое является "большим числом", а не целым числом с плавающей запятой), тогда я боюсь, что

Это невозможно!

Как указано выше, формула для чисел Фибоначчи такова:

fib n = floor (phi ⁿ / √5 + ¹ / ₂ )

fib n ~ = phi ⁿ / √5

Сколько цифр в fib n ?

numDigits (fib n) = log (fib n) = log (phi ⁿ / √5) = log phi ⁿ - журнал √5 = n * log phi - журнал √5

numDigits (fib n) = n * const + const

это O ( n )

Поскольку запрошенный результат имеет вид O ( n ), его нельзя вычислить менее чем за O ( n ) времени.

Если вам нужны только младшие цифры ответа, то можно рассчитать за сублинейное время, используя метод матричного возведения в степень.

с использованием 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