Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Looking for optimization, smart tips and verification of complexity: O (log (base 2) power).

NOTE: System.out.println("Expected 16, Actual: " + Power.pow(2, 7)); is a typo. It correctly returns 128.

/**
 * Find power of a number.
 * 
 * Complexity: O (log (base 2) power) 
 */
public final class Power {

    private Power() { }

    /**
     * Finds the power of the input number.
     * @param x     the number whose power needs to be found
     * @param pow   the power  
     * @return      the value of the number raised to the power.
     */
    public static double pow(double x, int pow) {
        if (x == 0) return 1;
        return pow > 0 ? getPositivePower(x, pow) : 1 / getPositivePower(x,  -pow);
    }

    private static double getPositivePower(double x, int pow) {
            assert x != 0;
        if (pow == 0) return 1;

        int currentPow = 1;
        double value = x; 
        while (currentPow <= pow/2) {
            value = value * value;
            currentPow = currentPow * 2;
        }

        return value * getPositivePower(x, pow - currentPow);
    }

    public static void main(String[] args) {    
        System.out.println("Expected 6.25, Actual: " + Power.pow(2.5, 2));
        System.out.println("Expected 16, Actual: " + Power.pow(2, 7));
        System.out.println("Expected 0.25, Actual: " + Power.pow(2, -2));
        System.out.println("Expected -27, Actual: " + Power.pow(-3, 3));
    }
}
share|improve this question
1  
I assume you don't want to use the built-in java.lang.Math.pow function. –  ChrisW Jan 14 at 0:27

2 Answers 2

up vote 6 down vote accepted

This can get worse than O(log pow). [Remark: in O notation, the base of the logarithm is irrelevant, since it represents only a multiplication with the constant]

Let pow be 2n-1 for some n. Then you're computing powers

1, 2, 4,..., 2^{n-1},
(now called for pow = (2^n-1) - 2^{n-1} = 2^{n-1} - 1)
1, 2, 4,..., 2^{n-2},
(now called for pow = (2^{n-1}-1) - 2^{n-2} = 2^{n-2} - 1)
1, 2, 4,..., 2^{n-3},
...

All in all,

n + (n-1) + ... + 1 = n(n+1)/2

calls of inner loop. In terms of pow, this is O(log2 pow).

Instead, observe pow as a binary number. I don't do Java, so I'll just sketch this in C, which is quite like it.

double px = x; // current power of x
double result = 1;
while (pow > 0) {
    if (pow % 2) result *= px;
    pow /= 2;
    px *= px;
}

So, you are observing x, x2, x4, x8,... and multiplying with them if the corresponding binary digit of pow is equal to 1. This has O(log pow) steps.

By the way, I don't think 27 is expected to be 16. ;-)

share|improve this answer

Bug #1: 0.0n where n > 0 is equal to 0.0, and not 1 as you have in your code if (x == 0) return 1; (although 00 is 1, not 0, and 0.0n where n < 0 is NaN).

Bug #2: You very carefully have the test method:

System.out.println("Expected 16, Actual: " + Power.pow(2, 7));

But, 27 is actually 128.

At this point, I figure a vote-to-close, but, FYI:

Picking apart the core method getPositivePower(double, int) .... This is your code:

private static double getPositivePower(double x, int pow) {
        assert x != 0;
    if (pow == 0) return 1;

    int currentPow = 1;
    double value = x; 
    while (currentPow <= pow/2) {
        value = value * value;
        currentPow = currentPow * 2;
    }

    return value * getPositivePower(x, pow - currentPow);
}
  • Why do you need the assert? Sure, you can check the input value is correct, but, there is only one place to call the method, and it is a few lines above. There is no reason to assert everything.... you have to trust something somewhere, and in my opinion, this is overly cautious.
  • in the last line, you are either 1, or 0 powers short of your intended result, so why do you have to do a full recursion? Simply: `return value * (pow == currentPow ? 1 : x);
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.