Scribd
Importer
8 vues1 page

Méthode binaire pour calculer x^n

Transféré par

Aboubaker Zirani
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
8 vues1 page

Méthode binaire pour calculer x^n

Transféré par

Aboubaker Zirani
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

1.2.2 Algorithme trivial yi = yi−1 ×y1,i ∈ [2,n]. Résultat : yn = x n . Coût : m−1 = n−1 multiplications.

Algorithme y[1] = x Pour i ← 2 à n faire y[i] = y[i−1] × y[1] renvoyer y[n] 1.2.3 Méthode binaire
Algorithme 1. Écrire n sous forme binaire 2. Remplacer chaque : – « 1 » par la paire de lettres « SX » ;
– « 0 » par la lettre « S ». 3. Éliminer la paire « SX » la plus à gauche. 4. Résultat : un mode de calcul
de x n où – S signifie « élever au carré » (squaring) ; – X signifie « multiplier par x ». Le tout en partant
de x. Illustration avec n = 23 1. n = 10111 1 0 1 1 1 2. SX S SX SX SX 3. S SX SX SX 4. Nous partons de x
et nous obtenons successivement : x 2 , x 4 , x 5 , x 10 , x 11 , x 22 , x 23 . Nous sommes donc
capables de calculer x 23 en 7 multiplications au lieu de 22 ! Explication de la méthode – Écriture
binaire de n : n = ∑ i=p i=0 ai2 i . – Plaçons nous au cours du calcul de puissances de x. Soit j le dernier
bit de la représentation binaire de n qui ait été « décodé » et soit yj le dernier résultat obtenu.
Initialement, j = p et yp = x = x ap . – Deux cas sont possibles pour aj−1 : 1. aj−1 = 1. aj−1 est remplacé
par SX, nous élevons y j au carré puis multiplions le résultat par x. Le nouveau résultat est yj−1 = y 2 j
×x. 2. aj−1 = 0. aj−1 est remplacé par S et nous élevons simplement yj au carré. Le nouveau résultat
est y j−1 = y 2 j . Dans tous les cas nous avons : yj−1 = y 2 j ×(x aj−1 ). – D’où, yp−1 = y 2 p ×(x ap−1 ) =
(x ap ) 2 ×

Vous aimerez peut-être aussi