Inscription / Connexion Nouveau Sujet
Niveau logiciels
Partager :

Calculer les nombres de Fibonacci avec Maple

Posté par
fade2black
11-11-08 à 18:54

Bonjour !

Je suis absolument nul en Maple, mais j'aimerais créer un petit algorithme qui calculerait les nombres de Fibonacci. En réalité, j'en ai déjà fait un, mais j'aimerais en créer un autre, en éséprant qu'il soit plus rapide, qui utiliserait les relations suivantes :

F2n = 2 * Fn-1 * Fn

F2n+1 = Fn+1² + Fn²

J'aurais notamment besoin de la traduction en language maple de "si n est pair, alors..."

Merci de votre aide !

Posté par
Narhm
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 19:25

Bonjour,

Pour savoir si n est pair, tu pourrais tout simplement diviser n par 2 et vérifier si c'est égale à la partie entière de (n/2) [floor(n/2);]. Ça pourrait être une première idée.
Une deuxième qui est plus directe consiste à utiliser le reste de la division euclidienne de n par 2.
On l'écrit : [irem(n,2);] ca te retourne le reste , tout simplement.

En résumé, tu peux faire comme ceci :
if n/2=floor(n/2) then
   #code pour n pair
else                                
   #code pour n impair
fi;

ou

if irem(n,2)=0 then
   #code pour n pair
else
   #code pour n impair
fi;

Bye

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 19:59

Merci de ta réponse, Narhm,

j'ai essayé de taper ce que tu m'as dit, mais comme je l'ai signalé, je suis vraiment nul en Maple donc je ne sais pas comment le rédiger en détail.
Voilà ce que j'ai tapé :

fibo:=proc(n);
> if n<1 then n;
> if n/2=floor(n/2) then
>    fibo(n):=2*fibonacci3(n/2-1)*fibonacci3(n/2);
> else                                
>    fibo(n):=(fibonacci3((n+3)/2)^2+(fibonacci3((n+1)/2))^2
> fi;
> fi;
> RETURN(fibo(n));
> end;

Et ça ne marche pas ; où ai-je commis une erreur ?

Posté par
1 Schumi 1
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 20:08

Salut

C'est juste qu'il ne sait pas qui est "fibonacci". Si tu fais une procédure récursive (ce qui est le cas) vaut mieux appellé la bonne fonction.

Posté par
1 Schumi 1
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 20:09

Un "elif" serait mieux pour le 2ème "if". Je suis pas sûr qu'il accepte cela aussi.

Posté par
Narhm
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 20:10

Oui je me demande pas plutot si c'est pas à cause de tes "if" et "fi" qui trainent que ca bug.

Posté par
Narhm
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 20:13

Sinon, essaie comme ceci:

fibo:=proc(n);
>local var;
> if n<1 then
>   var:=n;
> fi;
> if irem(n,2)=0 then
>    p:=2*fibonacci3(n/2-1)*fibonacci3(n/2):
> else                                
>    p:=(fibonacci3((n+3)/2)^2+(fibonacci3((n+1)/2))^2:
> fi;
> return p;
> end;

Il y a aussi un probleme quand tu définies fibo(n):= ...
Autant proceder avec des variables locales je pense.
Apres je suis pas du tout expert, alors je peux me tromper, mais essaie déjà avec ca.

Posté par
Narhm
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 20:14

Petite erreur... remplace le 'p' par 'var'
Désolé

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 20:40

Pardon,
"fibonacci3" c'est une autre procédure pour calculer les nombres de fibonacci.
Quand je tape ta procédure, il me dit "Error, reserved word `local` unexpected"...

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 20:45

En fait j'ai déjà une procédure pour calculer les nombres de Fibonacci ; la voilà :

fibonacci3:=proc(n)
> local i,f1,f2,f;
> f1:=0; f2:=1;
> for i from 2 to n do
> f:=f1+f2;
> f1:=f2;
> f2:=f; od;
> if n=0 then 0;
> else RETURN(f2); fi;
> end;

Et là, je veux l'améliorer grâce aux identités de mon premier post.

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 20:58

Ah ca marche maintenant mais ca trouve pas les bons nombres, j'ai du me tromper dans les identités ; je vérifie.

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 21:02

Voilà donc le programme :

fibo:=proc(n)
> local var;
>  if n<2 then
>    var:=n;
>  fi;
>  if irem(n,2)=0 then
>     var:=2*fibonacci3(n/2-1)*fibonacci3(n/2);
>  else                                
>     var:=(fibonacci3((n+3)/2)^2+(fibonacci3((n+1)/2)))^2;
>  fi;
>  return var;
>  end;

Le problème, déjà, c'est qu'il me donne fibo(1)=4...

Posté par
Narhm
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 21:29

Alors en faite je viens de voir,
Ta formule n'est pas tout fait bonne non pour les n pairs ou impaires ?
J'ai fait à peu pres ce que je pensais que tu voulais en corrigeant les formules :

#Debut
fibo := proc (n)
local i, f1, f2, f;
f1 := 0; f2 := 1;
for i from 2 to n do
f := f1+f2;
f1 := f2;
f2 := f;
od;
if n = 0 then
  f2 := 0;
fi;
return f2;
end;
#Fin


Et le deuxième :
#Debut
fibonacci:= proc (n)
local var;
if n = 0 then
  var := 0;
fi;
if irem(n, 2) = 0 then
  var := 2*fibo((1/2)*n-1)*fibo((1/2)*n)+fibo((1/2)*n)^2;
else
  var := fibo((1/2)*n+1/2)^2+fibo((1/2)*n-1/2)^2;
fi;
return var;
end;

Voilà. Moi ca me retourne correctement les nombres de fibonacci.

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 23:00

Ok, merci beaucoup !
Ca marche, et ça marche bien.
Pour info, cet algorithme est plus rapide que le précédent. Je mets 116 secondes pour calculer le millionième nombre de Fibonacci, contre 150 avec le précédent algorithme.
Bye bye !

Posté par
Narhm
re : Calculer les nombres de Fibonacci avec Maple 11-11-08 à 23:22

J'ai effectivement les meme temps de calcul.
En revanche, tu peux pousser encore plus loin le truc.
La suite de Fibonacci peut s'écrire encore plus simplement de manière récursive sans distingué n pair ou impair.

\large F_n = F_{E(\fr{n}{2})+1}^2 \ - \ (-1)^nF_{E(\fr{n-1}{2})}^2 où E désigne la partie entière.
J'ai calculé le millionième et j'ai trouvé un peu mions de 80s de calcul.

Voilà, Bye

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 12-11-08 à 00:45

Mais on pourrait aussi améliorer l'algorithme précédent non ?
Parce que là, par exemple, si on veut calculer F100, notre algorithme va l'exprimer en fonction de F50 et F49, et il va calculer F50 et F49 avec le vieil algorithme (celui que j'ai appelé fibonacci3). On ne pourrait pas faire un genre de boucle, pour qu'il se serve de nos identités jusqu'au bout ?
Par exemple pour F100, il voit qu'on peut l'exprimer en fonction de F50 et F49, ensuite il voit qu'on peut exprimer F50 en fonction de F25 et F24 etc...
C'est possible de faire quelque chose du genre ?

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 12-11-08 à 20:27

Up !

Posté par
1 Schumi 1
re : Calculer les nombres de Fibonacci avec Maple 12-11-08 à 20:30

Salut

Si tu travailles sur une bonne version de Maple il y a "option remember:" qui fait chuter le temps de calcul mais cette commande n'est pas sur toutes les versions...

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 12-11-08 à 21:06

Salut Schumi,
oui j'ai l'option remember, mais je ne suis pas sûr que ce soit ça dont j'ai besoin. Je rappelle la procédure :

fibonacci3:=proc(n)
local i,f1,f2,f;
f1:=0; f2:=1;
for i from 2 to n do
f:=f1+f2;
f1:=f2;
f2:=f; od;
if n=0 then 0;
else RETURN(f2); fi;
end;

fibonacci4:=proc(n)
local var;
if n=0 then
  var := 0;
fi;
if irem(n,2)=0 then
  var:=2*fibonacci3((1/2)*n-1)*fibonacci3((1/2)*n)+fibonacci3((1/2)*n)^2;
else
  var:=fibonacci3((1/2)*n+1/2)^2+fibonacci3((1/2)*n-1/2)^2;
fi;
return var;
end;


Dans notre procédure fibonacci4, on utilise qu'une seule fois la proprieté qui donne F2n ou F2n+1 en fonction de nombres de Fibonacci plus petit. Pour F100 par exemple, l'algorithme trouve que F100 s'exprime en fonction de F50 et F49, et là il va CALCULER F50 et F49 DIRECTEMENT, grâce à fibonacci3. Moi j'aimerais qu'il utilise notre proprieté en boucle, c'est à dire qu'au lieu de calculer directement F50 et F49 à l'aide de fibonacci3, il commence par exprimer F50 en fonction de F25 et F24 (toujours avec la même proprieté), et F49 en fonction de F24 et F23... Tu vois ce que je veux dire  ?

Posté par
jandri Correcteur
re : Calculer les nombres de Fibonacci avec Maple 14-11-08 à 18:37

Bonjour,

Voici une procédure récursive (en Maple) qui calcule F1000000 (nombre à 200000 chiffres) en environ une seconde:

f:=proc(n)
local a,b:
if n = 0 then
0,1
elif irem(n,2)=0 then
a,b:=f(n/2): a*(2*b-a),a^2+b^2
else
a,b:=f((n-1)/2): a^2+b^2,b*(2*a+b)
fi end;

time(f(1000000)[1]);
1.453

explication: f renvoie le couple Fn,Fn+1.
si par exemple n=2p , f(n/2) renvoie le couple a,b=Fp,Fp+1 donc Fn,Fn+1=a*(2*b-a),a^2+b^2.

Posté par
fade2black
re : Calculer les nombres de Fibonacci avec Maple 15-11-08 à 21:51

Merci pour cet algorithme !
Quelle est la commande de Maple qui nous donne le nombre de chiffres d'un nombre ?

Posté par
jandri Correcteur
re : Calculer les nombres de Fibonacci avec Maple 16-11-08 à 23:07

Il suffit d'utiliser evalf.
Après avoir défini la fonction f:
evalf(f(1000000)[1]);
affiche: .1953282129 10208988.
F1000000 a donc 208988 chiffres.

Posté par
tringlarido
re : Calculer les nombres de Fibonacci avec Maple 17-11-08 à 00:28

python gagne en concision avec seulement quatre lignes :

1) récursive

def fibo(n):
    if n == 0 : return 0
    return fibo(n-1)+fibo(n-2)



2) linéaire

def fibo(n):
    u,v=0,1
    for i in range(n) : u,v=v,u+v
    return v

Posté par
frenicle
re : Calculer les nombres de Fibonacci avec Maple 17-11-08 à 11:22

Bonjour

Il y a aussi

> with(combinat, fibonacci):
> fibonacci(100);

354224848179261915075

>

Citation :
The method used to compute F(n) is, however, based on the following identity: Let A be the two by two matrix [[1, 1], [1, 0]]. Observe that [ F(n+1), F(n) ] = A [ F(n), F(n-1) ] Thus F(n) can be computed quickly (in time O(log(n)^3) instead of O(n^2)) by computing A^n using binary powering.




Cordialement
Frenicle

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !