Fibonnaci à complexité logaritmique

slt Kzanadeus , je veut savoir est ce que cette solution à complexité logarithmique?
F:=proc(n) option remember;
local m;
if n=0 then 0
elif n=1 then 1
else
m:=iquo(n,2):
if n mod 2 = 0 then F(m)^2+2*F(m-1)*F(m)
else F(m)^2+F(m+1)^2 fi:
fi:
end:

Bonjour,
je veut savoir un algorithme de calcul d'une suite de Fibonacci mais àa complexité logarithmique ( O(log(n)) et la méthode consiste à le suivant : (parexemple je veut calculer F(62) ) alors : je calcul

-------------- 1er itération ------------------>2em itération-------------> 3em itération-----------> dernière itération
F(31)F(30)------------------> F(15)F(14)------------------>F(7)F(6)---------------------->F(3)F(2)----------------­----> F(1)F(0)

et voila à chaque itération en divise par 2 et on diminue 1 jusqu'a F(1) et F(0)
et merci d'avance

RE !!!

Je viens de comprendre ou le bas blesse....

C'est un algorithme à compléxité logarithmique que tu recherche et ainsi non pas une méthode récursive terminale.

Cadeau pour toi : GOOGLE + WIKIPEDIA = https://fr.wikipedia.org/wiki/Suite_de_Fibonacci#Algorithme_logarithmique

Cordialement Kzanadeus.

oui avec le lien ça marche , je vous remerciez Kzanadeus

Bonjour

As-tu lu TON premier post ? La réponse esr dedans !

salut, cela me parait trop simple pour tout avoir compris mais s'est-on jamais.

int function fibo(int num)
{
if(num == 0)return 0;
if(num == 1 || num == 2)return 1;
return(fibo(num/2) + fibo((num/2)-1);
}

On dirait que c'est ce que tu veux faire mais il me semblait que la théorie était plutôt soit F la fonction de fibonacci :
Fx = Fx-1 + Fx-2
avec F0 = 0, F1 = 1 et F2 = 1.

Mais bon. J'espère que cela à pu t'aider un peu.

Cordialement Kzanadeus.