Recursive solution?

[Xanz1441]

I've been tasked to come up with a recursive solution to

X^n = (X^(n/2))^ 2 if n is even

X^n = (X * ((X^(n/2))^2)) if n is odd

now here's the function i've written so far

double RecursivePower3(double& baseValue, double expPower, double powerValue){

    if (expPower == 0)
		return 1;
	if (expPower == 2)
		return baseValue;
    if (fmod(expPower, 2) == 0){           //then it's even
		powerValue = pow(pow(baseValue,floor(expPower / 2)), 2);
                return powerValue;
    }
    else{
                powerValue = (baseValue * pow(pow(baseValue,floor(expPower / 2)), 2);
                return powerValue;
    } 
}

where baseValue = X and expPower = n and are values entered in by the user.

can anyone tell me how this can be solved recursively?

[robatino]

You're trying to efficiently compute a nonnegative integer power n of x? Basically just picture the binary representation of n, and which power of x each digit corresponds to. You don't have to do it recursively - there's a fairly simple iterative solution (if you're allowed to use it).

[Xanz1441]

we're supposed to write a recursive solution implementing that equation i gave at the beginning. The code I gave gives the right answers, it's just not the method wanted.

[robatino]

Your recursive function should be declared something like

double power(double x, unsigned int n)

(I think that's enough of a hint). You definitely don't want to call pow(), which is expensive. The recursive function doesn't need to do anything more than squaring and/or multiplying.

Edit: If you want, you could extend the function to negative powers by having it call itself if n is negative, and then take the reciprocal.

[Xanz1441]

I still don't understand where I should call the function inside the function to make it recursive.

[matsp]

I still don't understand where I should call the function inside the function to make it recursive.

Yes, a recursive function is calling itself, that is what makes it recursive.

Say for example you have factorial, which is fac(n) = fac(n - 1) * n, and fac(0) = 1, then you have the following code:

int fac(int n)
{
   if (n == 0) return 1;
   else 
      return n * fac(n - 1);
}

You should be able to do the same thing for your function, although it is a little bit more complex.

--
Mats

[Xanz1441]

so i tried this

double RecursivePower3(double& baseValue, double expPower){

	if (expPower == 0)
		return 1;
	if (expPower == 2)
		return baseValue;
    if (fmod(expPower, 2) == 0){           //then it's even
                return (RecursivePower3(baseValue, expPower) / 2);
    }
	else
		return baseValue * (RecursivePower3(baseValue, expPower) / 2);

}

but it doesn't work.

[Daved]

In your formula you have:

X^n = (X^(n/2))^ 2
X^n = (X * ((X^(n/2))^2))

In your code you have:

X^n = (X^n) / 2
X^n = X * (X^n) / 2


Also, don't forget that for some value num, num^2 is the same as num*num.

[Xanz1441]

Ok, now i've got this

double RecursivePower3(double& baseValue, double expPower){

	double powerValue;

	if (expPower == 0)
		return 1;
	if (expPower == 2)
		return baseValue;
    if (fmod(expPower, 2) == 0){   //then it's even
                return ((RecursivePower3(baseValue, expPower / 2)) * (RecursivePower3(baseValue, expPower / 2)));
    }
	else
		return (baseValue * ((RecursivePower3(baseValue, expPower / 2)) *(RecursivePower3(baseValue, expPower / 2))));
}

and for an even numbered expPower, it's outputting the power value of X ^ n/2 only, not squaring it

like for 3 ^ 32 it's outputting 43046721

and for the odd numbers it's not even outputting anything at all

[cyph1e]

You do realize that (X^(n/2))^2 = X^n and (X * ((X^(n/2))^2)) = X^(n+1)? No need to overcomplicate things. However, if n is an integer, both will be X^n. Are you sure that is not the case? It seems like you should solve this by only using multiplication.

X^n = X * X * ... {n times total} ... * X

(why did I need code-tags to be able to submit this?)

Study matsp's example.

Edit: added a line.

[Daved]

I think the problem might be your base cases. You have a base case of 2 returning the basevalue. But what that means is that basevalue^2 = basevalue. That of course is not right.

I would think the only base you would need would be 0.

Actually, the other problem I see is that you are using a double for the exponent. Are you sure that should be a double? The formulas look like they use integer math. You might never get to a base case with floating point math because that's not exact and you are using ==.

Change the exponent to an integer and remove the second base case and I think you might have it right.

[matsp]

You do realize that (X^(n/2))^2 = X^n and (X * ((X^(n/2))^2)) = X^(n+1)? No need to overcomplicate things. However, if n is an integer, both will be X^n. Are you sure that is not the case? It seems like you should solve this by only using multiplication.

X^n = X * X * ... {n times total} ... * X

(why did I need code-tags to be able to submit this?)

Study matsp's example.

Edit: added a line.

Yes, but the solution is supposed to be done slightly differently - by squaring the result of a previous power calculation, you don't need so many steps. If we use the "brute force method"

double power(double x, int n)
{ 
   if (n == 0) return 1.0;
   else return d * power(d, n - 1);
}

For 2 ^5, this takes 6 recursions.

If instead, we take the original formula:

x^5 = x * ((x ^ 2) ^ 2), you only half the number of recursions.

--
Mats

[matsp]

Here's my obfuscated solution:

	if(!I)return 1.0;{double l=rp(i,I>>1);return(I&1)?(i*l*l):(l*l);}

Note that I don't want to give the full solution, so this is just the function body.

--
Mats

[robatino]

Here's the iterative solution:

double power(double x, unsigned int n) {
  double xn = 1.;
  while (n) {
    if (n & 1) xn *= x;
    n >>= 1;
    x *= x;
  }
  return xn;
}