Raising to a power without multiplying that many times

Compute x to the power of n, reported modulo 1000000007.

The modulus is there because the real answer is astronomically large: 2 to the power of a billion has about 300 million digits. Taking a remainder at every step keeps the numbers small without changing the answer, since a remainder survives multiplication.

Worked example#

2 to the power of 10 is 1024.

3 to the power of 5 is 243.

The idea#

Multiplying x by itself n times takes n multiplications. With n around a billion, that is a billion multiplications and the judge stops you.

The way out is one observation:

x to the n  =  (x to the n/2)  squared,        when n is even
            =  (x to the n/2)  squared  ×  x,  when n is odd

Compute the half once and square it. Do not compute it twice, which is the mistake that turns this back into n multiplications wearing a disguise:

half = power(x, n / 2)        # once
return half * half            # then square it

Each step halves n, so it finishes in about log n multiplications. For a billion that is thirty, not a billion.

Why the base case is 1#

x to the power of zero is 1, and that is not a convention chosen to be tidy. It is the value that makes the squaring work: one more halving of an exponent of 1 gives 0, and the answer has to be the multiplicative identity for 1 × 1 × x to come out as x.

The recursion is genuinely worth it here#

Most of the recursions you have written could have been loops. This one can too, by reading the bits of n, but the recursive version is the one that states the idea: the answer for n is the answer for n/2, squared. Writing it that way first and converting later is the right order.

Constraints#

• 0 <= x <= 1000000000
• 0 <= n <= 1000000000