Exponentiation Rapide

Exponentiation Rapide

Exponentiation rapide

L'exponentiation rapide est un algorithme utilisé pour calculer rapidement, de grandes puissances entières. En anglais, cette méthode est aussi appelée square-and-multiply (« mettre au carré et multiplier »).

Sommaire

Écriture mathématique

La première façon de calculer une puissance np, est de multiplier n par lui-même p fois. Cependant, il existe des méthodes bien plus efficaces, où le nombre d'opérations nécessaires n'est plus de l'ordre de p mais de l'ordre de log(p), pour le logarithme en base 2. On peut par exemple écrire p=\sum_{i\leq d} a_i2^i pour a_i\in \{0,1\}, et on constate alors que :

n^p=n^{a_0}(n^2)^{a_1}(n^4)^{a_2}\dots (n^{2^d})^{a_d}

Il faut ainsi d opérations pour calculer tous les n^{2^i}, puis d opérations supplémentaires pour former le produit des (n^{2^i})^{a_i} pour i variant. Le nombre d'opérations total est donc 2d, qui est bien de l'ordre du logarithme de p. Cette simple remarque algébrique conduit par exemple à l'algorithme ci-dessous.

Algorithme

Soit n un entier strictement supérieur à 1, supposons que l'on sache calculer pour tout x appartenant à l'ensemble des réels, toutes les puissances xk de x, pour tout k, tel que 1 \le k < n .

  • Si n est pair alors xn = (x2)n / 2. Il suffit alors de calculer yn / 2 avec y = x2.
  • Si n est impair et n>1, alors x^n = x\cdot(x^2)^{(n-1)/2}. Il suffit de calculer y(n − 1) / 2 avec y = x2 et de multiplier par x le résultat.

Cette remarque nous amène à l'algorithme récursif suivant qui calcule xn pour un entier strictement positif n:


\mbox{puissance}(x,\,n)=\left\{
\begin{matrix} x, & \mbox{si }n\mbox{ = 1} \\ 
\mbox{puissance}(x^2,\,n/2), & \mbox{si }n\mbox{ est pair} \\
x\times\mbox{puissance}(x^2,\,(n-1)/2), & \mbox{si }n >\mbox{2 est impair} \\
\end{matrix}\right.

En comparant à la méthode ordinaire qui consiste à multiplier x par lui-même n-1 fois, cet algorithme nécessite de l'ordre de O(lg n) multiplications et ainsi accélère le calcul de xn de façon spectaculaire pour les grands entiers.

La méthode fonctionne dans tout semi-groupe et est souvent utilisée pour calculer des puissances de matrices, et particulièrement en cryptographie, mais aussi pour calculer les puissances dans un anneau d'entiers modulo q. Elle peut être aussi utilisée pour calculer des puissances d'un élément dans un groupe, en utilisant pour les puissances négatives la règle : puissance(x, -n) = (puissance(x, n))-1.

Exemples d'implémentation

Voici une implémentation itérative de l'algorithme précédent, dans le langage de programmation Ruby. Dans la plupart des langages, vous aurez besoin de remplacer resultat=1 par resultat=matrice_unite_de_la_meme_taille_que_x, pour obtenir le programme de calcul d'une puissance d'une matrice. En Ruby, resultat s'adapte automatiquement au type approprié. Ainsi, cette fonction s'utilise aussi bien avec les matrices, qu'avec les entiers ou les réels.


def puissance(x,n)
    resultat = 1
    while (n != 0)
        # si n est impair, on multiplie resultat par x
        if ((n % 2) == 1) then
            resultat = resultat * x
            n=n-1
        end
        x = x*x
        n = n/2
    end
    return resultat
end

Un autre exemple d'implémentation, cette fois en Pascal, et en utilisant la récursivité.

function puissance(x,n:longint):longint;
var intermediaire:longint;
begin
	if n=1 then
		puissance:=x
	else
		begin
			intermediaire:=puissance(x,n div 2);
			if (n mod 2)=0 then
				puissance:=intermediaire*intermediaire
			else
				puissance:=intermediaire*intermediaire*x;
		end
end;

Enfin, un exemple dans un langage fonctionnel, OCaml. Pour travailler en toute généricité, on fournit à la fonction une fonction de multiplication (correspondant au * sur les entiers) et un élément neutre (correspondant à 1). Cela permet par exemple de faire une exponentiation rapide sur les polynômes.

let rec puissance neutre ( * ) a = function
  0 -> neutre
| n -> let b = puissance neutre ( * ) (a * a) (n / 2) in
       if n mod 2 = 0 then b else a * b;;

On peut aussi observer que cette fonction permet de faire une multiplication rapide en ne se servant que de la fonction d'addition : "puissance 0 ( + ) 3 7" renvoie bien 21.

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Exponentiation rapide ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Exponentiation Rapide de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Exponentiation rapide — L exponentiation rapide est un algorithme utilisé pour calculer rapidement, de grandes puissances entières. En anglais, cette méthode est aussi appelée square and multiply (« mettre au carré et multiplier »). Sommaire 1 Écriture… …   Wikipédia en Français

  • Exponentiation Modulaire — En mathématiques, plus précisément en arithmétique modulaire, l exponentiation modulaire est un type d élévation à la puissance (exponentiation) exécutée modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le… …   Wikipédia en Français

  • Exponentiation modulaire — En mathématiques, plus précisément en arithmétique modulaire, l exponentiation modulaire est un type d élévation à la puissance (exponentiation) exécutée modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le… …   Wikipédia en Français

  • Exponentiation — Notation du résultat de l exponentiation de base a et d exposant b. En mathématiques, l’exponentiation est une opération binaire non commutative qui étend la notion de puissance en algèbre. Elle se note en plaçant l un des opérandes en exposant… …   Wikipédia en Français

  • Rapide — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Rapide », sur le Wiktionnaire (dictionnaire universel) Rapide est un adjectif qui indique une vitesse… …   Wikipédia en Français

  • Rapides — Rapide Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Formule BBP — La formule BBP (ou Bailey Borwein Plouffe) permet de calculer le nème chiffre après la virgule de π en base 2 (ou 16) sans avoir à en calculer les précédents, et en utilisant très peu de mémoire et de temps. Elle a été obtenue le… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Exposant (mathématiques) — Pour les articles homonymes, voir Exposant. En mathématiques, l opération puissance consiste à multiplier un nombre a par lui même plusieurs fois de suite. Le nombre de facteurs intervenant dans cette opération est noté à la suite du nombre a en… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”