How to explain this algorithm for calculating the power of a number?

Question

I am currently reading Skiena's "The Algorithm Design Manual".

He describes an algorithm for calculating the power of a number i.e. calculate a^n.

He begins by saying that the simplest algorithm is simply a*a*a ... *a, so we have a total of n-1 calculations.

He then goes on to say that there is an optimisation for that, and asks us to recognise that:

n = n/2 + n/2

and we can also say that

a^n = ((a^n/2)^2)  (a to the n equals a to the n over 2, squared)

Which I understand so far. From these equations, he deduces an algorithm which performs only O(lg n) multiplications.

function power(a, n)
  if (n = 0) 
    return(1)

  x = power(a,n/2)

  if (n is even)       
    return(x^2)
  else             
    return(a*x^2)

It appears that x must be the current value computed so far. But still after reading this several times, I don't understand how from those equations he designed this algorithm, or even how it works. Can anyone explain?

Answer 1

The concept is simple. For example, compute the value of 3⁸

You can use the obvious way which is 3⁸ = 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 which takes 7 multiplication operations. Or there is a better way.

Let say that

• If we know the value 3⁴, we can compute 3⁸ only in one multiplication operation, but we don't know the value of 3⁴
• If we know the value of 3², we can compute 3⁴ in one multiplication operation.
• And finally, we know that 3² can be easily compute by 3 x 3.

Going backward, it only takes 3 multiplication to compute 3⁸ instead of 7

Here is the clearly view of the process:

   32 = 3 x 3 = 9
   34 = 32 x 32 = 9 x 9 = 81
   38 = 34 x 34 = 81 x 81 = 6,561

Then, there is another problem, what if the power is odd number. For example: 3⁹, how to deal with it? You can either do this

   39 = 3 x 38   or
   39 = 3 x 34 x 34

---

Lets call the algorithm that continuously multiple the number as Method A, and algorithm that continuously divide the power by two as Method B. How good is method A comparing to method B? For a small number such as 3⁸, there is not much significant improvement, even those, we minimize the number of multiplication, but we also slightly increase the number of division operation.

So for 3⁸

               Multiplication   Division
   Method A:        7              0
   Method B:        3              3

However, for the larger power, for example: 3^{4,294,967,296}

               Multiplication   Division
   Method A:   4,294,967,295       0
   Method B:       32              32

The difference is huge.