Pow (x, n)

Naturally we will think of bisection and use recursion to get the result.

let k = n / 2;
let l = n - 2 * k;
thus 2 * k + l = n;
Recursively solve p1 = pow(x, k) and p2 = pow(x, l), and the solution is p1 * p1 * p2 if n > 0 and the reciprocal of that if n < 0.


Update: 2015 - 02 - 03
If n is an odd number, l will be 1. If n is an even number, l will be 0.

public class Power {
    public double pow(double x, int n) {
        if (n == 0)
            return 1.0;
        if (n == 1)
            return x;
        boolean isReciprocal = false;
        if (n < 0)
        {
            isReciprocal = true;
            n = - n;
        }
        int k = n / 2;
        int l = n - 2 * k;
        double p1 = pow(x, k);
        double p2 = pow(x, l);
        return isReciprocal == true ? (1 / (p1 * p1 * p2)) : (p1 * p1 * p2);
    }
}