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}.\]

  1. Combien de multiplications faut-il pour calculer \(a^n\) avec cette méthode ?

  2. Si l’on écrit \[b=a^2,~c=b^2,~d=c^2\] combien de multiplications sont-elles nécessaires pour calculer \(a^8\) ?

  3. 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)\).

  4. Lorsque l’exposant \(n\) est une puissance de \(2\) : \(n=2^p\), calculer \(T(n)\).

  5. 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
  1. Il faut en calculer \(n-1\).

  2. Il faut en calculer \(3\) : une pour \(b\), une pour \(c\) une pour \(d\).

  3. 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.

  4. On vérifie que \(T(2^p) = p\).

  5. 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