nième numéro de fibonacci dans le temps sublinéaire
https://stackoverflow.com/questions/1525521
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Y at-il algorithme pour calculer le nombre de n-ième fibonacci dans le temps sous linéaire?
La solution
Le nombre nth Fibonacci est donné par
f(n) = Floor(phi^n / sqrt(5) + 1/2)
où
phi = (1 + sqrt(5)) / 2
En supposant que les opérations mathématiques primitives (+, -, * et /) sont O(1) vous pouvez utiliser ce résultat pour calculer le nombre nth de Fibonacci dans le temps de O(log n) (O(log n) en raison de la exponentiation dans 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);
}
Autres conseils
À la suite de la référence de Pillsy à Matrice exponentiation, de telle sorte que pour la matrice
M = [1 1]
[1 0]
puis
fib(n) = Mn1,2
Raising matrices à des puissances en utilisant la multiplication répétée n'est pas très efficace.
Deux approches de matrice exponentiation sont diviser pour régner qui donne M n O ( ln n ) étapes ou décomposition en valeurs propres qui est constante de temps, mais peut introduire des erreurs en raison de la précision en virgule flottante limité.
Si vous voulez une approche valeur exacte supérieure à la précision de votre implémentation en virgule flottante, vous devez utiliser le O (ln n) en fonction de cette relation:
Mn = (Mn/2)2 if n even = M·Mn-1 if n is odd
La décomposition en valeurs propres sur M trouve deux matrices U et Λ de telle sorte que Λ est diagonale et
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
Élever une matrice diagonale Λ n ième puissance est une simple question de soulever chaque élément Λ n e, de sorte que cela donne un procédé de O (1) de collecte M n ième puissance. Cependant, les valeurs Λ ne sont pas susceptibles d'être des entiers, donc une erreur se produit.
Définir Λ pour notre matrice 2x2 comme
Λ = [ λ1 0 ] = [ 0 λ2 ]
Pour 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-Φ } where Φ = ( 1 + √5 ) / 2
Si vous avez lu la réponse de Jason, vous pouvez voir où cela va aller.
Résolution des vecteurs propres X 1 et X 2 :
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 ]
Ces vecteurs donnent U :
U = [ X1,1, X2,2 ]
[ X1,1, X2,2 ]
= [ Φ, 1-Φ ]
[ 1, 1 ]
Inverting U avec
A = [ a b ]
[ c d ]
=>
A-1 = ( 1 / |A| ) [ d -b ]
[ -c a ]
U -1 est donné par
U-1 = ( 1 / ( Φ - ( 1 - Φ ) ) [ 1 Φ-1 ]
[ -1 Φ ]
U-1 = ( √5 )-1 [ 1 Φ-1 ]
[ -1 Φ ]
test de cohérence:
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
Ainsi, le contrôle de la santé mentale tient.
Maintenant, nous avons tout ce que nous devons calculer M n 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
Ce qui est d'accord avec la formule donnée ailleurs.
Vous pouvez le déduire d'une relation de récurrence, mais dans le calcul de l'ingénierie et de la simulation du calcul des valeurs propres et vecteurs propres des grandes matrices est une activité importante, car elle donne la stabilité et les harmoniques des systèmes d'équations, ainsi que de permettre élever des matrices à haute pouvoirs efficacement.
Si vous voulez que le nombre exact (qui est un "bignum", plutôt que d'un int / flotteur), alors je crains que
Il est impossible!
Comme indiqué plus haut, la formule pour les nombres de Fibonacci est la suivante:
fib n = plancher (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
il est O ( n )
Étant donné que le résultat est de O ( n ), il ne peut pas être calculé en moins de O ( n ) temps.
Si vous voulez que les derniers chiffres de la réponse, il est alors possible de calculer en temps sous-linéaire en utilisant la méthode matrice exponentiation.
L'un des exercices de rel="noreferrer"> est à ce sujet, qui a la réponse décrit ici.
Dans le style impératif, le programme ressemblerait à quelque chose comme
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
Vous pouvez le faire par exponentiation une matrice d'entiers ainsi. Si vous avez la matrice
/ 1 1 \
M = | |
\ 1 0 /
alors (M^n)[1, 2] va être égal au nombre nth de Fibonacci, si [] est une matrice et ^ est l'indice matrice exponentiation. Pour une matrice de taille fixe, exponentiation à une puissance entière positive peut être fait en O (log n) de la même façon que pour les nombres réels.
EDIT: Bien sûr, selon le type de réponse que vous voulez, vous pourrez peut-être sortir avec un algorithme de temps constant. Comme les autres formules montrent, le nombre nth Fibonacci croît de façon exponentielle avec n. Même avec des entiers non signés 64 bits, vous aurez seulement besoin d'une table de consultation 94-entrée afin de couvrir toute la gamme.
DEUXIÈME EDIT: Faire la matrice exponentielle avec un eigendecomposition premier est exactement équivalent à la solution de JDunkerly ci-dessous. Les valeurs propres de cette matrice 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 ceux qui sont vraiment grands, 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 grands entiers. J'utilise la bibliothèque BigInteger de https://mattmccutchen.net/bigint/ .
Commencez par un tableau de numéros de fibonacci. Utilisez fibs [0] = 0, fibs [1] = 1, fibs [2] = 1, fibs [3] = 2, fibs [4] = 3, etc. Dans cet exemple, j'utiliser un tableau de la première 501 (en comptant 0). Vous pouvez trouver les 500 premiers non nuls nombres de Fibonacci ici: http://home.hiwaay.net /~jalison/Fib500.html . Il faut un petit montage pour le mettre dans le bon format, mais pas trop dur.
Ensuite, vous pouvez trouver un certain nombre de Fibonacci 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é cela pour le nombre de 25,000th Fibonacci et autres.
Voici ma version récursive récursif log (n) fois. Je pense qu'il 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)
Il fonctionne parce que vous pouvez calculer à l'aide fib(n),fib(n-1) fib(n-1),fib(n-2) si n est impair et si n est pair, vous pouvez calculer fib(n),fib(n-1) en utilisant fib(n/2),fib(n/2-1).
Le cas de base et le cas impair sont simples. Pour tirer le même cas, commencer par a, b, c que les valeurs de Fibonacci consécutifs (par exemple, 8,5,3) et les écrire dans une matrice, avec a = b + c. Avis:
[1 1] * [a b] = [a+b a]
[1 0] [b c] [a b]
De là, on voit qu'une matrice des trois premiers numéros de fibonacci, fois une matrice de trois numéros consécutifs de fibonacci, est égal à l'autre. Nous savons donc que:
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)]
Simplifier le côté droit mène à la même affaire.
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
En dehors de peaufinage par des approches mathématiques, un de la meilleure solution optimale (je crois) utilise un dictionnaire afin d'éviter des calculs répétitifs.
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))
Nous commençons avec le dictionnaire trivial (deux premières valeurs de la séquence de Fibonacci) et en ajoutant constamment des valeurs de Fibonacci au dictionnaire.
Il a fallu environ 0,7 secondes pour la première 100000 valeurs de Fibonacci (Intel Xeon E5-2680 CPU @ 2,70 GHz, 16 Go de RAM, OS bits de Windows 10-64)
voir diviser pour mieux régner algorithme ici
Le lien a pour la matrice pseudo-code exponentiation mentionné dans certaines des autres réponses à cette question.
arithmétique à virgule fixe est inexacte. C # Code de Jason donne réponse incorrecte pour n = 71 (308061521170130 au lieu de 308061521170129) et au-delà.
Pour toute réponse correcte, utilisez un système d'algèbre informatique. Sympy est une bibliothèque 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)
Calculer ensuite
>>> f(10)
55
>>> f(71)
308061521170129
Vous pouvez essayer d'inspecter phi.
Vous pouvez utiliser l'équation rooty carré étrange pour obtenir une réponse exacte. La raison en est que le $ \ sqrt (5) $ tombe à la fin, il vous suffit de garder une trace des 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 une seule ligne qui calcule F (n), en utilisant des nombres entiers de taille O (n), en O (log n) des opérations arithmétiques:
for i in range(1, 50):
print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))
En utilisant des nombres entiers de taille O (n) est raisonnable, puisque c'est comparable à la taille de la réponse.
Pour comprendre cela, laisser phi être le nombre d'or (le plus grand de solution de x ^ 2 = x + 1) et F (n) est le n-iè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, phi puis ^ (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 dans ce calcul est celle qui remplace phi ^ 2 par (1 + phi), qui suit car phi est le nombre d'or.
Aussi nombres de la forme (a + b * phi), où a, b sont des nombres entiers sont fermés pour la multiplication.
Preuve: (p0 + p1 * phi) (q0 + q1 * phi) = p0q0 + (+ p0q1 q1p0) + phi phi p1q1 * ^ 2 = p0q0 + (+ p0q1 q1p0) + phi p1q1 * (phi + 1) = (p0q0 + p1q1) + (P0q1 + q1p0 + p1q1) * phi.
L'utilisation de cette représentation, on peut calculer des opérations entières phi ^ n en O (log n) en utilisant exponentiation par élévation au carré. Le résultat sera F (n-1) + F (n) phi, à partir de laquelle on peut lire le n-ième nombre 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 norme exponentiation par élévation au carré fonction.
Pour accéder à la seule ligne qui commence cette réponse, on peut noter que représentant phi par un assez grand nombre entier X, on peut effectuer (a+b*phi)(c+d*phi) comme (a+bX)(c+dX) modulo (X^2-X-1) de fonctionnement entier. Ensuite, la fonction de pow peut être remplacé par la fonction standard python pow (qui comprend commodément un troisième argument z qui calcule le résultat modulo z. Le X choisi est 2<<i.
