Computing integer powers with a recursive divide-and-conquer algorithm

Question

I have implemented a recursive function to find m^n (m raised to the power n).

Now I want to implement the same function but by dividing the problem into two equal parts, like

m^n = m^(n/2) * m^(n/2) = ... (for even n like, m^2, m^4, m^6).

With the implementation below, if I give m = 2 and n = 4, my output is 4 while it should be 16.

public class Recursion {

  public static void main(String[] args) {
    System.out.println(pow(2, 4));
  }

  public static long pow(long m,long n) { 
    if (n > 0)
      return m * pow(m, ((n/2) - 1) * pow(m, ((n/2) - 1)));
    else
      return 1;
  }

}

You have an extra `-1` in your code but not your formula. The recursion should probably be something like `return pow(m, n/2) * pow(m, (n + 1)/2);` — Tavian Barnes, Aug 12 '14 at 15:34
you're going to have a problem any time `n` is odd because the resulting exponent will lose a 0.5 — Alnitak, Aug 12 '14 at 15:34
@TavianBarnes that's probably right, and might also avoid the "odd n" case, but he'd still need an "n == 1" case too or the right hand side of the recursion will never terminate. — Alnitak, Aug 12 '14 at 15:36
@Tavian Barnes **pow(m, n/2) * pow(m, (n + 1)/2)** is not working. — user3934003, Aug 12 '14 at 15:40
@TavianBarnes the `-1` probably came from the `m * pow`, i.e. he's already got `m ^ 1` on the LHS. — Alnitak, Aug 12 '14 at 15:48
Another problem I didn't notice until I reformatted the code a bit is that the second argument to `pow` is actually `((n/2) - 1) * pow(m, ((n/2) - 1))`, i.e. the first call to `pow` was not closed before the multiplication. I kept it in case the OP really had that problem in their code. — Tavian Barnes, Aug 12 '14 at 17:06

score 5 · Answer 1 · answered Aug 12 '14 at 15:44

5

public static long pow(long m,long n)
{ 
    if (n <= 0) {
        return 1; // Be lazy first
    } else if (n % 2 == 1) {
        return m * pow(m, n - 1); // Normal slow strategy
    } else { // n even
        long root = pow(m, n / 2); // Do not evaluate twice
        return root * root;
    }
}

answered Aug 12 '14 at 15:44

Joop Eggen

107,315
7
83
138

+1 nice clean solution! Good combination of the slow strategy for the odd case combined with only needing a single recursive call in the even case. – Alnitak Aug 12 '14 at 15:45
on second thoughts, I'm not so sure. This'll only be optimal if `n` is a power of two. In other cases it'll very quickly degenerate into the slower "odd" case for the majority of the recursive calls. – Alnitak Aug 12 '14 at 15:52
Yes, but on every iteration there is 50% chance to meet an even number, which has a logarithmic speed. And for an odd number the next recursion is even again. So you have at most (²log n) odd single products, and the speed is logarithmic. – Joop Eggen Aug 12 '14 at 16:02
+1, this algorithm is known as binary exponentiation and it's much faster than the OP's original one. – Tavian Barnes Aug 12 '14 at 16:05
@JoopEggen true, but the odd case is also equivalent to `root = pow(m, n / 2); return m * root * root` making that step logarithmic time too. – Alnitak Aug 12 '14 at 16:10
@Alnitak Which it will do inside the call to `pow(m, n - 1)`. So the same thing. Though you have a good idea: one could first calculate root*root and _then_ check if n is even (* 1) or odd (* m). – Joop Eggen Aug 12 '14 at 16:17
@JoopEggen yeah, that's what I've done in my answer, based on a combination of yours and sujithvm's ;-) – Alnitak Aug 12 '14 at 16:18
@JoopEggen FWIW, calculating 3^13 takes four recursive steps with my answer and 7 with yours – Alnitak Aug 12 '14 at 16:24
@JoopEggen oh dear - somehow sujihvm's method takes _twenty-five_ calls ! – Alnitak Aug 12 '14 at 16:27

Alnitak · Answer 2 · 2014-08-12T18:49:09.653

3

Based on a combination of two other answers here, I believe this is the optimal algorithm:

public static long pow(long m, int n)
{ 
    if (n <= 0) {
        return 1;
    } else if (n == 1) {
        return m;
    }

    int rem = n & 1;
    n >>= 1;

    if (rem == 0) {
        return pow(m * m, n);      // x^(2n) = (x^2)^n 
    } else {
        return m * pow(m * m, n);  // x^(2n+1) = x * ((x^2)^n)
    }
}

i.e. an immediate short-circuit for m^0 or m^1, and a single recursive call for other cases.

EDIT cleaned up slightly and now exactly follows the Wikipedia article on exponentiation by squaring which was algorithmically the same as my previous edit but is now improved by being the even-case being potentially tail recursive on languages that support it.

edited Aug 12 '14 at 18:49

answered Aug 12 '14 at 16:01

Alnitak

334,560
70
407
495

The last recursive call is not in tail position, you would need to add an accumulator parameter or something. Also what's `pow1`? – Tavian Barnes Aug 12 '14 at 16:51
@TavianBarnes it's the last expression in the function - that _should_ suffice. The accumulator trick should only be necessary to convert recursive functions in pure functional languages (e.g. erlang) to tail recursive. `pow1` was a copy&paste error from the version I had offline comparing two other answers. – Alnitak Aug 12 '14 at 18:44
The last expression is in fact a multiplication expression, not a function call. It's like you wrote `multiply(m, pow(m * m, n))`, which I hope you agree is not a tail call. – Tavian Barnes Aug 12 '14 at 18:46
@TavianBarnes oops, yes, you're right - the `rem == 0` case is (potentially) tail recursive but the odd case isn't. – Alnitak Aug 12 '14 at 18:48

sujithvm · Answer 3 · 2014-08-12T16:11:33.767

1

Try this, it computes by splitting into two parts as required. Also look at http://en.wikipedia.org/wiki/Exponentiation_by_squaring for other methods

class Main {

    public static void main(String[] args) {    
        System.out.println(pow(2, 4));    
    }

    public static long pow(long m, long n) {
        if (n > 1)
            return pow(m, (n / 2)) * pow(m, (n - (n / 2)));
        else if (n <= 0)
            return 1;
        else
            return m;
    }
}

edited Aug 12 '14 at 16:11

answered Aug 12 '14 at 15:40

sujithvm

2,351
3
15
16

This is missing the case for `n == 0`. – Tavian Barnes Aug 12 '14 at 15:41
@TavianBarnes fixed it now. Please check – sujithvm Aug 12 '14 at 15:42
+1 - `n - (n / 2)` is a good way of calculating the right-hand term given the rounding you'll get from the left-hand term. – Alnitak Aug 12 '14 at 15:53
Looks correct, but is somehow _really_ suboptimal?! I just traced it making _twenty five_ calls to itself to calculate 3^13 – Alnitak Aug 12 '14 at 16:28
I'm not sure how it happened but you've managed to make your algorithm O(2n) instead of O(log2 n) – Alnitak Aug 12 '14 at 16:38
I expect it's because of the double recursive calls to `pow` in the `n > 1` case. – Alnitak Aug 12 '14 at 16:45
@Alnitak that's exactly right. Exponents that are one less than a power of two will hit the slow case every time, giving an exponential algorithm instead of a linear one. – Tavian Barnes Aug 12 '14 at 16:49
@Alnitak Barnes yeah. Slowness is probably due to 2 recursive calls which might end up in computing same values again and again. Exponential squaring would perform better. Was focusing on fixing user3934003 's code as he wanted to split into 2 and compute using divide and conquer. – sujithvm Aug 12 '14 at 17:51

score 1 · Answer 4 · edited May 23 '17 at 12:15

This answer adds error reporting on invalid inputs and handles all corner cases:

public long pow(long base, long exponent) {
    if (exponent < 0) {
        if (base == 1) {
            return 1;
        } else if (base == -1) {
            return exponent % 2 == 0 ? 1 : -1;
        } else {
            throw new ArithmeticException("Negative exponent");
        }
    } else if (exponent == 0) {
        if (base == 0) {
            throw new ArithmeticException("0**0 is undefined");
        } else {
            return 1;
        }
    } else {
        long root = pow(base, exponent/2);
        long result = root * root;
        if (exponent % 2 != 0) {
            result *= base;
        }
        return result;
    }
}

Technically this computes the result truncated to fit in a long. To detect overflow, the multiplications should be replaced with something like this.

For a non-recursive solution, replace the final else-block with

long result = 1;
while (exponent != 0) {
    if (exponent % 2 != 0) {
        result *= base;
    }
    base *= base;
    exponent /= 2;
}
return result;

score 0 · Answer 5 · answered Aug 12 '14 at 15:41

if you add up you ms you have

1+n/2-1+n/2-1

which reduces to

n - 1

Also, you have misplaced a few parenthesis, so you are not actually multiplying where you think you are. You are multiply the result of pow((n/2) -1) to the partialnin your firstpow` call.

Computing integer powers with a recursive divide-and-conquer algorithm

5 Answers5