Discuter:Exponentiation rapide
Un article de Wikipédia, l'encyclopédie libre.
En passant, une application de l'algorithme est le calcul rapide des termes d'une suite à récurrence linéaire, par exemple la suite de Fibonacci f, qui vérifie:
( f_(n+1) ) = ( 0 1 ) ( f_n ) ( f_(n+2) ) ( 1 1 ) ( f_(n+1) )
en notant A la matrice carrée ( 0 1 / 1 1 ) on a donc
( f_k ) k ( f_0 ) k ( 0 ) ( f_(k+1) ) = A ( f_1 ) = A ( 1 )
où peut calculer A^k en O(log k) opérations grâce à l'exponentiation rapide.
- Bonjour,
- en fait cette méthode est donnée dans la page suite de Fibonacci sous une forme légèrement différente.
- COLETTE 8 avr 2003 à 17:12 (CEST)
Le code Pascal donné en exemple me semble faux.
D'une part, la variable puissance qui est modifiée n'est jamais renvoyée. Il est possible que ce soit une feature cachée de ce langage que je ne connais pas, mais on ne sait jamais.
L'erreur qui me gêne beaucoup (j'ai essayé de trouver un pascaleux pour le corriger correctement, mais c'est visiblement une espèce en voie de disparition) c'est le fait que l'algorithme n'utilise pas de variable intermédiaire pour stoquer le résultat de l'appel récursif à la fonction :
puissance:=puissance(x,n div 2)*puissance(x,n div 2)
Il faut impérativement stocker le résultat de puissance(x,n div 2) dans une variable, sinon la complexité de l'algorithme redevient linéaire, ce qui lui enlève tout son intérêt. On peut donc considérer que le code actuel est faux.
Bluestorm 2 mars 2007 à 11:40 (CET)
