Find power of a number

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

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\$. ;-)

StackExchange Code Review Q#39190, answer score: 7