Méthode naturelle et dichotomique

[Rockleader]

Il s'agit de déterminer le nombre de multiplication nécessaire pour calculer x^n



Alors par la méthode naturelle x^n = x*x*...*x on a donc n-1 multiplication.


Par la méthode dichotomique si j'ai bien compris on tente de réduire le nombre d'opération.

Exemple x^8 = (x*x) * x² * x^4 Le coût est donc de 3 multiplications.


Maintenant si je veux calculer x^n par la méthode dichotomique, comment on procède ?

[Kikoo <3 Bieber]

Hello Rockleader !

Je ne sais pas ce qu'est la méthode par dichotomie mais je pense que l'algorithme d'exponentiation rapide t'intéressera :)
Cela te permet de réduire de manière logarithmique le nombre d'opérations à effectuer.

[Rockleader]

Hello Rockleader !

Je ne sais pas ce qu'est la méthode par dichotomie mais je pense que l'algorithme d'exponentiation rapide t'intéressera
Cela te permet de réduire de manière logarithmique le nombre d'opérations à effectuer.

La méthode dichotomique c'est au lieu d'écrire x^8 = x*x*x*x*x*x*x*x

On écrit

x²=x*x
x^4=x²*x²
x^8 = x^4*x^4

Résultat 3 multiplication et non 7 c’est donc intéressant d'un point de vue machine.

Mais là je cherche pour n !




L'exponentiation rapide oui c'est ça.

J'aurais donc a^n = e(n*ln(a)) mais ça ne me donne pas le nombre de multiplication de a^n ça =)

[Jacky22]

Salut,

Alors je pensais à ça, si n>2,
x²=x*x
x^4=x^2*x^2
x^8=x^4*x^4
...
x^(k)=x^(k/2)*x^(k/2)
x^n=x^(n-k)*x^(k) si n pair

où k est un entier du type 2^(p) où p est un entier naturel et où n est compris entre k et 2*k.
Ce qui fait 2^(k)+1 opérations.
Pour le cas impair, je te laisse voir.

[Rockleader]

Salut et merci, j'ai bien suivis le raisonnement, mais je ne vois pas comment on peut dire pour autant qu'il y a 2^k +1 multiplications.

[Jacky22]

Pour le nombre d'opérations, je raisonne comme ceci :
x^2 -> 1 opération
x^4 -> 2 opérations
x^8 -> 3 opérations
x^16 -> 4 opérations
...
La puissance est multipliée par 2 à chaque opération. Donc, pour x^k, on a 2^k opérations.
Après, il reste l'opération pour obtenir x^n, ce qui fait 2^k+1.

[Jacky22]

Heu, désolé, je me suis un peu embrouillé et j'ai fait une erreur,
Pour la k ème opération, on arrive à la puissance x^(2^k)
Pour x^P, on est donc à la ln(P)/ln(2) ème opération.

Au final, on aurait donc ln(k)/ln(2)+1 opérations.