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

This algorithm was already used around 200 BC. Discovered in India and is recorded in a work called Chandah-sûtra .

motivation

To calculate, you can either calculate (three multiplications) or , (two multiplications), that is . ${\ displaystyle z = x ^ {4}}$ ${\ displaystyle z = x \ cdot x \ cdot x \ cdot x}$ ${\ displaystyle y = x \ cdot x}$ ${\ displaystyle z = y \ cdot y}$ ${\ displaystyle z = (x ^ {2}) ^ {2}}$

Likewise, other whole-number powers can be calculated efficiently by “continued squaring and occasional multiplication”.

This saving of multiplications works for real numbers as well as for real-valued matrices , elliptic curves and any other semigroups .

algorithm

Conversion of the exponent into the associated binary representation . ${\ displaystyle k}$

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

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. ${\ displaystyle k> 0}$ ${\ displaystyle 1 ^ {2} \ cdot x = x}$ ${\ displaystyle x}$

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 ". ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle x}$

Formally, the whole thing looks like this: or written successively: ${\ displaystyle \ left (\ left ((x ^ {2}) ^ {2} \ cdot x \ right) ^ {2} \ cdot x \ right) ^ {2} \ cdot x}$

{\ displaystyle x \; {\ stackrel {\ mathrm {Q}} {\ longrightarrow}} \; x ^ {2} \; {\ stackrel {\ mathrm {Q}} {\ longrightarrow}} \; x ^ { 4} \; {\ stackrel {\ cdot x} {\ longrightarrow}} \; x ^ {5} \; {\ stackrel {\ mathrm {Q}} {\ longrightarrow}} \; x ^ {10} \; {\ stackrel {\ cdot x} {\ longrightarrow}} \; x ^ {11} \; {\ stackrel {\ mathrm {Q}} {\ longrightarrow}} \; x ^ {22} \; {\ stackrel { \ cdot x} {\ longrightarrow}} \; x ^ {23}}

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 . ${\ displaystyle x}$

Pseudocode (algorithm)

The algorithm is shown in two variants. Variant 1 uses an if-condition 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
    end-if
  end-for
  return res
end-function

// 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}
  end-for
  return res
end-function

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 ¹⁸
18th	2
9	4th
4th	16
2	~~256~~
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. ${\ displaystyle x}$ ${\ displaystyle k}$ ${\ displaystyle x ^ {23} = x ^ {16} \ cdot x ^ {4} \ cdot x ^ {2} \ cdot x}$

Should be determined without having to be in binary representation. ${\ displaystyle x ^ {k}}$ ${\ displaystyle k}$

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
      end-if
      x = x^2
      k = k DIV 2 //Ganzzahlige Division (das Ergebnis wird abgerundet)
    end-while
    return res
  end-function

Recursive algorithm with derivation

Every natural number can be clearly broken down into, where . Due to the power laws, it results ${\ displaystyle n}$ ${\ displaystyle n = 2m + b}$ ${\ displaystyle b \ in \ {0.1 \}}$

{\ displaystyle {\ begin {aligned} a ^ {n} & = a ^ {2m + b} \\ & = (a ^ {m}) ^ {2} a ^ {b}. \ end {aligned}} }

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, ${\ displaystyle m}$ ${\ displaystyle n}$
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, divModfor 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 ¹⁸ mod 39
18th	2
9	4th
4th	16
2	22 (= 256 mod 39)
1	16 (= 484 mod 39)
Result	25 (= 4 16 mod 39 = 2 ¹⁸ 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 long-number 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. ${\ displaystyle x ^ {k}}$ ${\ displaystyle (k-1)}$ ${\ displaystyle \ log _ {2} (k)}$ ${\ displaystyle \ log _ {2} (k)}$ ${\ displaystyle k}$ ${\ displaystyle O (\ log (k))}$ ${\ displaystyle O (k)}$ ${\ displaystyle O}$

Similar algorithms

Binary exponentiation does not necessarily have to be the most multiplication-saving method of calculating a power. For example, to calculate, one can either use binary exponentiation ${\ displaystyle z = x ^ {15}}$

{\ displaystyle z = \ left (\ left ((x ^ {2} \ cdot x) ^ {2} \ cdot x \ right) ^ {2} \ cdot x \ right)}

calculate (6 multiplications), or else

{\ displaystyle z = y ^ {3} = y \ cdot y ^ {2}}

With

{\ displaystyle y = x ^ {5} = x \ cdot (x ^ {2}) ^ {2}}

(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. ${\ displaystyle 0 ^ {0}: = 1}$ powunsignedh(#)

// 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. Addison-Wesley, 1998 (Section 4.6.3, p. 461).
Jörg Arndt, Christoph Haenel: Pi. Algorithms, computers, arithmetic. 2nd Edition. Springer, Berlin 2000, ISBN 3-540-66258-8 , pp. 120-121.