Binary exponentiation
The binary exponentiation (including Square and multiply called) is an efficient method for the calculation of natural powers , ie expressions of the form with a natural number .
This algorithm was already used around 200 BC. Discovered in India and is recorded in a work called Chandahsûtra .
motivation
To calculate, you can either calculate (three multiplications) or , (two multiplications), that is .
Likewise, other wholenumber powers can be calculated efficiently by “continued squaring and occasional multiplication”.
This saving of multiplications works for real numbers as well as for realvalued matrices , elliptic curves and any other semigroups .
algorithm
 Conversion of the exponent into the associated binary representation .
 Replace every 0 with Q and every 1 with QM.
 Now Q is interpreted as an instruction to square and M as an instruction to multiply .
 Thus, the resulting character string, read from left to right, forms a rule for calculating . You start with one, squaring for each read Q the previous interim result and multiply it for each read M with .
Since the binary representation of always begins with the number 1  and so the instruction also begins with QM  the intermediate result for the first instruction QM is always obtained . For this reason, there is a slightly simplified variant in which the first instruction QM is replaced by.
Example (algorithm)
Let k = 23. The binary representation of 23 is 10111 . This results after the substitutions QM Q QM QM QM . After deleting the leading QM pair, you have Q QM QM QM . From this we can now read that the calculation process has to look like this: "square, square, multiply by , square, multiply by , square, multiply by ".
Formally, the whole thing looks like this: or written successively:
The example shows that binary exponentiation can save you a few calculation steps. Instead of 22 multiplications, only 7 are required by squaring four times and multiplying by three times .
Pseudocode (algorithm)
The algorithm is shown in two variants. Variant 1 uses an ifcondition to multiply at the appropriate places. Variant 2 implicitly builds the if condition into the arithmetic expression.
version 1  Variant 2 

// Calculates x ^ k // b ... binary representation of k // res ... result of the calculation function bin_exp (x, b) res = 1 for i = n..0 res = res ^ 2 if b_i == 1 res = res * x endif endfor return res endfunction 
// Calculates x ^ k // b ... binary representation of k // res ... result of the calculation function bin_exp (x, b) res = 1 for i = n..0 res = res ^ 2 * x ^ {b_i} endfor return res endfunction 
Alternative algorithm
You can also design the procedure for a calculation by hand in such a way that you first square the base often enough and then multiply the correct numbers with each other. Then it is similar to the Russian pawn multiplication , which traces the multiplication of two numbers back to halving, doubling and adding numbers.
To do this, write the exponent on the left and the base on the right. The exponent is gradually halved (the result is rounded down) and the base is gradually squared . Delete the lines with an even exponent. The product of the unprimed numbers on the right is the desired power.
Example (alternative algorithm)
2 ^{18}  
18th 

9  4th 
4th 

2 

1  65,536 
Result  262,144 (= 4 65,536 ) 
Pseudocode (alternative algorithm)
In contrast to the previous approach, the required powers of are multiplied by directly. This variant is useful if the exponent is not explicitly available in binary representation. To illustrate, the equality can be considered.
Should be determined without having to be in binary representation.
Binary exponentiation 

// Berechnet x^k
// res … Resultat der Berechnung
function res = bin_exp(x,k)
res = 1
while k > 0
if k mod 2 == 1
res = res * x
endif
x = x^2
k = k DIV 2 //Ganzzahlige Division (das Ergebnis wird abgerundet)
endwhile
return res
endfunction

Recursive algorithm with derivation
Every natural number can be clearly broken down into, where . Due to the power laws, it results
The last term only includes
 an exponentiation with an exponent that is only about half as large as , which can be calculated recursively with the same algorithm,
 a squaring,
 a multiplication,
 an exponentiation with 0 or 1 as an exponent.
A direct implementation in Haskell would look like this:
a^0 = 1
a^1 = a
a^2 = a*a
a^n = (a^m)^2 * a^b where (m, b) = n `divMod` 2
The function ^
that is defined here is based on an existing one *
for multiplication, divMod
for splitting off the lowest binary digit of the exponent and, recursively, itself.
Minor optimizations, such as the conversion to a final recursive variant, essentially lead to the iterative algorithms mentioned above.
Binary modulo exponentiation
When calculating modulo a natural number, a slight modification can be used to prevent the calculated numbers from becoming too large: After each squaring and multiplication, the remainder is formed. The algorithms presented above can easily be extended by these module operations. This method is used, for example, with RSA encryption .
example
2 ^{18} mod 39  
18th 

9  4th 
4th 

2 

1  16 (= 484 mod 39) 
Result  25 (= 4 16 mod 39 = 2 ^{18} mod 39) 
Runtime analysis
In the simple and slow potentiation of are multiplications. With binary exponentiation, the loop is run through only once ( corresponds approximately to the length of the number in the binary representation). In each loop pass there is a squaring (whereby the first squaring can be neglected) and possibly a multiplication. Operations (possibly longnumber operations) are required asymptotically , whereas operations are required for simple exponentiation. denotes an asymptotic upper bound for the runtime behavior of the algorithm. As can easily be seen, binary exponentiation is much more efficient than the simple method. This reduced demand on the computing power is enormous with large bases and exponents.
Similar algorithms
Binary exponentiation does not necessarily have to be the most multiplicationsaving method of calculating a power. For example, to calculate, one can either use binary exponentiation
calculate (6 multiplications), or else
 With
(5 multiplications in total).
Implementation in C ++
It is used as in the function from the STL . Instead , each limited may unsigned integer data type can be used if necessary. If a separate type is used for long number arithmetic (LZA), it can not be determined as here. What is important is the place i. H. a bit mask that masks the most significant bit. Whether and how this is effectively possible depends specifically on the type of LTA. It is always possible to copy the value and then delete set bits from the end until the copy is zero; or another linear method.
pow
unsigned
h
(#)
// b: basis
// e: Exponent
// Annahmen: Typ T besitzt T operator*(T, T) und eine 1.
template<typename T>
T bin_exp(T b, unsigned e)
{
if (!e) return T(1);
// Ab hier: e != 0, d, h. irgendein Bit in e ist 1.
unsigned h = ~(~0u >> 1); // h = binär 100...0
while (!(e & h)) h >>= 1;
// h maskiert nun das erste gesetzte Bit in e. (#)
T r = b;
// solange weitere Bits zu prüfen sind (das erste wurde durch r = b bereits abgearbeitet),
while (h >>= 1)
{
r *= r; // quadrieren
if (e & h) r *= b; // falls Bit gesetzt, multiplizieren
}
// h == 0, d. h. alle Bits geprüft.
return r;
}
literature
 Donald E. Knuth : The Art of Computer Programming . Vol 2. AddisonWesley, 1998 (Section 4.6.3, p. 461).
 Jörg Arndt, Christoph Haenel: Pi. Algorithms, computers, arithmetic. 2nd Edition. Springer, Berlin 2000, ISBN 3540662588 , pp. 120121.