Lecture zen
**
Algorithme d’exponentiation rapide
Soit un anneau \(A\), un élément de cet anneau \(a\in A\) et un entier \(n\in \mathbb N\). On rappelle que \[a^1 = a,\qquad\textrm{ et }\qquad a^n = aa^{n-1}.\]
Combien de multiplications faut-il pour calculer \(a^n\) avec cette méthode ?
Si l’on écrit \[b=a^2,~c=b^2,~d=c^2\] combien de multiplications sont-elles nécessaires pour calculer \(a^8\) ?
Plus généralement, si l’on écrit : \[a^n = \begin{cases} (a^k)\times (a^k) & \textrm{ si } n=2k \\ a\times (a^k)\times (a^k) & \textrm{ si } n=2k+1 \end{cases}\] et si on note \(T(n)\) le nombre de multiplications nécessaires pour calculer \(a^n\), trouver une relation entre \(T(n)\) et \(T\left( \left\lfloor {\scriptstyle n\over\scriptstyle 2} \right\rfloor\right)\).
Lorsque l’exposant \(n\) est une puissance de \(2\) : \(n=2^p\), calculer \(T(n)\).
Si un ordinateur met \(10^{-6}\) seconde pour effectuer une multiplication, comparer les temps de calcul de \(a^{100 000}\) en utilisant a) et c).
Barre utilisateur
[ID: 3333] [Date de publication: 18 novembre 2022 16:00] [Catégorie(s): Anneaux ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]Solution(s)
Solution(s)
Algorithme d’exponentiation
rapide
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 16:00
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 16:00
Il faut en calculer \(n-1\).
Il faut en calculer \(3\) : une pour \(b\), une pour \(c\) une pour \(d\).
On a \(T(n) = T\left( \left\lfloor {\scriptstyle n\over\scriptstyle 2} \right\rfloor\right)+1\) si \(n\) est pair et \(T(n) = T\left( \left\lfloor {\scriptstyle n\over\scriptstyle 2} \right\rfloor\right)+2\) si \(n\) est impair.
On vérifie que \(T(2^p) = p\).
Un peu moins de \(0,1\) seconde avec 1. Avec 3. on écrit en binaire \(100 000 = (11000011010100000)_2\) autrement dit \(10^5 = 2^5+2^7+2^9+2^{10}+2^{15}+2^{16}\). On a donc \(16+6-1=21\) opérations donc \(2,1\times10^{-5}\) seconde avec 3.
Documents à télécharger
L'exercice