Let's imagine we're trying to compute 24=162^4 = 16. Our above approach computes

2×2×2×22 \times 2 \times 2 \times 2

which requires three multiplications. In general, it requires n−1n - 1 multiplications to compute an nthn^{th} power.

The trick is realizing that we don't have to just multiply by 22 here. Here's a different approach:

2×2=44×4=16 \begin{aligned} 2 \times 2 &= 4\\ 4 \times 4 &= 16 \end{aligned}

We've saved a multiplication by using 44 twice!

OK, I'll admit this example is pretty lame. You probably didn't need me to tell you that 24=162^4 = 16. But this approach scales far better than the old one.

For example, to compute 2322^{32}, we can use the following series of multiplications:

2×2=4=224×4=16=2416×16=256=28256×256=65,536=21665,536×65,536=4,294,967,296=232 \begin{aligned} 2 \times 2 &= 4 &= 2^2 \\ 4 \times 4 &= 16 &= 2^4 \\ 16 \times 16 &= 256 &= 2^8 \\ 256 \times 256 &= 65,536 &= 2^{16} \\ 65,536 \times 65,536 &= 4,294,967,296 &= 2^{32} \\ \end{aligned}

The old approach required 31 multiplications—now we can do it in 5.

Each multiplication doubles the exponent, so in the best case we can compute 2n2^n in log⁡2n\log_2 n multiplications. That's an exponential speedup over our old approach!

You might have a question at this point: how do we adapt this approach to work with exponents that aren't powers of two? How would we compute 2202^{20}, for example?

Let's imagine we're trying to compute 24=162^4 = 16. Our above approach computes

2×2×2×22 \times 2 \times 2 \times 2

which requires three multiplications. In general, it requires n−1n - 1 multiplications to compute an nthn^{th} power.

The trick is realizing that we don't have to just multiply by 22 here. Here's a different approach:

2×2=44×4=16 \begin{aligned} 2 \times 2 &= 4\\ 4 \times 4 &= 16 \end{aligned}

We've saved a multiplication by using 44 twice!

OK, I'll admit this example is pretty lame. You probably didn't need me to tell you that 24=162^4 = 16. But this approach scales far better than the old one.

For example, to compute 2322^{32}, we can use the following series of multiplications:

2×2=4=224×4=16=2416×16=256=28256×256=65,536=21665,536×65,536=4,294,967,296=232 \begin{aligned} 2 \times 2 &= 4 &= 2^2 \\ 4 \times 4 &= 16 &= 2^4 \\ 16 \times 16 &= 256 &= 2^8 \\ 256 \times 256 &= 65,536 &= 2^{16} \\ 65,536 \times 65,536 &= 4,294,967,296 &= 2^{32} \\ \end{aligned}

The old approach required 31 multiplications—now we can do it in 5.

Each multiplication doubles the exponent, so in the best case we can compute 2n2^n in log⁡2n\log_2 n multiplications. That's an exponential speedup over our old approach!

You might have a question at this point: how do we adapt this approach to work with exponents that aren't powers of two? How would we compute 2202^{20}, for example?