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

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 ?

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.

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

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

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.

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

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"...

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.

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

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...

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.

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 !

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.

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

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 ?

Up !

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...

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  ?

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 F_n,F_n+1.
si par exemple n=2p , f(n/2) renvoie le couple a,b=F_p,F_p+1 donc F_n,F_n+1=a*(2*b-a),a^2+b^2.

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

Il suffit d'utiliser evalf.
Après avoir défini la fonction f:
evalf(f(1000000)[1]);
affiche: .1953282129 10²⁰⁸⁹⁸⁸.
F_1000000 a donc 208988 chiffres.

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

Bonjour

Il y a aussi

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

354224848179261915075

>