Calculate x ^ y in O(log n) [closed]

Question

Interview question:

Calculate x ^ y in O(log n)

There are different answers like "Use the Indian Power algorithm" or

double power(double x, int y) 
{
    if(y == 0) return 1;

    double d = power(x, y/2);

    if(y%2 == 0) return d*d;
    else return x*d*d;
}

1. is it a correct answer?

2. is there any better way of writing a code for this question?

Answer 1

This is called Exponentiation by Squaring. As far as implementation goes, it is a matter of taste. Your recursive implementation is good, but non-recursive implementations (from the link above) may look a little cleaner to people who do not like recursion or erroneously believe that it is somehow "wasteful" or "slow".

Answer 2

Questions about basic mathematical operations, and questions about computational complexity, are usually answered quickly by Wikipedia.

Exponentiation: Efficient computation of integral powers

In general, the number of multiplication operations required to compute bn can be reduced to Θ(log n) by using exponentiation by squaring or (more generally) addition-chain exponentiation. Finding the minimal sequence of multiplications (the minimal-length addition chain for the exponent) is a difficult problem for which no efficient algorithms are currently known (see Subset sum problem), but many reasonably efficient heuristic algorithms are available.

Answer 3

Let's analyse it:

power is called (via recursion) as many times as the original y is divisible by 2 (that is the largest number, k, such that 2^k < y). This means that the number of calculations is roughly k=log_2(2^k)=log_2(y)~=log(y), so it is a correct answer.

The answer to the "better way" depends on what counts as "better"

Answer 4

Here's the way to do it:

let's say you wanna to 2^1024, that would take ... wait for it ... 11 multiplications

you do it this way

2*2 = 2^2
2^2 * 2^2 = 2^4
2^4 * 2^4 = 2^8
2^8 * 2^8 = 2^16
....
2^512 * 2^512 = 2^1024

so basically, you only need to write your exponent in base 2 and get all the relevant multiplications