Methode exponentiation rapide

[missnais]

Bonjour,
J'ai un niveau en mathematique de terminale ES, je prépare le tage mage et ai besoin d'une explicatition simple et detaillée de la méthode de l'exponentiation rapide afin de pouvoir caculer sans calculette des nombres à puissances. Merci d'avance pour votre précieuse aide car je suis à Taiwan et personne ne peux m'aider. :cry:

[busard_des_roseaux]

Bjr,


pour calculer par exemple :

on décompose l'exposant 15 en base 2:


il suffit d'élever au carré pour obtenir
au carré pour obtenir
au carré pour obtenir

ce qui conduit à l'algorithme:

calcul_de_


3 -> U
n-1 -> k
TANT QUE , FAIRE:
Si k pair,
-> U , ->k .

si k impair
3U -> U , k-1 -> k
FIN TANT QUE
renvoyer U.

[fatal_error]

salut,

wiki semble répondre a ta question ici

Il suffit de regarder la partie algorythme.J'ai utilisé celui en ruby.
Ci-dessous figure un tableau de suivi de variables : a chaque ligne correspond un passage dans la boucle.

Un exemple avec n=5, x=3 :

resultat=243

Un autre avec n=6, x=3


resultat=729.
La ou figure un x, c'est un résultat non calculé car inutile (on s'arrete a n=0)

[missnais]

Merci beaucoup mais si je viens demander de l'aide sur ce forum c'est par ce que j'ai déjà chercher longuement des cours sur le net, aucun ne peuvent m'éclairer car ils me parlent de matrices, logarithmes, de bases, de récursivités etc je suis novice en math, je peux comprendre si on m'explique étape par étape ce que je dois faire concrètement avec un exemple, mais ne comprends pas le langage mathématique. C'est pas la peine de trop m'expliquer le pourquoi je ne pense pas avoir assez d'expérience en la matière pour comprendre.

Merci encore d'avance pour vos précieuses réponses.

[fatal_error]

def puissance(x,n)
resultat = 1
while (n != 0)
# si n est impair, on multiplie resultat par x
if ((n % 2) == 1) then
resultat = resultat * x
n=n-1
end
x = x*x
n = n/2
end
return resultat
end
//--->chez wiki
tu ne comprends pas l'algorythme?

PS: lalgo de busard_des_roseaux est encore plus "francisé". Essai de faire un tableau de variable...