Exponation binaire – Wikipedia
Le exponation binaire (aussi Carré et à cultiver appelé) est une méthode efficace pour calculer les puissances naturelles, c’est-à-dire exprimer la forme
Avec un nombre naturel
.
Cet algorithme était déjà d’environ 200 avant JC. BC a découvert en Inde et est appelé dans une œuvre Chandah-sûtra écrit.
Un
Pour calculer, vous pouvez soit
calculer (trois multiplications) ou
,
(deux multiplications), c’est-à-dire
.
De même, d’autres puissances entières peuvent être calculées efficacement par “carrés continus et multiplication occasionnelle”.
Ces multiplications de sauvegarde fonctionnent pour des nombres réels ainsi que des matrices réelles, des courbes elliptiques et tout autre demi-groupe.
- Conversion de l’exposant dans la présentation binaire associée.
- Remplacer tout le monde 0 à travers Q Et tout le monde d’abord à travers Qm.
- Devient maintenant Q Comme instruction pour les carrés et M compris comme des instructions pour le multiplicateur.
- Ainsi, la chaîne de caractères résultante de gauche à droite forme une disposition pour le calcul de . Vous commencez avec 1, carrés pour chaque lecture Q Le résultat provisoire précédent et le multiplique pour chaque lecture M avec .
Depuis la présentation binaire de
. Pour cette raison, il existe une variante légèrement simplifiée dans laquelle la première instruction QM à travers
est remplacé.
Exemple (algorithme) [ Modifier | Modifier le texte source ]]
Être k = 23. La présentation binaire de 23 est 10111 . Il en résulte le remplacement QM QM QM QM . Après avoir peint le principal QM -Ifaes tu as QM QM QM . À partir de cela, nous pouvons maintenant lire que le processus informatique doit être regardé comme suit: «Square, carrés, multiplier avec
, carrés, multiplier avec
, carrés, multiplier avec
«.
Formellement, le tout ressemble à ceci:
ou progressivement écrit:
Vous pouvez voir à partir de l’exemple que vous pouvez vous épargner quelques étapes de calcul à l’aide de l’exponation binaire.
Au lieu de 22 multiplications, seulement 7 sont nécessaires en carré quatre fois et trois fois avec
multiplié.
Pseudocode (algorithme) [ Modifier | Modifier le texte source ]]
L’algorithme est indiqué en deux variantes. La variante 1 utilise une condition IF pour se multiplier dans les endroits correspondants. Variante 2 incorpore implicitement la condition IF dans l’expression arithmétique.
version 1 | Variante 2 |
---|---|
// calcule x ^ k // b ... Représentation binaire de k // res ... résultat du calcul Fonction bin_exp (x, b) res = 1 pour i = n..0 res = res ^ 2 Si b_i == 1 res = res * x fin fin Retour Res fonction finale |
// calcule x ^ k // b ... Représentation binaire de k // res ... résultat du calcul Fonction bin_exp (x, b) res = 1 pour i = n..0 res = res ^ 2 * x ^ {b_i} fin Retour Res fonction finale |
Vous pouvez également concevoir la procédure pour un calcul à la main de manière à ce que vous fassez d’abord la base de la base assez souvent, puis multipliez les nombres corrects les uns avec les autres. Ensuite, il est similaire à la multiplication des agriculteurs russes, qui attribue la multiplication de deux nombres pour faire de moitié, double et ajouter des nombres.
Pour ce faire, écrivez l’exposant à gauche et la base à droite. L’exposant est progressivement divisé par deux (le résultat est arrondi) et la base est progressivement carré. Vous annulez les lignes avec un exposant droit. Le produit des droits non peinés est la puissance que vous recherchez.
Exemple (algorithme alternatif) [ Modifier | Modifier le texte source ]]
2 18 | |
18 | |
9 | 4 |
4 | |
2 | |
d’abord | 65 536 |
Résultat | 262.144 (= 4 · 65 536 ) |
Pseudocode (algorithme alternatif) [ Modifier | Modifier le texte source ]]
Contrairement à l’approche précédente, les puissances requises de
directement dégusté. Cette variante est idéale lorsque l’exposant
n’est pas explicitement présent dans la présentation binaire. Comme illustration, l’égalité peut
être considéré comme.
Devrait être déterminé
, sans
avoir dans la présentation binaire.
Exponation binaire |
---|
// calcule x ^ k
// res ... résultat du calcul
Fonction res = bin_exp (x, k)
res = 1
Tandis que k> 0
Si k mod 2 == 1
res = res * x
fin
X = x ^ 2
K = k div 2 // Nombre de division entièrement (le résultat est arrondi)
fin
Retour Res
fonction finale
|
Chaque nombre naturel
Peut être clairement dans
démonter, par lequel
. Sur la base des lois sur la puissance, il y a
La dernière expression ne comprend que
- une potentialisation avec un exposant Qui seulement à moitié aussi grand que est ce qui peut être calculé récursivement avec le même algorithme,
- Un carré,
- une multiplication,
- Une potentialisation avec 0 ou 1 comme exposant.
L’implémentation directe dans Haskell ressemblerait à ceci:
un ^ 0 = d'abord un ^ d'abord = un un ^ 2 = un * un un ^ n = ( un ^ m ) ^ 2 * un ^ b où ( m , b ) = n `` Divmod `` 2
La fonction ^
qui est défini ici est donc basé sur un existant *
Pour la multiplication, Divmod
Pour le rotation du point binaire le plus bas de l’exposant et, récursif, vous-même.
Des optimisations mineures, telles que la conversion en une variante répurative finale, conduisent essentiellement aux algorithmes itératifs mentionnés ci-dessus.
Lors du calcul du modulo d’un nombre naturel, une modification de la lumière est applicable qui empêche les nombres calculés de devenir trop grands: après chaque carrés et multiplicateur, le reste.
Cette procédure est utilisée, par exemple, pour le cryptage RSA.
Exemple [ Modifier | Modifier le texte source ]]
2 18 contre 39 | |
18 | |
9 | 4 |
4 | |
2 | |
d’abord | 16 (= 484 contre 39) |
Résultat | 25 (= 4 · 16 contre 39 = 2 18 contre 39) |
Avec la potentialisation simple et lente de
devenir
Multiplications nécessaires. Dans le cas de l’exponation binaire, la boucle est uniquement
-Run dans le temps (
correspond approximativement à la longueur du nombre
dans la présentation binaire). Dans chaque course de broyage, il y a un carré (par lequel le premier carré peut être négligé) et peut-être une multiplication. Devenir asymptotique
Opérations (opérations à long terme éventuellement à long terme) requises, tandis que
Battre les opérations en simple potentialisation.
Décrit une barrière supérieure asymptotique pour le comportement d’exécution de l’algorithme. Comme vous pouvez facilement le voir, l’exponation binaire est beaucoup plus efficace que le processus simple. Cette prétention réduite à la puissance de calcul est énorme pour les grandes bases et les exposants.
L’exponiation binaire ne doit pas nécessairement être le type de puissance de calcul la plus multiplication. À, par exemple,
Pour calculer, vous pouvez soit exponérer en fonction de l’exponation binaire
calculer (6 multiplications) ou mais
- avec
(un total de 5 multiplications).
Ce sera
utilisé, comme dans la fonction faire du quilles
De la st. Au lieu de non signé
tout le monde peut sans signe Utilisation du type de données entier si nécessaire. Un examen du débordement est manquant pour simplifier la présentation.
// b: base // E: Exposant // Hypothèses: le type T a l'opérateur * = (t) et A 1. modèle < typename T > T bin_exp ( T b , non signé C'est ) { si ( C'est == 0 ) retour T ( d'abord )); alors que ( C'est % 2 == 0 ) // E tout droit? { b * = b ; C'est / = 2 ; }
// hier ist e ungerade
T result = b;
while(true)
{
e /= 2;
if(e==0)
{
break;
}
b *= b;
if(e%2) // e ungerade?
{
result *= b;
}
};
return result;
}
Recent Comments