Fast power

Why this matters

Many programs raise a number to a power. Interest on a loan grows by a factor each year. Public-key encryption, which keeps online payments private, depends on raising very large numbers to very large powers, modulo another number (the remainder after dividing by it). If the program multiplies one step at a time, a power with an exponent of a million costs a million multiplications. This lesson shows a method that needs 27 multiplications for that same exponent, as the measurements below show.

The method is a direct use of recursion. The recursion lesson in this module showed how a problem can be split into a smaller problem of the same kind. Here, the smaller problem is a power with half the exponent. The same idea can also be written as a loop that reads the exponent one bit at a time. Both versions are shown below.

What x to the power n means

Write x for the number being raised, and n for the exponent. The value x to the power n is x multiplied by itself n times. For example, 2 to the power 10 is 2 multiplied by itself 10 times, which is 1024. The exponent n is a whole number of zero or more in this lesson. The power with exponent 0 is 1, because a product of no factors is 1.

The slow way follows the definition exactly. Start with 1, multiply by x once for each step of the exponent, and stop when the steps are used up.

The output is:

2^10 = 1024
multiplications = 10

This works, and for a small exponent it is fine. For n equal to 1,000,000 it does 1,000,000 multiplications. The goal of this lesson is to reduce that number without changing the answer.

The key idea: halve the exponent

Here is the fact that makes the speed-up possible. For any whole number n that is even, x to the power n is the same as x to the power n / 2, multiplied by itself. For example, 3 to the power 8 is the same as (3 to the power 4) times (3 to the power 4), because 4 plus 4 is 8. Once the power of 4 is known, one more multiplication gives the power of 8.

Now take the power of 4 in the same way. 3 to the power 4 is (3 to the power 2) times (3 to the power 2). 3 to the power 2 is 9. So 3 to the power 4 is 81, and 3 to the power 8 is 81 times 81, which is 6561.

Count the steps. Starting from 3, one squaring gives 9, which is 3 to the power 2. A second squaring gives 81, which is 3 to the power 4. A third squaring gives 6561, which is 3 to the power 8. Three multiplications produce the answer. The slow way needs 8 multiplications for the same answer. Each squaring doubles the exponent, so the number of squarings grows like the number of times you can halve the exponent, and that count is about log n.

The word "log" here means the base-2 logarithm, which is the number of times you can halve a number before it reaches 1. For example, halving 1000 gives 500, 250, 125, 62, 31, 15, 7, 3, 1. That is 9 halvings, and 2 to the power 10 is 1024, so the log base 2 of 1000 is a little less than 10. The exact rule is not important for coding. What matters is that the number of steps is small even when the exponent is large.

The odd case needs one extra step. Take 3 to the power 7. The exponent 7 is odd, so 3 to the power 7 is 3 times 3 to the power 6. Then 3 to the power 6 is (3 to the power 3) squared, and 3 to the power 3 is (3 to the power 1) squared times 3 again. Every odd exponent gives one extra multiplication by x.

So the rule has two cases.

If n is 0, the answer is 1.

If n is even, square the power of n / 2.

If n is odd, square the power of n / 2, then multiply by x once more.

The recursive version

The rule above maps directly onto a recursive function. The function asks for the power of n / 2, which is a smaller exponent, and then applies the rule to that answer. Division by 2 in C++ for whole numbers drops the remainder, so 7 divided by 2 is 3. That is the half the odd case needs.

The output is:

2^10 slow=1024 recursive=1024
3^13 slow=1594323 recursive=1594323
5^0 = 1
5^1 = 5
5^2 = 25
5^3 = 125
5^4 = 625
5^5 = 3125

Trace one call by hand so the code makes sense. Call fast_power_rec(5, 3). The exponent 3 is not 0, so the function first computes fast_power_rec(5, 1). That call computes fast_power_rec(5, 0), which returns 1. Then it squares 1 to get 1, and since 1 is odd it multiplies by 5, returning 5. Back in the call for exponent 3, the half is 5. Squaring gives 25, and since 3 is odd it multiplies by 5, returning 125. Each call does at most two multiplications, and each call handles an exponent about half the size of the one above it.

The function calls itself about log n times. The depth of the calls is the number of halvings, and the work at each level is at most two multiplications. For n equal to 1,000,000,000 the depth is 30, because 2 to the power 30 is about 1.07 billion. The measuring program later in this lesson counts the multiplications for both versions.

The iterative version: read the bits of n

A computer stores a whole number in binary, which uses only the digits 0 and 1. The exponent 10 is 1010 in binary. Read from the right, its bits are 0, 1, 0, 1. Each 1 bit means "this power of two is part of the exponent." The number 10 is 2 plus 8, so 2 to the power 10 is 2 to the power 2 times 2 to the power 8.

The iterative version uses this directly. It keeps two values. base holds x raised to a power of two, starting at x to the power 1. result collects the product of the bases that match a 1 bit. Each step looks at the lowest bit of n, multiplies result by base if that bit is 1, shifts n one bit to the right, and squares base.

The output is:

2^10 = 1024
multiplications = 5

Here is each step for n equal to 10, with x equal to 2.

In step 2, the bit is 1, so result becomes 1 times 4, which is 4. In step 4, the bit is 1, so result becomes 4 times 256, which is 1024. The bit pattern 1010 told the loop to use 2 to the power 2 and 2 to the power 8.

The check if (n == 0) break; is the only exit from the loop. It sits before the squaring, so base is never squared after the last bit has been used.

The iterative version and the recursive version do the same work. For n equal to 10 the recursive version made 6 multiplications, and the iterative version made 5. The recursive version squares 1 once more at the bottom of the calls, when the exponent is 1. The loop does not do that squaring. Both are about log n.

Measuring the work

The program below counts multiplications for four exponents. It runs the slow method only for the smaller ones, because the slow method for a million or a billion would take too long to be useful here.

The output is:

n=10 recursive=6 iterative=5 slow=10
n=1000 recursive=16 iterative=15 slow=1000
n=1000000 recursive=27 iterative=26 slow=1000000
n=1000000000 recursive=43 iterative=42

For a billion, the slow method would need a billion multiplications. The fast method needs 42. The count grows slowly because each doubling of the exponent adds only one squaring and sometimes one more multiplication.

The count is the measure here. The printed values are not checked in this program, and for large exponents they wrap around, as the overflow mistake below explains.

A practical use: powers with a modulus

Many real uses of powers do not want the full answer, which can be huge. They want the answer modulo a number, which means the remainder after dividing by it. A common choice is 1,000,000,007, a prime that programming contests often use.

The fix is simple. After each multiplication, take the remainder. The final remainder is the same as if the full answer had been computed and then divided. Every number stays below 1,000,000,007. The product of two such numbers is below about 10 to the power 18, which fits in a 64-bit unsigned integer.

The output is:

2^1000000 mod 1000000007 = 235042059
3^200 mod 1000000007 = 136318165
7^123 mod 13 = 5

Python has a built-in pow function with a third argument for the modulus. Running pow(2, 1000000, 10**9 + 7) in Python returns 235042059, the same value. Two implementations agreeing is a good check for code like this. The method used by Python is the same idea, though.

Common mistakes

Leaving out the base case

The recursive version must stop when the exponent is 0. Without that check the function calls itself forever, because n / 2 for n equal to 1 is 0, and 0 divided by 2 is still 0. The next program removes the check.

#include <cstdint>
#include <iostream>
using namespace std;
 
uint64_t no_base(uint64_t x, uint64_t n) {
    uint64_t half = no_base(x, n / 2);
    return half * half * (n % 2 == 1 ? x : 1);
}
 
int main() {
    cout << no_base(2, 5) << "\n";
}

Compile it with g++ -std=c++20 -Wall -o norecurse norecurse.cpp. The compiler prints this warning:

norecurse.cpp:5:10: warning: infinite recursion detected [-Winfinite-recursion]
    5 | uint64_t no_base(uint64_t x, uint64_t n) {
      |          ^~~~~~~
norecurse.cpp:6:28: note: recursive call
    6 |     uint64_t half = no_base(x, n / 2);
      |                     ~~~~~~~^~~~~~~~~~

When the program runs, it ends with exit status 139. Exit status 139 means the program was stopped by a segmentation fault, which is a crash caused by touching memory the program should not use. Here the memory that runs out is the stack, where each recursive call keeps its own data. The fix is the first line of the function, if (n == 0) return 1;.

Leaving out the extra multiplication for odd exponents

The odd case multiplies by x once more. If that step is missing, every odd exponent loses a factor of x. The next program has the even case only.

The output is:

3^1 = 1
3^7 = 1
3^8 = 1

The correct values are 3, 2187 and 6561. The program prints 1 for every one of them, because the odd exponents never get their extra factor and the error carries into every even exponent that is built from them. No error is printed. Checking a few small powers by hand is the simplest way to catch this.

Overflow with int

Plain int has a limit of about 2.1 billion, which is 2 to the power 31 minus 1. A power grows very quickly, so 3 to the power 40 does not fit. A naive loop with int will give a wrong answer. Compile with -fsanitize=undefined to make the compiler's runtime check report the problem. The program below multiplies 3 by itself with int.

Compile and run it with:

g++ -std=c++20 -Wall -fsanitize=undefined -o ov ov.cpp
./ov

The output is:

ov.cpp:6:40: runtime error: signed integer overflow: 1162261467 * 3 cannot be represented in type 'int'
1162261467
689956897

The message names the exact multiplication that does not fit. The value 3 to the power 19 fits, and the program prints it. The next multiplication overflows, and the program continues with a wrong number, 689956897, which is not 3 to the power 40. Without the sanitizer flag the program prints the wrong number and gives no message at all.

The unsigned 64-bit type used in the other programs in this lesson avoids this error message, but it does not avoid wrong answers. Unsigned arithmetic wraps around when the result is too big, so it keeps only the low 64 bits. The true value of 3 to the power 1000 has 478 digits, and the 64-bit result is a small number that is not that value. Use the modulus version when the answer must be exact modulo a number, and use a big-number type when the full answer is needed.

Practice

Exercise 1. Using the recursive function, how many multiplications does fast_power_rec(5, 6) make?

Show the answer

It makes 5 multiplications. The call for exponent 6 is even, so it squares the power of 3, which is 1 multiplication. The call for exponent 3 is odd, so it squares the power of 1 and then multiplies by 5, which is 2 multiplications. The call for exponent 1 is odd too, so it squares 1 and then multiplies by 5, which is 2 more. The call for exponent 0 returns 1 and does no multiplication. Adding them up gives 1 + 2 + 2 = 5.

Exercise 2. How many multiplications does the iterative version make for n equal to 8 and x equal to 2? What about n equal to 16?

Show the answer

It makes 4 multiplications for n equal to 8, and 5 for n equal to 16. The bit pattern of 8 is 1000, which has three squarings and one multiplication. The pattern of 16 is 10000, which has four squarings and one multiplication. In general, when n is 2 to the power k, the loop makes k plus 1 multiplications.

Exercise 3. Compute 7 to the power 123 modulo 13. Check your answer with Python.

Show the answer

The answer is 5. The Python check is pow(7, 123, 13), which also returns 5. You can also reason about it by hand: 7 to the power 12 is 1 modulo 13, so 7 to the power 123 is 7 to the power 3 modulo 13, which is 343, and 343 modulo 13 is 5.

Exercise 4. The iterative loop in this lesson has no condition in its while line, so if (n == 0) break; is its only exit. Explain what would happen if you deleted that check, and why.

Show the answer

The loop would never end. After the last bit is used, n is 0, so the if (n & 1) test is always false, and nothing else changes n or leaves the loop. The program would run forever. The break check is the only thing that stops it.

Exercise 5. Write the recursive rule in your own words for a function that computes x to the power n, then explain why the rule needs only about log n levels of calls.

Show the answer

When n is even, the power is the power of n / 2 squared. When n is odd, it is that squared value times x. Each call passes half of the exponent down, so the exponent reaches 0 after about log n halvings, which means about log n levels of calls.

Summary

• The slow method multiplies x by itself n times, which takes n multiplications.
• Squaring the power of n / 2 gives the power of n, and an odd exponent needs one extra multiplication by x.
• The recursive version follows this rule and makes about log n levels of calls.
• The iterative version reads the bits of n from the lowest bit upward, and it skips the last squaring.
• For a modulus, take the remainder after each multiplication so that every number stays small enough for the type.
• Check a few small powers by hand, because a missing base case crashes the program and a missing odd step gives wrong answers with no message.