rewriting a recursive function

[Wnt2bsleepin]

Hello, I have to rewrite a recursive function that take a number and raises it to a power. It's sounds simple, but we have to do it in Logn time using X^2n = X^n times X^n. I am having a hard time implementing this. Here is the code for the other power function that I have to modify.

public static double pow(double x, int n )
{

if(x == 0 && n <= 0)
     throw new IllegalArgumentException("Wrong inputs");
else if (x == 0)
      return 0;
else if (n == 0)
      return 1;
else if (n > 0)
      return x * pow(x, n-1);
else
     return 1/pow(x,-n);
}

I am able to follow the recursive calls for this method fine, I just don't know how to implement that weird form I was given to use. Thanks for any help.

[pbrockway2]

else if (n > 0)
      return x * pow(x, n-1);

The idea seems to be that you keep subtracting 1 from n until it becomes small (zero or one).

I think what you are asked to do is divide n by 2 instead of subtracting one. There is a small complication to deal with if n is odd. But even that shouldn't be too difficult since, in that case, n-1 is even.

[jlczuk]

Here's the deal. The original algorithm will work just fine for solving x^cn where c is some constant such as -2, 3, 21, etc. It will just take longer than if you take advantage of the algebraic rule that x^cn = (x^c)^n. Note that x^cn does NOT equal x^c * x^n

The original algorithm requires (c*n)-1 passes to achieve the answer. Taking advantage of factoring the exponents will take (n-1)+(c-1) passes.

I think I have that correct upon re-reading it before posting.

[Wnt2bsleepin]

else if (n > 0)
      return x * pow(x, n-1);

The idea seems to be that you keep subtracting 1 from n until it becomes small (zero or one).

I think what you are asked to do is divide n by 2 instead of subtracting one. There is a small complication to deal with if n is odd. But even that shouldn't be too difficult since, in that case, n-1 is even.

Would the modification involve adding another base case? Why would it being odd matter?

[JosAH]

Write down the recurrence relations for the pow operator:

1) x^0 == 1
2) x^1 == x
3) x^n == x^(n/2)*x^(n/2) if n is even
4) x^n == x*x^(n/2)*x^(n/2) if n is odd

cases 1) and 2) are the sentinel cases while case 3) and 4) describe the recursive step.

kind regards,

Jos

[Wnt2bsleepin]

Write down the recurrence relations for the pow operator:

1) x^0 == 1
2) x^1 == x
3) x^n == x^(n/2)*x^(n/2) if n is even
4) x^n == x*x^(n/2)*x^(n/2) if n is odd

cases 1) and 2) are the sentinel cases while case 3) and 4) describe the recursive step.

kind regards,

Jos

Thank you very much. I was able to solve it. Now I just have to write it nonRecursively.

[JosAH]

Thank you very much. I was able to solve it. Now I just have to write it nonRecursively.

Think of the exponent n as a binary number; each bit represents a power of the number x: x^1, x^2, x^3, x^4 etc. If a bit in that number n is 1, multiply your result by the corresponding power of x.

kind regards,

Jos