exponential multiplication algorithm that runs in O(n) time?

Question

I am reading an algorithms textbook and I am stumped by this question:

Suppose we want to compute the value x^y, where x and y are positive integers with m and n bits, respectively. One way to solve the problem is to perform y - 1 multiplications by x. Can you give a more efficient algorithm that uses only O(n) multiplication steps?

Would this be a divide and conquer algorithm? y-1 multiplications by x would run in theta(n) right? .. I don't know where to start with this question

Answer 1

I understand this better in an iterative way:

You can compute x^z for all powers of two: z = (2^0, 2^1, 2^2, ... ,2^(n-1))

Simply by going from 1 to n and applying x^(2^(i+1)) = x^(2^i) * x^(2^i).

Now you can use these n values to compute x^y:

result = 1
for i=0 to n-1:
    if the i'th bit in y is on:
        result *= x^(2^i)
return result

All is done in O(n)

Answer 2

Apply a simple recursion for divide and conquer. Here i am posting a more like a pseudo code.

x^y :=
    base case: if y==1 return x;
        if y%2==0:  
            then (x^2)^(y/2;
        else 
            x.(x^2)^((y-1)/2);