Число n-й фибоначчи в сублинейном времени

Ответ 1

Число Фибоначчи n определяется как

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

где

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

Предполагая, что примитивные математические операции (+, -, * и /) равны O(1) вы можете использовать этот результат для вычисления n го числа Фибоначчи за O(log n) времени (O(log n) из-за возведения в степень в формула).

В С#:

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);
}

Ответ 2

Следуя ссылке Пиллси на возведение в степень матрицы, такую, что для матрицы

M = [1 1] 
    [1 0] 

то

fib(n) = Mn1,2

Приведение матриц к степеням с использованием повторного умножения не очень эффективно.

Два подхода к экспоненции матрицы делятся и покоряются, что дает M ⁿ в O (ln n) шагов или декомпозиции собственных значений, которые являются постоянным временем, но могут приводить к ошибкам из-за ограниченной точности с плавающей точкой.

Если вы хотите, чтобы точное значение превышало точность вашей реализации с плавающей запятой, вы должны использовать подход O (ln n), основанный на этом отношении:

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

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

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

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

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

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

 |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 = λ1X1X1,1 + X1,2 = λ1X1,1X1,1      = λ1X1,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 ]

так

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

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

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

Ответ 3

Если вы хотите точный номер (который является "bignum", а не int/float), то я боюсь, что

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

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

fib n = floor (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).

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

Ответ 4

Один из упражнений в 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

Ответ 5

Вы можете сделать это, указав также матрицу целых чисел. Если у вас есть матрица

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

то (M^n)[1, 2] будет равняться числу n th Фибоначчи, если [] является матричным индексом, а ^ является экспоненциальной матрицей. Для матрицы фиксированного размера экспоненциация на положительную интегральную мощность может быть выполнена в O (log n) раз так же, как и с вещественными числами.

EDIT: Конечно, в зависимости от типа ответа, который вы хотите, вы можете уйти с алгоритмом с постоянным временем. Как показывают другие формулы, число n th Фибоначчи растет экспоненциально с n. Даже с 64-разрядными целыми числами без знака вам понадобится только таблица с 94-позиционным поиском, чтобы охватить весь диапазон.

ВТОРОЙ РЕДАКТИРОВАНИЕ: Выполнение матричной экспоненты с первой функцией eigendecomposition в точности эквивалентно решению JDunkerly ниже. Собственными значениями этой матрицы являются (1 + sqrt(5))/2 и (1 - sqrt(5))/2.

Ответ 6

Википедия имеет закрытое решение формы http://en.wikipedia.org/wiki/Fibonacci_number

Или в С#:

    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;
    }

Ответ 7

Для действительно больших, эта рекурсивная функция работает. Он использует следующие уравнения:

F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)

Вам нужна библиотека, которая позволяет работать с большими целыми числами. Я использую библиотеку BigInteger из https://mattmccutchen.net/bigint/.

Начните с массива чисел фибоначчи. Используйте fibs [0] = 0, fibs [1] = 1, fibs [2] = 1, fibs [3] = 2, fibs [4] = 3 и т.д. В этом примере я использую массив из первых 501 (считая 0). Здесь вы можете найти первые 500 ненулевых чисел Фибоначчи: http://home.hiwaay.net/~jalison/Fib500.html. Для правильного формата требуется небольшое редактирование, но это не слишком сложно.

Затем вы можете найти любое число Фибоначчи, используя эту функцию (в 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);
}

Я тестировал это для 25 000-го числа Фибоначчи и т.п.

Ответ 8

Здесь моя рекурсивная версия, которая повторяет log (n) раз. Я думаю, что это проще всего читать в рекурсивной форме:

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)

Это работает, потому что вы можете вычислить fib(n),fib(n-1) с помощью fib(n-1),fib(n-2), если n нечетно, а если n четно, вы можете вычислить fib(n),fib(n-1) с помощью fib(n/2),fib(n/2-1).

Основной случай и нечетный случай просты. Чтобы получить четный случай, начните с a, b, c как последовательные значения фибоначчи (например, 8,5,3) и напишите их в матрице с a = b + c. Примечание:

[1 1] * [a b]  =  [a+b a]
[1 0]   [b c]     [a   b]

Отсюда видно, что матрица из первых трех чисел фибоначчи, раз матрица любых трех последовательных чисел фибоначчи, равна следующей. Поэтому мы знаем, что:

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

Упрощение правой стороны приводит к четному случаю.

Ответ 9

используя 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

Ответ 10

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

import time

_dict = {1:1, 2:1}

def F(n, _dict):
    if n in _dict.keys():
        return _dict[n]
    else:
        result = F(n-1, _dict) + F(n-2, _dict)
        _dict.update({n:result})
        return result

start = time.time()

for n in range(1,100000):
    result = F(n, _dict) 

finish = time.time()

print(str(finish - start))

Мы начинаем с тривиального словаря (первые два значения последовательности Фибоначчи) и постоянно добавляем значения Фибоначчи в словарь.

Первые 100000 значений Фибоначчи заняли около 0,7 секунды (процессор Intel Xeon E5-2680 с частотой 2,70 ГГц, 16 ГБ ОЗУ, операционная система Windows 10-64 бит)

Ответ 11

см. алгоритм разделения и покоя здесь

Ссылка имеет псевдокод для экспоненциальности матрицы, упомянутой в некоторых других ответах на этот вопрос.

Ответ 12

Арифметика с фиксированной точкой неточна. Код Jason С# дает неверный ответ для n = 71 (308061521170130 вместо 308061521170129) и далее.

Для правильного ответа используйте систему вычислительных алгебр. Sympy - это такая библиотека для Python. Там есть интерактивная консоль на http://live.sympy.org/. Скопируйте и вставьте эту функцию

phi = (1 + sqrt(5)) / 2
def f(n):
    return floor(phi**n / sqrt(5) + 1/2)

Затем вычислить

>>> f(10)
55

>>> f(71)
308061521170129

Вам может потребоваться проверить phi.

Ответ 13

Вы можете использовать странное уравнение квадратного корня, чтобы получить точный ответ. Причина в том, что $\ 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

Ответ 14

Здесь однострочник, который вычисляет F (n), используя целые числа размера O (n), в O (log n) арифметических операциях:

for i in range(1, 50):
    print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))

Использование целых чисел размера O (n) разумно, так как это сопоставимо с размером ответа.

Чтобы понять это, пусть phi - золотое сечение (наибольшее решение для x ^ 2 = x + 1), а F (n) - n-ое число Фибоначчи, где F (0) = 0, F (1) = F (2) = 1

Теперь phi ^ n = F (n-1) + F (n) phi.

Доказательство по индукции: фи ^ 1 = 0 + 1 * фи = F (0) + F (1) фи. И если phi ^ n = F (n-1) + F (n) phi, то phi ^ (n + 1) = F (n-1) phi + F (n) phi ^ 2 = F (n-1) фи + F (n) (фи + 1) = F (n) + (F (n) +F (n-1)) фи = F (n) + F (n + 1) фи. Единственный сложный шаг в этом расчете - это тот, который заменяет фи ^ 2 на (1 + фи), что следует из-за того, что фи - это золотое сечение.

Также числа вида (a + b * phi), где a, b целые числа, замкнуты при умножении.

Доказательство: (p0 + p1 * phi) (q0 + q1 * phi) = p0q0 + (p0q1 + q1p0) phi + p1q1 * phi ^ 2 = p0q0 + (p0q1 + q1p0) phi + p1q1 * (phi + 1) = ( p0q0 + p1q1) + (p0q1 + q1p0 + p1q1) * фи.

Используя это представление, можно вычислить phi ^ n в O (log n) целочисленных операциях, используя возведение в степень путем возведения в квадрат. Результатом будет F (n-1) +F (n) phi, из которого можно прочитать n-е число Фибоначчи.

def mul(p, q):
    return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]

def pow(p, n):
    r=1,0
    while n:
        if n&1: r=mul(r, p)
        p=mul(p, p)
        n=n>>1
    return r

for i in range(1, 50):
    print(i, pow((0, 1), i)[1])

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

Чтобы добраться до строки, начинающей этот ответ, можно отметить, что, представляя phi достаточно большим целым числом X, можно выполнить (a+b*phi)(c+d*phi) как целочисленную операцию (a+bX)(c+dX) modulo (X^2-X-1). Затем функция pow может быть заменена стандартной функцией pow Python (которая обычно включает в себя третий аргумент z который вычисляет результат по модулю z. Выбранный X равен 2<<i.