Exponation binaire – Wikipedia

Posted on May 19, 2018 by lordneo

before-content-x4

Le exponation binaire (aussi Carré et à cultiver appelé) est une méthode efficace pour calculer les puissances naturelles, c’est-à-dire exprimer la forme

{displaystyle x ^ {k}}

after-content-x4

$x^k$ Avec un nombre naturel

{displaystyle k}

$k$ .

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.

{displaystyle z = x ^ {4}}

$z = x^4$ Pour calculer, vous pouvez soit

{displayStyle z = xcdot xcdot xcdot x}

$z = x cdot x cdot x cdot x$ calculer (trois multiplications) ou

{displayStyle y = xcdot x}

$y = x cdot x$ ,

after-content-x4

{displaystyle z = ycdot y}

$z = y cdot y$ (deux multiplications), c’est-à-dire

{displayStyle z = (x ^ {2}) ^ {2}}

$z = (x^2)^2$ .

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 ${displaystyle k}$
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 ${displaystyle x ^ {k}}$

Depuis la présentation binaire de

{displaystyle k> 0}

$k>0″>commence toujours par la section 1 – et donc aussi les instructions avec QM commence -, suit pour la première instruction QM Dans tous les cas, le résultat intermédiaire <span class=$

{displayStyle 1 ^ {2} cdot x = x}

$1^2 cdot x=x$ . Pour cette raison, il existe une variante légèrement simplifiée dans laquelle la première instruction QM à travers

{displaystyle x}

$x$ est remplacé.

Table of Contents

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

{displaystyle x}

$x$ , carrés, multiplier avec

{displaystyle x}

$x$ , carrés, multiplier avec

{displaystyle x}

$x$ «.

Formellement, le tout ressemble à ceci:

{displayStyle Left (Left ((x ^ {2}) ^ {2} cdot xRight) ^ {2} cdot xRight) ^ {2} cdot x}

$left( left( (x^2)^2 cdot x right)^2 cdot x right)^2 cdot x$ ou progressivement écrit:

{displayStyle x; {stackrel {mathrm {q}} {longRightArrow}}; x ^ {2}; {stackrel {mathrm {q}} {longRightArrow}}; x ^ {4}; {stackrel {CDOT X} {LongRightArw m {q}} {longRightArrow}}; x ^ {10}; {stackRel {cdot x} {longRightArrow}}; x ^ {11}; {empesser {mathrm {q}} {longRightArrow}}; x ^ {22}; {{};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};};}; {23}}

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

{displaystyle x}

$x$ 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

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	2
9	4
4	16
2	~~256~~
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

{displaystyle x}

$x$ directement dégusté. Cette variante est idéale lorsque l’exposant

{displaystyle k}

$k$ n’est pas explicitement présent dans la présentation binaire. Comme illustration, l’égalité peut

{displayStyle x ^ {23} = x ^ {16} CDOT x ^ {4} CDOT X ^ {2} CDOT X}

${displaystyle x^{23}=x^{16}cdot x^{4}cdot x^{2}cdot x}$ être considéré comme.

Devrait être déterminé

{displaystyle x ^ {k}}

$x^k$ , sans

{displaystyle k}

$k$ 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

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

{displaystyle n}

$n$ Peut être clairement dans

{displayStyle n = 2m + b}

$n = 2m+b$ démonter, par lequel

{displaystyle bin {0,1}}

$bin{0,1}$ . Sur la base des lois sur la puissance, il y a

{displayStyle {begin {aligné} a ^ {n} & = a ^ {2m + b} \ & = (a ^ {m}) ^ {2} a ^ {b} .end {aligné}}}

La dernière expression ne comprend que

une potentialisation avec un exposant ${displaystyle m}$
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 ¹⁸contre 39
18	2
9	4
4	16
2	22 (= 256 contre 39)
d’abord	16 (= 484 contre 39)
Résultat	25 (= 4 · 16 contre 39 = 2 ¹⁸contre 39)

Avec la potentialisation simple et lente de

{displaystyle x ^ {k}}

$x^k$ devenir

{displayStyle (k-1)}

$(k-1)$ Multiplications nécessaires. Dans le cas de l’exponation binaire, la boucle est uniquement

{DisplayStyle Log _ {2} (k)}

$log_2(k)$ -Run dans le temps (

{DisplayStyle Log _ {2} (k)}

$log_2(k)$ correspond approximativement à la longueur du nombre

{displaystyle k}

$k$ 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

{displayStyle o (log (k))}

$O(log(k))$ Opérations (opérations à long terme éventuellement à long terme) requises, tandis que

{displaystyle o (k)}

$O(k)$ Battre les opérations en simple potentialisation.

{displaystyle o}

$O$ 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,

{displaystyle z = x ^ {15}}

$z = x^{15}$ Pour calculer, vous pouvez soit exponérer en fonction de l’exponation binaire

{displayStyle z = Left (Left ((x ^ {2} cdot x) ^ {2} cdot xRight) ^ {2} cdot xRight)}

calculer (6 multiplications) ou mais

{displayStyle z = y ^ {3} = ycdot y ^ {2}}

(un total de 5 multiplications).

Ce sera

{DisplayStyle 0 ^ {0}: = 1}

$0^0 := 1$ 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;
}

after-content-x4

Exponation binaire – Wikipedia

Exemple (algorithme) [ Modifier | Modifier le texte source ]]

Pseudocode (algorithme) [ Modifier | Modifier le texte source ]]

Exemple (algorithme alternatif) [ Modifier | Modifier le texte source ]]

Pseudocode (algorithme alternatif) [ Modifier | Modifier le texte source ]]

Exemple [ Modifier | Modifier le texte source ]]

Recent Posts

Recent Comments

Archives

Categories

Meta