Accueil > Mots > Suites > Fibonacci > Fibonacci 2

Suite de Fibonacci
Calculs et Programmes

précédentesommairesuivante
Index général des suites


Programmes

Lisp ou Scheme

Dans le langage Scheme d'après le livre du langage :  Structure et interprétation des programmes informatiques  de Harold Abelson/ Gerald Jay Sussman avec Julie Sussman 
        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).

Fibonacci
n =         



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. 
      mfib(n) =
      {
          local(A,B);
          A=[1,1;1,0];
          if(n==1,B=A, if(n%2==0, B=mfib(n/2)^2, B=mfib(n-1)*A));
          B
      }
      fib(n) = 
      {
         local(U);U = mfib(n); 
         U[1,2]
      }
      fib(1000000)

Liens, références, documentations, compléments

analysis of algorithms David Eppstein
Fun with Fibonacci
Fibonacci numbers in many languages by by Sergei Zubkov
Fibonacci Number Prolog Colin Barker


précédentesommairesuivante


















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014