1 ]=> (define (F n) (Fs n 1 0))
(define (Fs n s c)
(if (= n 0)
c
(Fs (- n 1) (+ s c) s)))
;Value: f
1 ]=>
;Value: fs
1 ]=> (F 3000)
41061588630797126033356837871926710522012510863736925240888543092690
55842741134037313304916608500445608300368357069422745885693621454765
02674373045446852160486606292497360503469773453733196887405847255290
08204908690751262205905454219588975803110922267084927479385953913331
83712447955431476110732762400667379340851917318109932017067768389347
66764778739502174470268627820918553842225858306408301661862900358266
85723821023580250435195147299791967652400478423637645334726836415264
83462458405732142414199379172429186026398100978669423920154046201538
18671425739835074851396421139982713640679581178458198658692285968043
243656709796000
Bc
La calculatrice bc accepte le programme équivalent suivant :
define fib(n) {
auto a, b, c, i;
a=0; b=1;
for(i=0;i<n;i++) {
c=a+b; a=b; b=c;
}
return(a);
}
fib(3000);
quit;
Le second programme qui suit (calcul par dichotomie) est bien plus rapide lorsque n devient grand. Les
formules utilisées sont, suivant que n est pair ou impair
F(2p)= (2×F(p+1)-F(p))×F(p), F(2p+1)= F2(p+1)+F2(p)
scale=0;
define fib(n) {
auto a, b;
if(n<3) {
if(n==0) return 0;
return 1;
}
a = fib(n/2); b = fib(n/2+1)
if(n%2) return b^2 + a^2;
return (2*b-a)*a ;
}
fib(3000);
quit;
Javascript rapide, en ligne
Calculez en quelques secondes seulement, les centaines ou milliers de chiffres de Fn lorsque n est grand (n=1000 ou n=10000 ou même plus).
L'application javascript utilise la propriété : Pour 0<= k<= n-2, F(n)=F(k+2)*F(n-k-1)+F(k+1)*F(n-k-2) qui permet de ne calculer qu'une faible partie des nombres de Fibonacci qui précèdent F(n).
En prenant k+1=50, seuls sont calculés deux nombres de Fibonacci consécutifs toutes les 50 positions.
Le programme est très simple à écrire et est environ 25 fois plus rapide qu'en utilisant F(n)=F(n-1)+F(n-2).
Algorithmes rapides
PARI/GP
Pour concevoir des algorithmes encore plus rapides, pour de très grandes valeurs de n, consulter par exemple ma page de liens sur les algorithmes.
Si vous avez installé Pari/Gp, vous pouvez essayer de calculer : fibonacci(10^6) et ses 208988 chiffres.
Vous pouvez aussi construire votre propre fonction comme dans les deux exemples ci-dessous :
La session suivante calcule la puissance n-ième A = M^n =[F(n+1),F(n);F(n),F(n-1)] de la matrice carrée M=[1,1;1,0] pour obtenir F(n).
aven:~/fibonacci\> gp -q
? fib(n) =
{
local(A); A = [1,1;1,0]^n;
A[1,2];
}
? fib(100)
354224848179261915075
?
Avec le programme suivant vous pourrez essayer de rivaliser (en rapidité) avec la fonction 'fibonacci()'
préprogrammée dans GP/PARI.
Pour un premier contact, écrivez-moi en utilisant ce formulaire.
Les correspondances suivantes pourront se faire par messagerie électronique. Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès maintenant et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige votre travail ou le corrige de cette communication et lui montrer les documents fournis.
