Behind the Algorithms:
Sometimes a program needs to calculate a number raised to an integer power. That’s not hard if the power is small. For example, 7^3 is easy to evaluate by multiplying 7 \times 7 \times 7 = 343.
For larger powers such as 7^{102,187,291} , however, this would be fairly slow.
.
Fortunately, there’s a faster way to perform this kind of operation. This method is based on the fact that you can quickly calculate powers of a number that are themselves powers of 2.
For example, consider the value A^1 , which is simply A . From that, you can calculate A^2 because A^2 = A^1 \times A^1. Similarly, you can calculate A^4 because A^4 = A^2 \times A^2 . You can then calculate A^8 because A^8 = A^4 \times A^4 , and so on.
Now that you know how to calculate some large powers of A quickly, you need to figure out how to assemble them to produce any large power. To do that, consider the binary representation of the exponent. Each of the digits in that representation correspond to the powers of A: A^0, A^1, A^2, A^4, and so on.
For example, suppose you want to calculate A^{18}. The binary representation of 18 is 10010. Reading the binary digits from right to left, the digits correspond to the values A^0, A^1, A^2, A^4 , and A^8. You can use those special powers of A to calculate A^{18}. In this case, A^{18} = 0\times A^0+ 1\times A^1+ 0\times A^2+ 0\times A^4+1\times A^8
That’s the basis for the fast exponentiation algorithm. You build bigger and bigger powers of A and use the binary digits of the exponent to decide which of those should be multiplied into the final result.
The following pseudocode shows the algorithm:
// Perform the exponentiation.
Integer: Exponentiate(Integer: value, Integer: exponent)
Integer: result = 1
Integer: factor = value
While (exponent != 0)
If (exponent Mod 2 == 1) Then result *= factor
factor *= factor
exponent /= 2
End While
Return result
End Exponentiate
The algorithm sets result to 1. Initially, this holds value to the 0^{th} power, which is 1 for any value.
The algorithm also sets factor equal to value . This will represent the powers of value . Initially, it holds value to the first power.
The code then enters a loop that executes as long as the exponent is not zero. Inside the loop, the algorithm uses the modulus operator to see whether the exponent is odd. If it is odd, then its binary representation ends with a 1. In that case, the algorithm multiplies result by the current value of factor to include that power of value in the result.
The algorithm then multiplies factor by itself so that it represents value raised to the next power of 2. It also divides the exponent by 2 to remove its least significant binary digits.
When the exponent reaches zero, the algorithm returns the result.
The algorithm’s loop executes once for each binary digit in the exponent. If the exponent is P, then it has log _{_2} (P) binary digits, so the algorithm runs in O(log \space P) time. That’s fast enough to calculate some pretty large values. For example, if P is 1 \space milion , log (P) is about 20, so this algorithm uses about 20 steps.
[1]. Essential Algorithms- A practical approach to computer algorithms using Python and C# By Rod Stephens.
