Algorithmique ii - Square & Multiply

Présentation de l'algorithme.

Étant donnés un objet \(x\) et un entier relatif \(k\), le problème est de calculer une exponentielle \(x^k\), c'est-à-dire \(x\times x\times\cdots\times x\) où \(x\) apparaît \(k\) fois. Ce problème ne se limite pas à l'exponentiation de nombres \(x\) réels mais concerne l'exponentiation dans tout semi-groupe :

On appelle semi-groupe tout ensemble \(E\) muni d'une loi de composition interne \(*\) (\(\forall (x,y)\in E\times E,\ x*y\in E\)) et associative (\(\forall (x,y,z)\in E^3,\ x*(y*z)=(x*y)*z\in E\)). Si de plus il existe un élément neutre \(e\in E\) (\(\forall x\in E,\ e*x=x*e=x\)), le semi-groupe est un monoïde.
Pour ne citer que deux exemples, l'exponentiation est utilisée intensivement dans de nombreux pro­to­co­les cryptographiques, comme rsa et en algèbre linéaire où les puissances d'une matrice in­ter­vien­nent dans des contextes variés. Nous supposerons donc dans toute la suite que \(x\) est un élément d'un semi-groupe \((G,*)\) noté multiplicativement et que \(k\) est un entier naturel.

L'algorithme naïf qui consiste à multiplier la valeur \(x\) par elle-même \(k - 1\) fois dans le semi-groupe a un coût proportionnel à l'exposant \(k\) si l'on suppose que la multiplication a un coût fixe (ce qui est évi­dem­ment faux dès que l'on travaille en multiprécision, nous reviendrons sur ce point au chapitre Calcul multiprécision).

Écrivez l'algorithme d'exponentiation naïf sur la machine ram en supposant qu'un registre est capable de stocker des valeurs arbitrairement grandes.

L'idée sur laquelle repose l'algorithme de l'exponentiation binaire est très naturelle. En calculant le carré \(x^2\) de \(x\), puis le carré de \(x^2\), on obtient \(x^4\) en deux multiplications au lieu des trois nécessaires avec l'algorithme naïf. On peut continuer le processus et obtenir \(x^8\) en trois multiplications au lieu de sept, etc. À première vue, ce procédé ne paraît intéressant que pour les exposants \(k\) qui sont des puissance de 2, mais les règles de calcul sur les exponentielles permettent de dépasser cette apparente limitation. En effet, on rappelle que si \(r\) et \(s\) désignent deux entiers, alors \[x^{r+s}=x^r\times x^s.\] Ainsi, comme tout entier \(k\) peut s'écrire de manière unique comme une somme de puissances de \(2\) (c'est ce qu'exprime son écriture en base 2), il existe donc une séquence \((k_i)\) de \(t+1\) bits tels que \[k:=\sum_{i=0}^t k_i\times 2^i,\] on a donc \[x^k=\prod_{i=0}^t x^{k_i\times 2^i}.\] La table suivante illustre le mécanisme pour k = 87 et la décomposition en base 2 de k est donnée du chiffre le plus significatif au chiffre le moins significatif

\(k=87\) : 1 0 1 0 1 1 1
Exposant \(i\) : 6 5 4 3 2 1 0
Puissance de 2 : 64 32 16 8 4 2 1
Opérations : SM S SM S SM SM SM

Décomposion binaire de l'entier \(k=87\).
et ainsi
x87 = x64 × x16 × x4 × x2 × x1

On peut reconstituer \(x^k\) avec deux opérations uniquement, l'élévation au carré (noté S pour Square) et la multiplication par x (noté M pour Multiply). En effet, en initialisant une variable \(r\) à \(e\), l'élément neutre pour la multiplication (si l'on considère un monoïde plutôt qu'un semi-groupe, mais l'algorithme s'adapte trivialement), il suffit de lire successivement les bits de l'écriture binaire de l'entier \(k\) dans l'ordre des puissances décroissantes de \(2\), et pour chaque bit lu :

  1. On élève \(r\) au carré;
  2. Si le bit est égal à 1, on multiplie \(r\) par \(x\).

L'algorithme ci-dessous formalise ce processus :
SquareMultiply(x,k):valeur;
données
   x: valeur  // dans le monoide considéré
   k: entier  // exposant
variables
   R: valeur 
   i: entier // relatif, attention au test de boucle !
   B: tableau binaire // bit de poids faible en 0 
debut
   R ← e
   B ← Bits(k) // Bits renvoie la séquence binaire
   i ← #B - 1
   TQ (i ≥ 0) FAIRE  
      R ← R × R
      SI (B[i] = 1) ALORS
         R ← R × x
      FSI
      i ← i - 1
   FTQ
   RENVOYER R
fin
pour calculer \(x^{87}\), on applique donc la séquence d'instructions SM, S, SM, S, SM, SM, SM. Le tableau ci-dessous fournit le contenu de la variable \(R\) à après l'exécution des instructions de la boucle  TQ pour la valeur \(k=87\) :

 \(i\)   \(B[i]\)  op \(R\) (après opération)
\(e\)
6 1  SM  \(x\)
5 0 S \(x^2\)
4 1 SM \(x^4\times x\)
3 0 S \(x^8\times x^2\)
2 1 SM \(x^{16}\times x^4\times x\)
1 1 SM \(x^{32}\times x^8\times x^2\times x\)
0 1 SM \(x^{64}\times x^{16}\times x^4\times x^2\times x\)
Évolution des variables dans l'algorithme d'exponentiation binaire.

nous ne décrivons pas l'algorithme Bits car les entiers sont déjà codés en binaire en machine et qu'il existe toujours une manière efficace d'accéder aux chiffres binaires d'un entier sans avoir à faire de décomposition binaire inutile et coûteuse. Le chapitre sur le modèle de donnée ensemble reviendra sur cette question.
Quel est le nombre minimal de multiplications permettant de calculer \(x^{15}\) ? Comparer ce nombre au nombre de multiplications effectuées par l'algorithme SquareMultiply.
Écrivez l'algorithme d'exponentiation binaire sur la machine ram en supposant qu'un registre est capable de stocker des valeurs arbitrairement grandes.

Complexité.

Plutôt que la complexité au sens strict, nous allons évaluer le coût \(C(k)\) de l'algorithme exprimé en nombre de produits en fonction de l'exposant \(k\). Ce choix est légimité par le fait que l'al­go­ri­thme s'applique à n'importe quel semi-groupe, un calcul de complexité strict imposerait d'intégrer le coût de chaque produit, or l'algorithme auxiliaire qui effectue ce produit dépend de la nature du semi-groupe considéré, un produit d'entiers n'est pas équivalent à un produit de matrices par exemple.

Nous verrons à ce sujet dans le cadre du calcul multiprécision que les opérations arithmétiques sur les entiers n'ont pas un coût constant et que ce coût dépend de la taille des nom­bres que l'on manipule. L'algorithme de la multiplication étudié dans les classes du primaire a un coût quadratique en la taille des opérandes par exemple.
En guise d'exercice, le lecteur pourra démontrer le résultat classique suivant:
Soit \(N\) et \(b\) deux entiers naturels avec \(b\geq 2\). Le nombre de chiffres de l'écriture de \(N\) en base \(b\) est égal à \(\lfloor\log_{b}N\rfloor+1.\)
Soit \(q\) un entier naturel non-nul. On appelle poids \(q\)-aire d'un entier naturel \(N\) le nombre de ses chiffres non-nuls dans son écriture en base \(q\) et que l'on note \(\text{wt}_q(N)\).

Nous noterons \(n\) le nombre de chiffres binaires de l'exposant \(k\), c'est-à-dire \(n:=\lfloor\log_{2}k\rfloor+1\) d'après le lemme ci-dessus. Nous savons que le nombre de multiplications utilisées pour les élévations au carré (S) est exactement le nombre de chiffres de l'écriture binaire de \(k\) soit \(n\). Le nombre de mul­ti­pli­ca­tions pour l'opération (M) est égal au poids binaire \(\text{wt}_2(k)\) de l'entier \(k\). Comme la taille \(n\) est fixée le bit de poids fort est égal à \(1\), le nombre d'opé­ra­tions (M) est donc borné :

\[1\leq\text{wt}_2(k)\leq n.\]

On peut alors conclure par la proposition suivante :

Le coût en nombre de multiplications de l'algorithme SquareMultiply dans le meilleur des cas et dans le pire des cas est donné par les deux fonctions suivantes : \begin{align} \hat{C}_(k)&=2n\\ \check{C}(k)&=n+1\\ \end{align} où \(n=\lfloor\log_2 k\rfloor+1\) est le nombre de chiffres binaires de l'exposant \(k\).

Il reste à évaluer le cas moyen. On sait que quelle que soit l'instance \(k\) de taille \(n\) que l'on considère pour l'exposant, le nombre de multiplications pour calculer les carrés (S) est toujours égal à \(n\). D'autre part le bit de poids fort de \(k\) étant nécessairement égal à 1, il y a toujours une multiplication \(M\) à la première étape. Ce sont les \(n-1\) bits de poids faible qui vont fixer le nombre de mul­ti­pli­ca­tions qu'il reste à effectuer. Il y a donc \(2^{n-1}\) instances différentes à étudier, correspondant aux dif­férentes valeurs possibles des \(n-1\) bits de poids faible.

Le nombre d'opérations (M) étant égal au poids binaire de \(k\), on peut calculer la moyenne en par­ti­tion­nant l'ensemble \(K\) des séquences binaires de longueur \(n-1\) en \(n\) classes selon les différents poids possibles :

\[K_p:=\left\{u\in\{0,1\}^{n-1}\mid \text{wt}_2(n) = p\right\},\quad p\in[0,n-1].\]

On a donc à ce stade:

\[\overline{C}(k)=n+1+\frac{1}{2^{n-1}} \sum_{p=0}^{n-1}p|K_p|. \]

On veut dans un premier temps calculer les cardinaux \(|K_p|\). On rappelle que si \(p\) et \(n\) désignent deux entiers naturels avec \(0\leq p\leq n\), le nombre de parties à \(p\) éléments dans un ensemble à \(n\) élements, noté \(\binom{n}{p}\) est égal à

\[\binom{n}{p}=\frac{n!}{(n-p)!p!}.\]

En montre aisément que:

Il existe exactement \(\binom{n}{p}\) séquences binaires de longueur \(n\) et de poids binaire \(p\).

On en déduit que \(|K_p|=\binom{n}{p}\), le coût moyen devient

\[\overline{C}(k)=n+1+\frac{1}{2^{n-1}} \color{yellow}{\sum_{p=0}^{n-1}p\binom{n-1}{p}}. \]

Il nous reste à calculer la somme ci-dessus.

Soient \(p\) et \(n\) deux entiers naturels tels que \(0\leq p\leq n\). Alors \[\sum_{p=0}^{n}p\binom{n}{p}=n2^{n-1}.\]
En remplaçant \(y\) par \(1\) dans l'expression du binôme de Newton, on obtient \[(x+1)^n=\sum_{p=0}^n\binom{n}{p}x^{n-p}.\] En dérivant les deux côtés de l'égalité par rapport à \(x\) et en utilisant l'identité \(\binom{n}{p}=\binom{n}{n-p}\) (en faire la preuve), on obtient \[n(x+1)^{n-1}=\sum_{p=1}^np\binom{n}{p}x^{p-1}.\] Il suffit d'évaluer l'expression en \(x=1\) pour conclure.
Le coût moyen en nombre de multiplications de l'algorithme SquareMultiply est donné par la fonction suivante : \begin{equation}\label{eq:moyenne} \overline{C}(k)=\frac {3n+1}{2}\quad\text{où}\quad n=\lfloor\log_2 k\rfloor+1 \end{equation}
Démontrez le lemme 2. Rappel : on admettra que pour tout nombre réel \(x\geq 0\), il existe un unique entier naturel \(N\) tel que \(N\leq x < N+1\), cet entier est appelé la partie entière de \(x\), notée \(\lfloor x\rfloor\).
Démontrez le lemme 5.
Soient \(p\) et \(n\) deux entiers naturels tels que \(0\leq p\leq n\). Écrivez un algorithme qui calcule le nombre de combinaisons de \(p\) parmi \(n\) en exploitant les trois identités suivantes : \begin{equation*} \binom{n}{p}=\binom{n}{n-p},\qquad\binom{n+1}{p+1}=\frac{n+1}{p+1}\binom{n}{p},\qquad\binom{n}{0}=1. \end{equation*} Comparez sa complexité avec celle du calcul direct qui s'appuie sur la fonction factorielle dont on intègrera le coût.
Soit \(n\) un entier naturel tel que \(n\geq 1\)et \(B\) une matrice \(2^n\times n\) dont les lignes sont cons­ti­tuées par les \(2^n\) séquences binaires distinctes de longueur \(n\). Démontrez que chaque colonne de cette matrice contient exactement \(2^{n-1}\) valeurs \(0\) et autant de valeurs \(1\). En déduire le résultat \((\ref{eq:moyenne})\).

Travaux pratiques

Écrivez une fonction Python Lire() qui lit les valeurs x et n au clavier et les renvoie. Écrivez une fonction Python SM(x,n) qui calcule la valeur de \(x^n\) à l'aide de l'algorithme SquareMultiply et renvoie le résultat. Enfin écrivez un programme qui utilise ces fonctions pour le tester.

[Solution en C]
[Solution en Python]