1/4

Forum pour les étudiants de la préparation agreg option C de Grenoble

Modérateur : xcasadmin

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 10:01 am

Pour FIbonacci, on calcule une expression explicite des termes de la suite par résolution de l'équation caractéristique qui est : X^2-X-1=0.
On trouve deux racines, dont une seule (qui s'avère être le nombre d'or) est plus grande que 1 en valeur absolue, et on a donc un équivalent de la forme : x_n ~ a*phi^n (où \phi=(1+\sqrt(5))/2 est le nombre d'or).

On déduit donc la taille des termes de la suite en passant au log : taille(x_n) = n*ln(\phi)

Et donc le calcul de x_n à partir de x_{n-1} et x_{n-2} est en : max(taille(x_{n-1}),taille(x_{n-2})) = taille(x_{n-1}) = (n-1)*ln(\phi)

Et finalement, le calcul de x_n a un coût en : \sum_{k=0}^{n-1} k*ln(\phi) = n(n-1)/2 * ln(\phi) = O(n^2)

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 10:02 am

Si j'arrive à trouver du temps ce weekend j'essaierai de préparer un texte et je vous tiendrai au courant. Sinon les exercices me conviennent très bien (et me semblent tout aussi utiles pour l'oral d'option).

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 12:05 pm

En complément de la solution de Thomas pour Fibonacci, en voici une plus rapide utilisant les flottants multi-précision et à nouveau l'algorithme de la puissance rapide.

La précision des flottants qui sera nécessaire (nombre de chiffres significatifs de la mantisse) va etre proportionnelle à n. Si on utilise la relation de récurrence, on a aussi un cout en O(n^2).
Mais on peut utiliser la formule explicite donnant F(n) sous la forme C*((1+sqrt(5))/2)^n+D*((1-sqrt(5))/2)^n.
Pour trouver les valeurs explicites des constantes C et D, vous pouvez utiliser la commande rsolve

Code : Tout sélectionner

[Fn]:=rsolve(F(n+2)=F(n)+F(n+1),F(n),[F(0)=1,F(1)=1])
Il suffit ensuite de calculer en approché avec une précision suffisante pour obtenir le bon résultat en arrondissant le flottant à l'entier le plus proche. Et on peut appliquer l'algorithme de la puissance rapide pour calculer (1+sqrt(5))/2)^n avec des flottants multi-précision (l'autre terme de la somme est négligeable pour n grand). Pour n grand, le produit de deux flottants avec une précision proportionnelle à n est en O(n*ln(n)), le nombre d'étapes en O(ln(n)) donc le cout en O(n*ln(n)^2). Mais la constante cachée dans le O est grande, il faut des valeurs de n plus grandes qu'un million pour que cette méthode devienne plus rapide!

Session d'illustration: https://www-fourier.univ-grenoble-alpes ... g/fibo.xws, dont voici le détail:
programme pour Fibonacci avec des additions d'entiers (en syntaxe Xcas et Python)

Code : Tout sélectionner

fonction fibo(n) // nombre de Fibonacci par la methode la plus simple en O(n^2)
  local k,f;
  f:=1,1;
  pour k de 2 jusque n faire
    f:=f[1],f[0]+f[1];
  fpour;
  retourne f[1];
ffonction:;

Code : Tout sélectionner

def fibo(n):
   if n<2: return 1
   a,b=1,1
   for j in range(n-1):
     a,b=a+b,a
   return a
Fibonacci avec puissance rapide de flottants multi-précision

Code : Tout sélectionner

fonction fib(n) 
  // en utilisant la puissance rapide et la multiprecision, asymptotiquement en O(n*ln(n)^2)
  local k,f,a;
  // nombre de chiffres necessaires et marge de securite
  k:=ceil(n*log10((sqrt(5)/2+.5))+log(n)/log(2)*3);
  // puissance rapide iterative de sqrt(5)/2+1/2
  a:=sqrt(evalf(5,k))/2+1/2;
  f:=1;
  tantque n>0 faire
    si irem(n,2)=1 alors f:=f*a; fsi;
    a:=a*a;
    n:=iquo(n,2);
  ftantque;
  retourne round(f*(sqrt(5)+5)/10);
ffonction:;
On teste

Code : Tout sélectionner

n:=10^6;time(f:=fib(n));time(g:=fibo(n)); f-g
(fibo est plus rapide que fib)

Code : Tout sélectionner

n:=2*10^6;time(f:=fib(n));time(g:=fibo(n)); f-g
(a peu pres la meme vitesse)
Si vous avez la patience, essayez avec 4*10^6, fib devient plus rapide que fibo (sur ma machine, 50s pour fib et 100 pour fibo).

Répondre