nième nombre de fibonacci en temps sublinéaire

Existe-t-il un algorithme pour calculer le nième nombre de fibonacci en temps sub linéaire?

Le numéro de Fibonacci est donné par

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

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

En supposant que les opérations mathématiques primitives ( + , - , * et / ) soient O(1) vous pouvez utiliser ce résultat pour calculer le n ième nombre de Fibonacci en temps O(log n) ( O(log n) raison de l’exponentiation en la formule).

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

Suite à la référence de Pillsy à l’exponentiation de la masortingce, telle que pour la masortingce

 M = [1 1] 
     [dix] 

puis

  fib ( n ) = M 1,2 

Élever des masortingces à des puissances en utilisant une multiplication répétée n’est pas très efficace.

Deux approches de l’exponentiation de la masortingce sont la division et la conquête qui donnent M n en O ( ln n ) étapes ou la décomposition en valeurs propres qui est un temps constant, mais peuvent introduire des erreurs dues à une précision limitée en virgule flottante.

Si vous voulez une valeur exacte supérieure à la précision de votre implémentation en virgule flottante, vous devez utiliser l’approche O (ln n) basée sur cette relation:

  M n = ( M n / 2 ) 2 si n même
    = M · M n -1 si n est impair

La décomposition en valeurs propres sur M trouve deux masortingces U et that telles que Λ est diagonale et

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

Élever la masortingce diagonale power à la n- ième puissance consiste simplement à élever chaque élément de Λ au n- ième, ce qui donne une méthode O (1) pour élever M à la n- ième puissance. Cependant, les valeurs dans Λ ne sont probablement pas des entiers, donc une erreur se produira.

Définir Λ pour notre masortingce 2×2 comme

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

Pour trouver chaque λ , nous résolvons

  |  M - λ I |  = 0 

qui donne

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

 λ² - λ - 1 = 0

en utilisant la formule quadratique

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

Si vous avez lu la réponse de Jason, vous pouvez voir où cela va aller.

Résolution pour les vecteurs propres X 1 et X 2 :

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

Ces vecteurs donnent U :

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

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

Inverser U en utilisant

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

alors U -1 est donné par

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

Verification sanitaire:

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

 Soit Ψ = 1-Φ, l'autre valeur propre

 comme Φ est une racine de λ²-λ-1 = 0 
 so -ΨΦ = Φ²-Φ = 1
 et Ψ + Φ = 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]    
          [ dix ]

        = [1 1] 
          [ dix ]

        = M 

Donc, le contrôle de santé mentale tient.

Maintenant, nous avons tout ce dont nous avons besoin pour calculer M 1,2 :

 M n = U Λ n U -1
    = (√5) -1 [Φ Ψ].  [0 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 ] comme ΨΦ = -1

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

alors

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

Ce qui correspond à la formule donnée ailleurs.

Vous pouvez le déduire d’une relation de récurrence, mais en informatique et en simulation, calculer les valeurs propres et les vecteurs propres de grandes masortingces est une activité importante, car elle donne stabilité et harmoniques de systèmes d’équations.

Si vous voulez le nombre exact (qui est un “bignum”, plutôt qu’un int / float), alors je crains que

C’est impossible!

Comme indiqué ci-dessus, la formule pour les nombres de Fibonacci est la suivante:

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

fib n ~ = phi n / √5

Combien de chiffres est 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

c’est O ( n )

Comme le résultat demandé est de O ( n ), il ne peut pas être calculé en moins de O ( n ).

Si vous ne voulez que les chiffres inférieurs de la réponse, il est alors possible de calculer le temps sous-linéaire en utilisant la méthode d’exponentiation de la masortingce.

Un des exercices de SICP concerne ce sujet, qui a la réponse décrite ici.

Dans le style impératif, le programme ressemblerait à quelque chose

 Fonction Fib ( comte )
     un ← 1
     b ← 0
     p ← 0
     q ← 1

     Alors que compte > 0 Do
         Si pair ( compte ) alors
              p ← p² + q ²
              q ← 2 pq + q ²
              countcount ÷ 2
         Autre
              abq + aq + ap
              bbp + aq
              countcount - 1
         Fin si
     Fin tant que

     Retour b
 Fonction de fin

Vous pouvez le faire en exposant également une masortingce d’entiers. Si vous avez la masortingce

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

alors (M^n)[1, 2] va être égal au n ième nombre de Fibonacci, si [] est un indice masortingciel et ^ est une exponentiation masortingcielle. Pour une masortingce de taille fixe, une exponentiation à une puissance intégrale positive peut être effectuée dans le temps O (log n) de la même manière qu’avec les nombres réels.

EDIT: Bien sûr, selon le type de réponse que vous souhaitez, vous pourrez peut-être vous en sortir avec un algorithme à temps constant. Comme le montrent les autres formules, le nombre de Fibonacci augmente de façon exponentielle avec n . Même avec des entiers non signés de 64 bits, vous n’aurez besoin que d’une table de recherche à 94 entrées pour couvrir toute la plage.

SECOND EDIT: Faire la masortingce exponentielle avec une eigendecomposition d’abord est exactement équivalent à la solution de JDunkerly ci-dessous. Les valeurs propres de cette masortingce sont les (1 + sqrt(5))/2 et (1 - sqrt(5))/2 .

Wikipedia a une solution de forme fermée http://en.wikipedia.org/wiki/Fibonacci_number

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

Pour les très gros, cette fonction récursive fonctionne. Il utilise les équations suivantes:

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

Vous avez besoin d’une bibliothèque qui vous permet de travailler avec de gros entiers. J’utilise la bibliothèque BigInteger depuis https://mattmccutchen.net/bigint/ .

Commencez avec un tableau de nombres de fibonacci. Utiliser les fibs [0] = 0, fibs [1] = 1, fibs [2] = 1, fibs [3] = 2, fibs [4] = 3, etc. Dans cet exemple, j’utilise un tableau des 501 premiers (en comptant 0). Vous pouvez trouver les 500 premiers numéros de Fibonacci non nuls ici: http://home.hiwaay.net/~jalison/Fib500.html . Il faut un petit assembly pour le mettre dans le bon format, mais ce n’est pas trop difficile.

Vous pouvez ensuite trouver n’importe quel nombre de Fibonacci en utilisant cette fonction (en 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); } 

Je l'ai testé pour le 25 000ème numéro de Fibonacci et autres.

Voici ma version récursive qui récidive les temps de log (n). Je pense que c’est plus facile à lire sous la forme récursive:

 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) 

Cela fonctionne parce que vous pouvez calculer fib(n),fib(n-1) utilisant fib(n-1),fib(n-2) si n est impair et si n est pair, vous pouvez calculer fib(n),fib(n-1) utilisant fib(n/2),fib(n/2-1) .

Le cas de base et les cas impairs sont simples. Pour calculer le même cas, commencez par a, b, c en tant que valeurs consécutives de fibonacci (par exemple, 8,5,3) et écrivez-les dans une masortingce, avec a = b + c. Remarquer:

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

De cela, nous voyons qu'une masortingce des trois premiers nombres de fibonacci, fois une masortingce de trois nombres de fibonacci consécutifs, est égale à la suivante. Nous soaps donc que:

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

Alors:

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

Simplifier le côté droit conduit au même cas.

en utilisant 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 

voir diviser et conquérir l’algorithme ici

Le lien a un pseudo-code pour l’exponentiation de la masortingce mentionnée dans certaines des autres réponses à cette question.

L’arithmétique à virgule fixe est inexacte. Le code C # de Jason donne une réponse incorrecte pour n = 71 (308061521170130 au lieu de 308061521170129) et au-delà.

Pour une réponse correcte, utilisez un système de calcul formel. Sympy est une telle bibliothèque pour Python. Il y a une console interactive à http://live.sympy.org/ . Copiez et collez cette fonction

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

Puis calculer

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

Vous pouvez essayer d’inspecter phi .

Vous pouvez utiliser l’équation de racine carrée étrange pour obtenir une réponse exacte. La raison en est que $ \ sqrt (5) $ tombe à la fin, il vous suffit de suivre les coefficients avec votre propre format de multiplication.

 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 

Voici un one-liner qui calcule F (n), en utilisant des entiers de taille O (n), dans les opérations arithmétiques O (log n):

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

Utiliser des entiers de taille O (n) est raisonnable, car cela est comparable à la taille de la réponse.

Pour comprendre cela, que phi soit le nombre d'or (la plus grande solution à x ^ 2 = x + 1) et F (n) soit le nième nombre de Fibonacci, où F (0) = 0, F (1) = F (2) = 1

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

Preuve par induction: phi ^ 1 = 0 + 1 * phi = F (0) + F (1) phi. Et si phi ^ n = F (n-1) + F (n) phi, alors 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. La seule étape délicate de ce calcul est celle qui remplace phi ^ 2 par (1 + phi), car phi est le nombre d'or.

Les nombres de la forme (a + b * phi), où a, b sont des entiers sont fermés sous la multiplication.

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

En utilisant cette représentation, on peut calculer phi ^ n en O (log n) des opérations entières en utilisant une exponentiation par la mise au carré. Le résultat sera F (n-1) + F (n) phi, à partir duquel on peut lire le numéro de 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]) 

Notez que la majorité de ce code est une fonction standard d'exposant par carré.

Pour arriver au one-liner qui lance cette réponse, on peut noter que représenter phi par un entier suffisamment grand X , on peut effectuer (a+b*phi)(c+d*phi) comme opération entière (a+bX)(c+dX) modulo (X^2-X-1) . Ensuite, la fonction pow peut être remplacée par la fonction standard python pow (qui inclut commodément un troisième argument z qui calcule le résultat modulo z . Le X choisi est 2< .