Find power of a number

Question

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));
    }
}

Answer 1

This can get worse than \$\operatorname{O}(\log \verb~pow~)\$. [Remark: in \$\operatorname{O}\$-notation, the base of an logarithm is irrelevant, since it represents only a multiplication with a constant]

Let \$\verb~pow~ = 2^n - 1\$ for some \$n\$. Then you're computing the following powers:

• \$1, 2, 4,\dots, 2^{n-1}\$, followed by a function call for \$\verb~pow~ = (2^n-1) - 2^{n-1} = 2^{n-1} - 1\$;

• \$1, 2, 4,\dots, 2^{n-2}\$, followed by a function call for \$\verb~pow~ = (2^{n-1}-1) - 2^{n-2} = 2^{n-2} - 1\$;

• \$1, 2, 4,\dots, 2^{n-3}\$, followed by a function call for \$\verb~pow~ = (2^{n-2}-1) - 2^{n-3} = 2^{n-3} - 1\$;
  ...

All in all, \$n + (n-1) + ... + 1 = n(n+1)/2\$ calls of the inner loop. In terms of pow, this is \$\operatorname{O}(\log^2 \verb~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, x^2, x^4, x^8,...\$ and multiplying with them if the corresponding binary digit of pow is equal to \$1\$. This has \$\operatorname{O}(\log \verb~pow~)\$ steps.

By the way, I don't think \$2^7\$ is expected to be \$16\$. ;-)

Answer 2

Bug #1: 0.0ⁿ where n > 0 is equal to 0.0, and not 1 as you have in your code if (x == 0) return 1; (although 0⁰ is 1, not 0, and 0.0ⁿ 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, 2⁷ 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);