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
– Tavian Barnes, Commented Aug 12, 2014 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
– Alnitak, Commented Aug 12, 2014 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
– Alnitak, Commented Aug 12, 2014 at 15:36

Joop Eggen · Accepted Answer · 2014-08-12 15:44:33Z

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, 2014 at 15:44

Joop Eggen

110k8 gold badges89 silver badges142 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Alnitak Over a year ago

+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 Over a year ago

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.

Joop Eggen Over a year ago

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.

Tavian Barnes Over a year ago

+1, this algorithm is known as binary exponentiation and it's much faster than the OP's original one.

Alnitak Over a year ago

@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 · Accepted Answer · 2014-08-12 18:49:09Z

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, 2014 at 18:49

answered Aug 12, 2014 at 16:01

Alnitak

341k72 gold badges420 silver badges503 bronze badges

4 Comments

Tavian Barnes Over a year ago

The last recursive call is not in tail position, you would need to add an accumulator parameter or something. Also what's pow1?

Alnitak Over a year ago

@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.

Tavian Barnes Over a year ago

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.

Alnitak Over a year ago

@TavianBarnes oops, yes, you're right - the rem == 0 case is (potentially) tail recursive but the odd case isn't.

sujithvm · Accepted Answer · 2014-08-12 16:11:33Z

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, 2014 at 16:11

answered Aug 12, 2014 at 15:40

sujithvm

2,4413 gold badges17 silver badges16 bronze badges

8 Comments

Tavian Barnes Over a year ago

This is missing the case for n == 0.

sujithvm Over a year ago

@TavianBarnes fixed it now. Please check

Alnitak Over a year ago

+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 Over a year ago

Looks correct, but is somehow really suboptimal?! I just traced it making twenty five calls to itself to calculate 3^13

Alnitak Over a year ago

I'm not sure how it happened but you've managed to make your algorithm O(2n) instead of O(log2 n)

|

Community · Accepted Answer · 2017-05-23 12:15:25Z

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;

Edwin Buck · Accepted Answer · 2014-08-12 15:41:17Z

0

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.

answered Aug 12, 2014 at 15:41

Edwin Buck

71.2k7 gold badges103 silver badges145 bronze badges

Collectives™ on Stack Overflow

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

5 Answers 5

9 Comments

4 Comments

8 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

9 Comments

4 Comments

8 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related