Concept

Exponentiation rapide

Résumé
En informatique, 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 »). Écriture mathématique La première façon de calculer une puissance x{{exp|n}} est de multiplier x par lui-même n 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 n mais de l'ordre de . Par exemple, si l'on écrit en base 2 n=\sum_{k=0}^d a_k2^k pour a_k\in {0,1}, on constate que :x^n=x^{a_0}(x^2)^{a_1}(x^{2^2})^{a_2}\dots (x^{2^d})^{a_d}. Il faut ainsi d opérations pour calculer tous les x^{2^k}, puis d opérations supplémentaires pour former le produit des (x^{2^k})^{a_k}. Le nombre total d'opérations est donc 2d, qui est bien de l'ordr
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement