Complexité de l'algorithme d'exponentiation rapide - Bibm@th.net
Exercice 1 
- Complexité de l'algorithme d'exponentiation rapide [Signaler une erreur] [Ajouter à ma feuille d'exos]
- Complexité de l'algorithme d'exponentiation rapide [Signaler une erreur] [Ajouter à ma feuille d'exos]Enoncé 
L'algorithme d'exponentiation rapide est basé sur la remarque suivante : on a $a^{2p}=a^p\cdot a^p$ et $a^{2p+1}=a^p\cdot a^p\cdot a$. Ainsi, pour calculer $a^{2p}$, il suffit de savoir calculer $a^p$ et de faire une multiplication, et pour calculer $a^{2p+1}$, il suffit de savoir calculer $a^p$ et de faire deux multiplications. L'algorithme suivant implémente récursivement l'algorithme d'exponentiation rapide sous Python :
def exporapide(a,n):
if n==0:
return 1
b=exporapide(a,n//2)
if (n%2)==1:
return b*b*a
else:
return b*b
def exporapide(a,n):
if n==0:
return 1
b=exporapide(a,n//2)
if (n%2)==1:
return b*b*a
else:
return b*b
Démontrer que, pour tout $n\geq 1$, le nombre total de multiplications effectuées par un appel à exporapide(a,n) est inférieur ou égal à $2+2\lfloor \log_2 n\rfloor$.
