How would you compute powers?

Okay, I admit, it blew me away. I just love when I learn more efficient ways to implement elementary algorithms. At first, I answered this question in the most straightforward way. Check it out in the snippet below:

    /** power: linear implementation */
    private static int power(int x, int n) {
        int result = 1;
        for(int i = 0; i < n; ++i) {
            result *= x;
        }
        return result;
    }

Later, I learned a better (and ingenious) implementation while reading this book. The idea is beautifully simple: instead of the iteration, define a recursive function F(x, n) = { if n = 0 return 1; if n is even return f(x*x, floor(n/2)); if n is odd return x*f(x*x, floor(n/2)) }. That’s it! The implementation runs in logarithmic time, which can be proved by solving the recurrence relation derived from F (using repeated substitution). Check out the Java implementation below.

    /** power: logarithmic implementation */
    private static int power(int x, int n) {
        if(n == 0) {
            return 1;
        } else if(n % 2 == 0){
            return power(x*x, n/2);
        } else {
            return x * power(x*x, n/2);
        }
    }

Advertisement