
So the answer is we don't need 20 multiplications; we only need 4.

And the property we're taking advantage of is that X to the 2A is equal to X to the A squared.

That means we can break 2 to the 20 down into parts

it's equal to 2 to the 10th squared

which is equal to 2 to the 5 squared squared

which is equal tonow 2 to the 5 is not divisible by 2

so that's equal to 2 to the 4 times 2 squared and squared.

And so the number of multiplications

well what we're computing is each square involves a multiplication

so there's 1 multiplication there, there's 1 multiplication there,

there's 1 multiplication there, and there's 1 multiplication there

so 4 total multiplications.

So this does not scale exponentially in the size of the power.

So this means computing A to the N power requires

on the order of log N multiplications.

In terms of the size of N, that means it's linear

in terms of the number of bits needed to represent the power.