445,918 Members | 2,240 Online Need help? Post your question and get tips & solutions from a community of 445,918 IT Pros & Developers. It's quick & easy.

# Power calcualation once more :(

 P: n/a hi, i already posted an entry because of this problem, unfortunately i havent solved it so far..:( I have created a recursion for the calculation of the power like this: [code] Expand|Select|Wrap|Line Numbers double power(double x, int n) { if (n < 0) return 1/power(x, -n); else if (n == 0) return 1.0; else return x * power(x, n-1); }     But the problem ist that i should use this formula x^2n = x^n x^n in any way in order to have a runtime of log(n). I read in the previous posting something like i should use this: Expand|Select|Wrap|Line Numbers if (0 == n%2) { return (x^((n-1)/2))*(x^((n-1)/2)) } else { return x*(x^((n-1)/2))*(x^((n-1)/2)) }   Maybe someone could help me here once more in order to reach my final aim...? :( matti Nov 6 '06 #1
9 Replies

 P: n/a In article <11**********************@i42g2000cwa.googlegroups .com>, hi,i already posted an entry because of this problem, unfortunately ihavent solved it so far..:(I have created a recursion for the calculation of the power like this:[code] Expand|Select|Wrap|Line Numbers double power(double x, int n) {  if (n < 0)    return 1/power(x, -n);  else if (n == 0)    return 1.0;  else    return x * power(x, n-1); } But the problem ist that i should use this formula x^2n = x^n x^n inany way in order to have a runtime of log(n).I read in the previous posting something like i should use this: Expand|Select|Wrap|Line Numbers if (0 == n%2)   {        return (x^((n-1)/2))*(x^((n-1)/2))   }    else   {       return x*(x^((n-1)/2))*(x^((n-1)/2))   } >Maybe someone could help me here once more in order to reach my finalaim...? :( You're pretty close. Try: if (0 == n%2) { double y = power(x,n/2); return y*y; } else return x*power(x,n-1); You may have been confused by the shorthand use of ^ which shouldn't appear in your code. Steve Nov 6 '06 #2

 P: n/a hi, ah you mean like that: Expand|Select|Wrap|Line Numbers double power(double x, int n) { if (n < 0) return 1/power(x, -n); else if (n == 0) return 1.0;   if (0 == n%2) { double y = power(x,n/2); return y*y; } else return x*power(x,n-1); }   Have you meant it in that way...? matti Nov 6 '06 #3

 P: n/a hi,ah you mean like that: Expand|Select|Wrap|Line Numbers double power(double x, int n) {  if (n < 0)    return 1/power(x, -n);  else if (n == 0)    return 1.0;   if (0 == n%2)   {        double y = power(x,n/2);        return y*y;   }   else        return x*power(x,n-1); } Have you meant it in that way...? Yes, that looks okay to me, but I haven't tried to run it. Good luck. Steve >matti Nov 6 '06 #4

 P: n/a yes it runs. one last question, shouldnt i modify this line: return 1/power(x,-n); as well, to reach the runtime of log(n)? matti Steve Pope wrote:

 P: n/a yes it runs. >one last question, shouldnt i modify this line: >return 1/power(x,-n); >as well, to reach the runtime of log(n)? No, because that line gets run exactly once (and then only if the input is negative). It will not affect the order of your runtime. S. Nov 6 '06 #6

 P: n/a Steve Pope wrote: >>>> Expand|Select|Wrap|Line Numbers double power(double x, int n) { if (n < 0)   return 1/power(x, -n); else if (n == 0)   return 1.0;  if (0 == n%2)  {        double y = power(x,n/2);        return y*y;  }  else        return x*power(x,n-1); } ma****@gmx.at wrote: > yes it runs. one last question, shouldnt i modify this line: return 1/power(x,-n); as well, to reach the runtime of log(n)? 1. Please don't top-post. 2. Remove any greetings from the posts you're replying to (they have no informational content, so they just lengthen the post). 3. If you put an exponent of the form 2^n - 1 into your power function, you still end up with a complexity of O(n), since the step return x*power(x,n-1) will be called 1/2 * 2^n - 1 times. I will give you the advice not to try to tackle this problem recursively, as you will need to have all potences of x available (you still can do this recursively, but the resulting code would be rather messy). I won't spoil your fun of finding the right solution, so all I'm saying is that the solution you have found so far is good enough. Regards, Stuart Nov 7 '06 #7

 P: n/a Stuart Redmann >>3. If you put an exponent of the form 2^n - 1 into your power function,you still end up with a complexity of O(n), since the stepreturn x*power(x,n-1) will be called 1/2 * 2^n - 1 times. That doesn't seem right. Any pair of consecutive calls beginning with power(n) must reduce its argument by at least a factor of 2 since the only possibilities are: n = 2*k (n even) which results in a call to power(k) n = 2*k+1 (n odd) which results in a call to power(2*k), then a call to power(k) Therefore the runtime is bounded by 2 * log2(n). The runtime will be equal to this bound if n, (n-1)/2, ((n-1)/2)/2 etc. are all odd. Otherwise it will be lower than this bound. Or am I missing something? Steve Nov 7 '06 #8

 P: n/a I wrote, >That doesn't seem right. Any pair of consecutive callsbeginning with power(n) must reduce its argument by at least a factorof 2 since the only possibilities are: n = 2*k (n even) which results in a call to power(k) n = 2*k+1 (n odd) which results in a call to power(2*k), then a call to power(k)Therefore the runtime is bounded by 2 * log2(n). The runtimewill be equal to this bound if n, (n-1)/2, ((n-1)/2)/2 etc. areall odd. Otherwise it will be lower than this bound. Oops, that should be: n, (n-1)/2, ((n-1)/2 - 1)/2 etc. S. Nov 7 '06 #9

 P: n/a Steve Pope wrote: Stuart Redmann >>> Expand|Select|Wrap|Line Numbers >double power(double x, int n) >{ >if (n < 0)  return 1/power(x, -n); >else if (n == 0)  return 1.0; > if (0 == n%2) { >       double y = power(x,n/2); >       return y*y; } else >       return x*power(x,n-1); >} > >>3. If you put an exponent of the form 2^n - 1 into your power function,you still end up with a complexity of O(n), since the stepreturn x*power(x,n-1) will be called 1/2 * 2^n - 1 times. That doesn't seem right. Any pair of consecutive calls beginning with power(n) must reduce its argument by at least a factor of 2 since the only possibilities are: n = 2*k (n even) which results in a call to power(k) n = 2*k+1 (n odd) which results in a call to power(2*k), then a call to power(k) Therefore the runtime is bounded by 2 * log2(n). The runtime will be equal to this bound if n, (n-1)/2, ((n-1)/2)/2 etc. are all odd. Otherwise it will be lower than this bound. Or am I missing something? Nope. Obviously I did (*shame*). I didn't read your code properly (no comments, BTW). Of course, the computational complexity you have given is right. Using this algorithm is certainly even the most elegant solution since recursion is the shortest way to implement it. Sorry for giving bad advice (at least point 3 ;) Stuart Nov 7 '06 #10

### This discussion thread is closed

Replies have been disabled for this discussion. 