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

Question

Есть ли какой-либо алгоритм для вычисления n-го числа фибоначчи в сублинейном времени?

Answer 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) из-за потенцирования в формуле).

В 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

Википедия имеет замкнутую форму решения 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; 
    } 

Answer 3

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

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

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

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

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

Answer 4

Один из exercises in SICP около этого, который имеет ответ описано here.

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

 
FunctionFib(count) 
    a ← 1 
    b ← 0 
    p ← 0 
    q ← 1 

    Whilecount > 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 

    Returnb 
End Function 

Answer 5

Исходя из ссылки Pillsy на матрицу возведения в степень, таким образом, что для матрицы

 
M = [1 1] 
    [1 0] 

затем

fib(n) = Mn1,2

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

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

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

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

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

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

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

& Lambda; для 2х2 матрицы как

 
Λ = [ λ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 

Если вы читали ответ Джейсона, вы можете увидеть, где это будет идти.

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

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

M.X1 1 = λ1X1 

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

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

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

Answer 6

Если вы хотите, точное число (которое является «bignum», а не INT/поплавка), то я боюсь, что

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

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

FIB п = пол (фи ^п/√5 + /)

FIB п ~ = фи ^п/√5

Как много цифр fib n?

numDigits (FIB п) = лог (FIB п) = лог (фи ^п/√5) = лог фи ^п - журнал √5 = п * журнала фи - журнал √5

numDigits (FIB) п = п * + Const Const

это O (п)

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

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

Answer 7

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

Answer 8

см разделяй и властвуй алгоритм here

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

Answer 9

Арифметика с фиксированной точкой является неточной. Код C# Джейсона дает неверный ответ для 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.

Answer 10

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

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,000th числа Фибоначчи и тому подобного.

Answer 11

Вот моя рекурсивная версия, которая повторяет 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), если п нечетно, и если п четно, то можно вычислить с помощью 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)] 

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

Answer 12

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