Recursive method for x^n optimised for when n is even

Question

I need to write a recursive method using Java called power that takes a double x and an integer n and that returns x^n. Here is what I have so far.

public static double power(double x, int n) {
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    else
        return x * (power(x, n-1));

}

This code works as expected. However, I am trying to go the extra mile and perform the following optional exercise:

"Optional challenge: you can make this method more efficient, when n is even, using x^n = (x^(n/2))^2."

I am not sure how to implement that last formula when n is even. I do not think I can use recursion for that. I have tried to implement the following, but it also does not work because I cannot take a double to the power of an int.

if (n%2 == 0)
        return (x^(n/2))^2;

Can somebody point me in the right direction? I feel like I am missing something obvious. All help appreciated.

I voted you up just for being a student that tackled a problem on their own and showed some good code. Well done. Hint: Think about how to incorporate a recursive call into your even power case and you'll have it. — duffymo, Sep 27 '15 at 02:13
The notation of the question is confusing you. In Java, `^` means a bitwise XOR. In quasi-mathematical notation, `x ^ 2` means "x to the second power". Yes, you already got an answer but I wanted to make explicit the battling notations. — msw, Sep 27 '15 at 15:55

Stefan Haustein · Accepted Answer · 2015-09-30T14:32:48.493

23

It's exactly the same principle as for x^n == x*(x^(n-1)): Insert your recursive function for x^(n/2) and (...)^2, but make sure you don't enter an infinite recursion for n == 2 (as 2 is even, too):

if (n % 2 == 0 && n > 2) 
  return power(power(x, n / 2), 2);
}

Alternatively, you could just use an intermediate variable:

if (n % 2 == 0) {
  double s = power(x, n / 2);
  return s * s;
}

I'd probably just handle 2 as a special case, too -- and avoid the "and"-condition and extra variable:

public static double power(double x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  if (n == 2) return x * x;
  if (n % 2 == 0) return power(power(x, n / 2), 2);
  return x * (power(x, n - 1));
}

P.S. I think this should work, too :)

public static double power(double x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  if (n == 2) return x * x;
  return power(x, n % 2) * power(power(x, n / 2), 2);
}

edited Sep 30 '15 at 14:32

answered Sep 27 '15 at 02:10

Stefan Haustein

18,427
3
36
51

5

In the spirit of further optimization, one can note that if `n%2 == 1` (and thus the last line is reached), then `(n-1) % 2 == 0` and thus the latter expression can be further "unrolled": `x * power(power(x, (n-1)/2), 2)`. – Matthieu M. Sep 27 '15 at 20:51
2

One could also combine the last two cases into `return power(x, n % 2) * power(power(x, n/2), 2);` :) – Stefan Haustein Sep 27 '15 at 23:01
2

That too :) Actually, I am curious about `power(power(x, n/2), 2)` too, since most of the times when I've done it, I've used `power(x*x, n/2)` (which avoids a function call). – Matthieu M. Sep 28 '15 at 06:35
If you ever edit the question adding those, make sure to place a warning for homework seeking students to stick with the previous. – Mariano Sep 28 '15 at 07:00

Sergey Kalinichenko · Answer 2 · 2015-09-27T13:41:10.933

11

When n is even, the formula is exactly what you wrote: divide n by two, call power recursively, and square the result.

When n is odd, the formula is a little more complex: subtract 1 from n, make a recursive call for n/2, square the result, and multiply by x.

if (n%2 == 0)
    return (x^(n/2))^2;
else
    return x*(x^(n/2))^2;

n/2 truncates the result, so subtraction of 1 is not done explicitly. Here is an implementation in Java:

public static double power(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    double pHalf = power(x, n/2);
    if (n%2 == 0) {
        return pHalf*pHalf;
    } else {
        return x*pHalf*pHalf;
    }
}

Demo.

edited Sep 27 '15 at 13:41

answered Sep 27 '15 at 02:10

Sergey Kalinichenko

714,442
84
1,110
1,523

that seems correct, but when I try to implement that code in Java, I get an error "The operator ^ is undefined for the argument type(s) double, int. Perhaps I am missing something? – Omar N Sep 27 '15 at 02:24
@OmarN This should be straightforward to implement ([demo](http://ideone.com/wxk9MQ)). – Sergey Kalinichenko Sep 27 '15 at 02:48
1

Downvoter: would you mind sharing your reasons for voting down a perfectly correct answer with a fully working demo? – Sergey Kalinichenko Sep 30 '15 at 15:56

score 6 · Answer 3 · answered Sep 27 '15 at 02:11

6

Hint: The ^ operation won't perform exponentiation in Java, but the function you wrote, power will.

Also, don't forget squaring a number is the same as just multiplying it by itself. No function call needed.

answered Sep 27 '15 at 02:11

jaynp

3,275
4
30
43

score 6 · Answer 4 · answered Sep 27 '15 at 02:23

Making a small change to your function, it will reduce the number of recursive calls made:

public static double power(double x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }

    if (n % 2 == 0) {
        double temp = power(x, n / 2);
        return temp * temp;
    } else {
        return x * (power(x, n - 1));
    }
}

score 5 · Answer 5 · answered Sep 27 '15 at 15:28

Since

x^(2n) = (x^n)^2

you can add this rule to your method, either using the power function you wrote, as Stefan Haustein suggested, or using the regular multiplication operator, since it seems you are allowed to do that.

Note that there is no need for both the base cases n=1 and n=0, one of them suffices (prefferably use the base case n=0, since otherwise your method would not be defined for n=0).

public static double power(double x, int n) {
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        double val = power(x, n/2);
        return val * val;
    else
        return x * (power(x, n-1));
}

There is no need to check that n>2 in any of the cases.

score 0 · Answer 6 · answered Sep 30 '15 at 04:50

This just reminds me more optimisation could be done and this following code.

class Solution:
# @param x, a float
# @param n, a integer
# @return a float
def pow(self, x, n):
    if n<0:
        return 1.0/self.pow(x,-n)
    elif n==0:
        return 1.0
    elif n==1:
        return x
    else:
        m = n & (-n)
        if( m==n ):
            r1 = self.pow(x,n>>1)
            return r1*r1
        else:
            return self.pow(x,m)*self.pow(x,n-m)

what is more intermediate result could be memorised and avoid redundant computation.

Recursive method for x^n optimised for when n is even

6 Answers6