A General Approach

We're now going to shift the problem a little. Instead of thinking about multiplications, we'll think about additions. When we multiply 2a2b2^a 2^b, the result is 2a+b2^{a + b}: the sum of the exponents. So we want to find an addition chain that starts at 1 and ends at our target exponent. An addition chain is a sequence of numbers, each of which is the sum of two previous numbers in the chain. 1 → 2 → 4 → 8 is one addition chain: another would be 1 → 2 → 3 → 5 → 8 (seems familiar somehow...).

Let's say we want to compute 2202^{20}. In other words, we want an addition chain for 20: that will give us a series of steps to compute 2202^{20} using powers of two we already have. As it turns out, getting the optimal addition chain for large numbers is very challenging—there are no fast algorithms that always get the best answer. But we don't need a perfect approach that never fails to save a multiplication: we just want to do better than 1 + 1 + 1 + 1 + ... which is what we had before, computing MnM^n by doing M×M×M×…M \times M \times M \times \dots

Powers of 2 are easy to make in addition chains. What if we can use that?

Specifically, let's start our chain by going 1 → 2 → 4 → 8 → 16, ending at the last power of 2 before 20. Adding the previous number to itself is the fastest our chain can grow, so this makes intuitive sense: we want to get close to 20 quickly to get a short chain. Now, is there any way to represent 20 as the sum of powers of 2?

A General Approach

We're now going to shift the problem a little. Instead of thinking about multiplications, we'll think about additions. When we multiply 2a2b2^a 2^b, the result is 2a+b2^{a + b}: the sum of the exponents. So we want to find an addition chain that starts at 1 and ends at our target exponent. An addition chain is a sequence of numbers, each of which is the sum of two previous numbers in the chain. 1 → 2 → 4 → 8 is one addition chain: another would be 1 → 2 → 3 → 5 → 8 (seems familiar somehow...).

Let's say we want to compute 2202^{20}. In other words, we want an addition chain for 20: that will give us a series of steps to compute 2202^{20} using powers of two we already have. As it turns out, getting the optimal addition chain for large numbers is very challenging—there are no fast algorithms that always get the best answer. But we don't need a perfect approach that never fails to save a multiplication: we just want to do better than 1 + 1 + 1 + 1 + ... which is what we had before, computing MnM^n by doing M×M×M×…M \times M \times M \times \dots

Powers of 2 are easy to make in addition chains. What if we can use that?

Specifically, let's start our chain by going 1 → 2 → 4 → 8 → 16, ending at the last power of 2 before 20. Adding the previous number to itself is the fastest our chain can grow, so this makes intuitive sense: we want to get close to 20 quickly to get a short chain. Now, is there any way to represent 20 as the sum of powers of 2?