Exponentiation in logarithmic time

Question

• Input: Real number y and Integer number x
• Output: x^y
• Constraint: Must be done in O(log(y)) time.

Notice that O(log(y)) is O(length-of(y)).

public static double expon(double x, int y){
    double result = 1.0;

    double part = x;
    for (int i = 0; i < 32; i++){
        if (((y >> i) & 1) == 1){
            result *= part;
        }
        part *= part;
    }   

    return result;
}

Answer 1

Your code is lacking comments that explain the why, ideally every non-trivial math programme should include a brief description of the algoritmh used.

Answer 2

I'd try to make your code more readable by giving a meaningful name to the variables you use. What about changing the signature of your method to

public static double exponentiate(double base, int exponent)

I think it is worth it, even if you're implementing a simple mathematical function like this one.

I'd also try to make it clear what you're doing with the ((y >> i) & 1) == 1 expression. What about introducing an isBitSet variable? I think introducing it (or an equivalent bool isByteSet(int number, int position) function) would make your code more readable. I'd also rename part to something like candidateFactor, which would make it clear that you're computing the factor corresponding to each binary digit and deciding whether to use it or not according to isBitSet.

I'd also recommend you to do some validation of your input values. What happens if you get passed a negative value for exponent? You can either make it an exceptional case and throw an IllegalArgumentException or handle it knowing that x^y = 1/(x^(-y))

Answer 3

Your style seems to be consistent. The code is acceptably clear.