Velocity Reviews > C++ > Power calcualation once more :(

# Power calcualation once more :(

mathon@gmx.at
Guest
Posts: n/a

 11-06-2006
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]
Code:
```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:
Code:
``` 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

Steve Pope
Guest
Posts: n/a

 11-06-2006
In article <(E-Mail Removed) .com>,
<(E-Mail Removed)> wrote:
>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]
>
Code:
```>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:
>
Code:
```> 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...?

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

Steve

mathon@gmx.at
Guest
Posts: n/a

 11-06-2006
hi,

ah you mean like that:

Code:
```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

Steve Pope
Guest
Posts: n/a

 11-06-2006
<(E-Mail Removed)> wrote:

>hi,
>
>ah you mean like that:
>
>
Code:
```>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
>

mathon@gmx.at
Guest
Posts: n/a

 11-06-2006

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:
> <(E-Mail Removed)> wrote:
>
> >hi,
> >
> >ah you mean like that:
> >
> >
Code:
```> >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
> >

Steve Pope
Guest
Posts: n/a

 11-06-2006
<(E-Mail Removed)> 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)?

No, because that line gets run exactly once (and then only
if the input is negative). It will not affect the order

S.

Stuart Redmann
Guest
Posts: n/a

 11-07-2006
> Steve Pope wrote:
>><(E-Mail Removed)> wrote:
>>>
Code:
```>>>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);
>>>}
>>>```

http://www.velocityreviews.com/forums/(E-Mail Removed) 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)?

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

Steve Pope
Guest
Posts: n/a

 11-07-2006
Stuart Redmann <(E-Mail Removed)> wrote:

>>><(E-Mail Removed)> wrote:
>>>>
Code:
```>>>>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 step
>return 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

Steve Pope
Guest
Posts: n/a

 11-07-2006
I wrote,

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

Oops, that should be: n, (n-1)/2, ((n-1)/2 - 1)/2 etc.

S.

Stuart Redmann
Guest
Posts: n/a

 11-07-2006
Steve Pope wrote:

> Stuart Redmann <(E-Mail Removed)> wrote:
>
>
>>>><(E-Mail Removed)> wrote:
>>>>
>>>>>
Code:
```>>>>>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 step
>>return 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.

Stuart