Exponentiation by squaring
The binary exponentiation (also called Square & Multiply ) is an efficient method for the calculation of natural powers, ie expressions of the form with a natural number.
This algorithm has already been discovered around 200 BC in India and is written down in a book called Chandah - sûtra.
- 3.1 Example
- 3.2 Pseudocode
- 5.1 Example
Motivation
To calculate, you can either calculate ( three multiplications ) or, ( two multiplications ), ie.
Also can be computed efficiently, other integer powers by " repeated squaring and multiplying random ".
This saving of multiplications works for both real numbers as well as for real-valued matrices, elliptic curves, and any other semigroups.
Algorithm
- Conversion into the corresponding binary representation.
- Replacing each 0 by Q and each 1 by SQM
- Now Q is interpreted as an instruction for squaring and M as an instruction to multiply.
- Thus, to the right read the resulting string from left is a provision for the calculation of. You start with 1, squaring for each Q read the previous intermediate result and multiply it for each thread M with.
Since the binary representation of always begins with the number 1 - and so also begins the statement with QM - results for the first statement QM in any case, the intermediate result. For this reason, there is a slightly simplified variant in which the first statement is replaced by QM.
Example
Let k = 23 The binary representation of 23 is 10111th Therefore, under the substitutions QM QM QM QM Q After the strike of the leading QM QM QM pair one has Q SQM From this we can now read off that the calculation process look as follows has: " squaring, squaring, multiply by x, squaring, multiply by x, squaring, multiply by x ".
Formal sees the whole thing like this: or written successively:
You can see the example that you can save some computation steps using the binary exponentiation. Instead of 22 multiplications only 7 are required by four squared and multiplied three times with x.
Pseudocode
The algorithm is presented in two versions. Version 1 uses an if statement to multiply in the appropriate places. Option 2 builds the if condition implicitly in the arithmetic expression.
/ / Compute x ^ k / / B ... binary representation of k / / Res ... result of the calculation bin_exp function ( 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 / / Compute x ^ k / / B ... binary representation of k / / Res ... result of the calculation bin_exp function ( x, b) res = 1 for i = n .0 res = res ^ 2 * x ^ { b_i } end -for return res end -function alternative algorithm
One can make the procedure for calculation by hand also so that you initially often enough squares the base and then multiplying the right numbers together. Then it is similar to the Russian peasant multiplication, which returns the multiplication of two numbers on halving, doubling and adding numbers.
Do this by writing the exponent on the left and the right base. The exponent is halved gradually (the result is rounded down) squared and the base gradually. It deletes the rows with straight exponents. The product is not painted right numbers is the required potency.
Example
Pseudocode
Unlike the previous approach, the required powers of be multiplied up right here. This variant is useful when the exponent is not explicitly present in the binary representation. To illustrate the equality can be considered
Is to be determined without having present in the binary representation
/ / Compute x ^ k / / res ... result of the calculation bin_exp function res = (x, k) res = 1 aktpot = x while k> 0 if k mod 2 == 1 res = res * aktpot end -if aktpot = aktpot ^ 2 k = k DIV 2 / / Integer division (the result is rounded down) end -while return res end -function Recursive algorithm with derivation
Every natural number can be uniquely decomposed into, where. Due to the power laws obtained
The last expression contains only
- Exponentiation with an exponent as is only about half the size, which can be calculated recursively using the same algorithm,
- Squaring,
- A multiplication,
- Potentiation with 0 or 1 as an exponent.
A direct implementation in Haskell would look like the following.
A ^ 0 = 1 a ^ 1 = a a ^ 2 = a * a a ^ n = (a ^ m ) ^ 2 * a ^ b where ( m, b ) = n ` 2 ` divmod The ^ function that is defined here is therefore based on an existing * for multiplication, divmod for the elimination of the lowest binary digit of the exponent and, recursively, itself
Gering joining optimizations, such as the transformation into a tail-recursive variant, essentially lead to the above imperative algorithms.
Binary modulo exponentiation
When computing modulo a natural number, a slight modification is applicable, that prevents the calculated numbers are too big: You form after each squaring and multiplying the rest The previously presented algorithms can be easily extended by this module operations.
Example
Runtime Analysis
With the simple and slow potentiation of multiplications are needed. At the " Square & Multiply" the loop is executed only once ( in this case corresponds approximately to the length of the number in the binary representation ). In each loop there is a squaring ( the first squaring can be neglected ) and possibly a multiplication. Asymptotically operations (possibly long integer operations ) is required, whereas strike operations in the simple exponentiation to book. called an asymptotic upper bound for the runtime behavior of the algorithm. How easy to see that the "square -and- multiply " method is much more efficient than the simple process. This reduced demand on computing power is enormous with large bases and exponents.
Similar algorithms
The Binary exponentiation must not necessarily be the " multiplikationssparendste " Calculation of potency. To compute, for example, you can either according to binary exponentiation
Calculate (6 multiplications ), or
With
( a total of 5 multiplications ).