Pour FIbonacci, on calcule une expression explicite des termes de la suite par résolution de l'équation caractéristique qui est : X^2-X-1=0.
On trouve deux racines, dont une seule (qui s'avère être le nombre d'or) est plus grande que 1 en valeur absolue, et on a donc un équivalent de la forme : x_n ~ a*phi^n (où \phi=(1+\sqrt(5))/2 est le nombre d'or).
On déduit donc la taille des termes de la suite en passant au log : taille(x_n) = n*ln(\phi)
Et donc le calcul de x_n à partir de x_{n-1} et x_{n-2} est en : max(taille(x_{n-1}),taille(x_{n-2})) = taille(x_{n-1}) = (n-1)*ln(\phi)
Et finalement, le calcul de x_n a un coût en : \sum_{k=0}^{n-1} k*ln(\phi) = n(n-1)/2 * ln(\phi) = O(n^2)
1/4
Modérateur : xcasadmin
Re: 1/4
En complément de la solution de Thomas pour Fibonacci, en voici une plus rapide utilisant les flottants multi-précision et à nouveau l'algorithme de la puissance rapide.
La précision des flottants qui sera nécessaire (nombre de chiffres significatifs de la mantisse) va etre proportionnelle à n. Si on utilise la relation de récurrence, on a aussi un cout en O(n^2).
Mais on peut utiliser la formule explicite donnant F(n) sous la forme C*((1+sqrt(5))/2)^n+D*((1-sqrt(5))/2)^n.
Pour trouver les valeurs explicites des constantes C et D, vous pouvez utiliser la commande rsolve
Il suffit ensuite de calculer en approché avec une précision suffisante pour obtenir le bon résultat en arrondissant le flottant à l'entier le plus proche. Et on peut appliquer l'algorithme de la puissance rapide pour calculer (1+sqrt(5))/2)^n avec des flottants multi-précision (l'autre terme de la somme est négligeable pour n grand). Pour n grand, le produit de deux flottants avec une précision proportionnelle à n est en O(n*ln(n)), le nombre d'étapes en O(ln(n)) donc le cout en O(n*ln(n)^2). Mais la constante cachée dans le O est grande, il faut des valeurs de n plus grandes qu'un million pour que cette méthode devienne plus rapide!
Session d'illustration: https://www-fourier.univ-grenoble-alpes ... g/fibo.xws, dont voici le détail:
programme pour Fibonacci avec des additions d'entiers (en syntaxe Xcas et Python)
Fibonacci avec puissance rapide de flottants multi-précision
On teste
(fibo est plus rapide que fib)
(a peu pres la meme vitesse)
Si vous avez la patience, essayez avec 4*10^6, fib devient plus rapide que fibo (sur ma machine, 50s pour fib et 100 pour fibo).
La précision des flottants qui sera nécessaire (nombre de chiffres significatifs de la mantisse) va etre proportionnelle à n. Si on utilise la relation de récurrence, on a aussi un cout en O(n^2).
Mais on peut utiliser la formule explicite donnant F(n) sous la forme C*((1+sqrt(5))/2)^n+D*((1-sqrt(5))/2)^n.
Pour trouver les valeurs explicites des constantes C et D, vous pouvez utiliser la commande rsolve
Code : Tout sélectionner
[Fn]:=rsolve(F(n+2)=F(n)+F(n+1),F(n),[F(0)=1,F(1)=1])
Session d'illustration: https://www-fourier.univ-grenoble-alpes ... g/fibo.xws, dont voici le détail:
programme pour Fibonacci avec des additions d'entiers (en syntaxe Xcas et Python)
Code : Tout sélectionner
fonction fibo(n) // nombre de Fibonacci par la methode la plus simple en O(n^2)
local k,f;
f:=1,1;
pour k de 2 jusque n faire
f:=f[1],f[0]+f[1];
fpour;
retourne f[1];
ffonction:;
Code : Tout sélectionner
def fibo(n):
if n<2: return 1
a,b=1,1
for j in range(n-1):
a,b=a+b,a
return a
Code : Tout sélectionner
fonction fib(n)
// en utilisant la puissance rapide et la multiprecision, asymptotiquement en O(n*ln(n)^2)
local k,f,a;
// nombre de chiffres necessaires et marge de securite
k:=ceil(n*log10((sqrt(5)/2+.5))+log(n)/log(2)*3);
// puissance rapide iterative de sqrt(5)/2+1/2
a:=sqrt(evalf(5,k))/2+1/2;
f:=1;
tantque n>0 faire
si irem(n,2)=1 alors f:=f*a; fsi;
a:=a*a;
n:=iquo(n,2);
ftantque;
retourne round(f*(sqrt(5)+5)/10);
ffonction:;
Code : Tout sélectionner
n:=10^6;time(f:=fib(n));time(g:=fibo(n)); f-g
Code : Tout sélectionner
n:=2*10^6;time(f:=fib(n));time(g:=fibo(n)); f-g
Si vous avez la patience, essayez avec 4*10^6, fib devient plus rapide que fibo (sur ma machine, 50s pour fib et 100 pour fibo).