n ° numero di fibonacci in tempo sublimatico

Esiste un algoritmo per calcolare l’ennesimo numero di fibonacci in sub linear time?

Il n numero di Fibonacci è dato da

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

dove

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

Supponendo che le operazioni matematiche primitive ( + , - , * e / ) siano O(1) puoi usare questo risultato per calcolare il n numero di Fibonacci in O(log n) tempo ( O(log n) causa dell’esponenziazione in la formula).

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

Seguendo il riferimento di Pillsy all’esponenziazione della matrice, tale che per la matrice

 M = [1 1] 
     [1 0] 

poi

  fib ( n ) = M n 1,2 

Aumentare le matrici per le potenze usando la moltiplicazione ripetuta non è molto efficiente.

Due approcci all’esponenziazione della matrice sono divisione e conquista che produce M n in passi O ( ln n ), o scomposizione autovalore che è un tempo costante, ma possono introdurre errori dovuti alla precisione a virgola mobile limitata.

Se si desidera un valore esatto maggiore della precisione dell’implementazione in virgola mobile, è necessario utilizzare l’approccio O (ln n) basato su questa relazione:

  M n = ( M n / 2 ) 2 se n pari
    = M · M n -1 se n è dispari

La scomposizione dell’autovalore su M trova due matrici U e Λ tali che Λ è diagonale e

  M = U Λ U -1 
  M n = ( U Λ U -1 ) n
     = U Λ U -1 U Λ U -1 U Λ U -1 ... n volte
     = U Λ Λ Λ ... U -1 
     = U Λ n U -1 

Alzare una matrice diagonale Λ al nesimo potere è una semplice questione di innalzare ciascun elemento in Λ al n , quindi questo dà un metodo O (1) di elevare M alla potenza n . Tuttavia, i valori in Λ non sono probabilmente interi, quindi si verificherà un errore.

Definire Λ per la nostra matrice 2×2 come

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

Per trovare ogni λ , risolviamo

  |  M - λ I |  = 0 

che dà

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

 λ² - λ - 1 = 0

usando la formula quadratica

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

Se hai letto la risposta di Jason, puoi vedere dove andrà.

Risoluzione per gli autovettori X 1 e X 2 :

 se X 1 = [ X 1,1 , X 1,2 ]

  M.  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]

Questi vettori danno U :

 U = [ X 1,1 , X 2,2 ]
     [ X 1,1 , X 2,2 ]

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

Invertendo U usando

 A = [ab]
       [cd]
 =>
 A -1 = (1 / | A |) [d -b]
                    [ -circa ]

quindi U -1 è dato da

 U -1 = (1 / (Φ - (1 - Φ)) [1 Φ-1]
                                [-1 Φ]
 U -1 = (√5) -1 [1 Φ-1]
                [-1 Φ]

Controllo sanitario:

 UΛU -1 = (√5) -1 [Φ 1-Φ].  [Φ 0].  [1 Φ-1] 
                      [1 1] [0 1-Φ] [-1 Φ]

 sia Ψ = 1-Φ, l'altro autovalore

 come Φ è una radice di λ²-λ-1 = 0 
 quindi -ΨΦ = Φ²-Φ = 1
 e Ψ + Φ = 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 

Quindi il controllo di sanità mentale tiene.

Ora abbiamo tutto il necessario per calcolare M n 1,2 :

 M n = U Λ n U -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] [-Ψ nn -1 ] come ΨΦ = -1

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

così

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

Che è d’accordo con la formula fornita altrove.

È ansible ricavarlo da una relazione di ricorrenza, ma nel calcolo ingegneristico e nella simulazione il calcolo degli autovalori e autovettori di matrici di grandi dimensioni è un’attività importante, in quanto fornisce stabilità e armoniche di sistemi di equazioni, oltre a consentire l’elevazione efficiente di matrici ad alte potenze.

Se vuoi il numero esatto (che è un “bignum”, piuttosto che un int / float), allora ho paura che

È imansible!

Come detto sopra, la formula per i numeri di Fibonacci è:

fib n = floor (phi n / √5 + 1/2 )

fib n ~ = phi n / √5

Quante cifre è fib n ?

numDigits (fib n) = log (fib n) = log (phi n / √5) = log phi n – log √5 = n * log phi – log √5

numDigits (fib n) = n * const + const

è O ( n )

Poiché il risultato richiesto è di O ( n ), non può essere calcolato in meno di O ( n ).

Se si desidera solo le cifre inferiori della risposta, è ansible calcolare in tempo sub-lineare utilizzando il metodo di esponenziazione della matrice.

Uno degli esercizi in SICP riguarda questo, che ha la risposta descritta qui.

In uno stile imperativo, il programma avrebbe un aspetto simile

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

     Mentre conta > 0 Do
         Se pari ( contare ) Quindi
              pp ² + q ²
              q ← 2 pq + q ²
              conteggiocontare ÷ 2
         Altro
              abq + aq + ap
              bbp + aq
              contaconta - 1
         Finisci se
     Fine Mentre

     Ritorno b
 Fine Funzione

Puoi farlo esponenziando anche una matrice di interi. Se hai la matrice

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

allora (M^n)[1, 2] sarà uguale al n ° numero di Fibonacci, se [] è un indice matriciale e ^ è l’esponenziazione matriciale. Per una matrice a dimensione fissa, l’esponenziazione a una potenza integrale positiva può essere eseguita in tempo O (log n) allo stesso modo dei numeri reali.

EDIT: Ovviamente, a seconda del tipo di risposta che si desidera, si può essere in grado di farla franca con un algoritmo a tempo costante. Come mostrano le altre formule, il n ° numero di Fibonacci cresce esponenzialmente con n . Anche con interi senza segno a 64 bit, avrete bisogno solo di una tabella di ricerca a 94 voci per coprire l’intero intervallo.

SECONDA MODIFICA: fare la matrice esponenziale con una eigendecomposizione prima equivale esattamente alla soluzione di JDunkerly di seguito. Gli autovalori di questa matrice sono (1 + sqrt(5))/2 e (1 - sqrt(5))/2 .

Wikipedia ha una soluzione di forma chiusa http://en.wikipedia.org/wiki/Fibonacci_number

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

Per quelli veramente grandi, questa funzione ricorsiva funziona. Usa le seguenti equazioni:

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

Hai bisogno di una libreria che ti permetta di lavorare con i grandi numeri interi. Io uso la libreria BigInteger da https://mattmccutchen.net/bigint/ .

Inizia con una serie di numeri di Fibonacci. Usa fibs [0] = 0, fibs [1] = 1, fibs [2] = 1, fibs [3] = 2, fibs [4] = 3, ecc. In questo esempio, utilizzo un array del primo 501 (contando 0). Puoi trovare i primi 500 numeri di Fibonacci non zero qui: http://home.hiwaay.net/~jalison/Fib500.html . Ci vuole un po ‘di editing per metterlo nel formato giusto, ma non è troppo difficile.

Quindi puoi trovare qualsiasi numero di Fibonacci usando questa funzione (in 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); } 

Ho provato questo per il numero 25.000 di Fibonacci e simili.

Ecco la mia versione ricorsiva che ricorre log (n) volte. Penso che sia più facile da leggere nella forma ricorsiva:

 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) 

Funziona perché puoi calcolare fib(n),fib(n-1) usando fib(n-1),fib(n-2) se n è dispari e se n è pari, puoi calcolare fib(n),fib(n-1) usando fib(n/2),fib(n/2-1) .

Il caso base e il caso strano sono semplici. Per ricavare il caso pari, iniziare con a, b, c come valori consecutivi di fibonacci (ad esempio, 8,5,3) e scriverli in una matrice, con a = b + c. Avviso:

 [1 1] * [ab] = [a+ba] [1 0] [bc] [ab] 

Da ciò, vediamo che una matrice dei primi tre numeri di Fibonacci, volte a una matrice di tre numeri di Fibonacci consecutivi, è uguale alla seguente. Quindi sappiamo che:

  n [1 1] = [fib(n+1) fib(n) ] [1 0] [fib(n) fib(n-1)] 

Così:

  2n 2 [1 1] = [fib(n+1) fib(n) ] [1 0] [fib(n) fib(n-1)] 

La semplificazione della parte destra porta alla cassa uniforms.

usando 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 

vedi algoritmo divide et impera qui

Il collegamento ha uno pseudocodice per l’esponenziazione della matrice menzionata in alcune delle altre risposte a questa domanda.

L’aritmetica a punti fissi è inaccurata. Il codice C # di Jason fornisce una risposta errata per n = 71 (308061521170130 anziché 308061521170129) e oltre.

Per una risposta corretta, utilizzare un sistema di algebra computazionale. Sympy è una tale libreria per Python. C’è una console intertriggers su http://live.sympy.org/ . Copia e incolla questa funzione

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

Quindi calcola

 >>> f(10) 55 >>> f(71) 308061521170129 

Ti potrebbe piacere provare a ispezionare phi .

È ansible utilizzare la strana equazione di rooty quadrata per ottenere una risposta esatta. Il motivo è che $ \ sqrt (5) $ cade alla fine, devi solo tenere traccia dei coefficienti con il tuo formato di moltiplicazione.

 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 

Ecco un one-liner che calcola F (n), usando numeri interi di dimensione O (n), in operazioni aritmetiche O (log n):

 for i in range(1, 50): print(i, pow(2< 

L'uso di numeri interi di dimensione O (n) è ragionevole, poiché è paragonabile alla dimensione della risposta.

Per capire questo, sia phi il rapporto aureo (la soluzione più grande per x ^ 2 = x + 1) e F (n) sia il n ° numero di Fibonacci, dove F (0) = 0, F (1) = F (2) = 1

Ora, phi ^ n = F (n-1) + F (n) phi.

Prova per induzione: phi ^ 1 = 0 + 1 * phi = F (0) + F (1) phi. E se phi ^ n = F (n-1) + F (n) phi, allora phi ^ (n + 1) = F (n-1) phi + F (n) phi ^ 2 = F (n-1) phi + F (n) (phi + 1) = F (n) + (F (n) + F (n-1)) phi = F (n) + F (n + 1) phi. L'unico passaggio difficile in questo calcolo è quello che sostituisce phi ^ 2 di (1 + phi), che segue perché phi è la sezione aurea.

Anche i numeri della forma (a + b * phi), dove a, b sono numeri interi sono chiusi in moltiplicazione.

Dimostrazione: (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.

Usando questa rappresentazione, si può calcolare phi ^ n in O (log n) operazioni in interi usando l'esponenziazione quadrando. Il risultato sarà F (n-1) + F (n) phi, da cui si può leggere il n ° numero di Fibonacci.

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

Nota che la maggior parte di questo codice è una funzione standard di esponenziazione per quadratura.

Per arrivare al liner che inizia questa risposta, si può notare che rappresentando phi da un numero intero abbastanza grande X , si può eseguire (a+b*phi)(c+d*phi) come operazione intera (a+bX)(c+dX) modulo (X^2-X-1) . Quindi la funzione pow può essere sostituita dalla funzione pow standard di Python (che include opportunamente un terzo argomento z che calcola il risultato modulo z X scelta è 2< .