Calucalting the power

[mathon]

hi,

i develeoped a recursive function for the power and it works fine

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 is this function should have a runtime of log(n) and
therefore i should use this formula x^2n = x^n x^n in any way. does
maybe someone knows here how i can modifiy it to reach my aim...?

matti

 

[Victor Bazarov]

i develeoped a recursive function for the power and it works fine

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 is this function should have a runtime of log(n) and
therefore i should use this formula x^2n = x^n x^n in any way. does
maybe someone knows here how i can modifiy it to reach my aim...?

If 'n' is even, calculate the power as (x^(n/2))*(x^(n/2))
If 'n' is odd, calculate the power as x*(x^(n/2))*(x^(n/2))

V

 

[mathon]

so you mean in that way:

double power(double x, int n)
 {
    if (n==0)
        return 1.0;

   if (0 == n%2)
   {
        return (x^((n-1)/2))*(x^((n-1)/2))
   }
    else
   {
       return x*(x^((n-1)/2))*(x^((n-1)/2))
   }
}

or did i interpret something wrong...?

matti

 

[Victor Bazarov]

so you mean in that way:

double power(double x, int n)
{
if (n==0)
return 1.0;[/QUOTE]

You could also create a few other predefined return values,
for example for 'n==1' or 'n==2', just to optimize a bit.
[QUOTE]
if (0 == n%2)
{
return (x^((n-1)/2))*(x^((n-1)/2))
}
else
{
return x*(x^((n-1)/2))*(x^((n-1)/2))
}
}

or did i interpret something wrong...?

Did I use "-1" anywhere in my reply (which you didn't quote)?
First of all, don't use ^, instead use the recursion which you
already have. Second, use -1 only where needed.

V

 

[Mark P]

so you mean in that way:

double power(double x, int n)
{
if (n==0)
return 1.0;[/QUOTE]

You could also create a few other predefined return values,
for example for 'n==1' or 'n==2', just to optimize a bit.
[QUOTE]
if (0 == n%2)
{
return (x^((n-1)/2))*(x^((n-1)/2))
}
else
{
return x*(x^((n-1)/2))*(x^((n-1)/2))
}
}

or did i interpret something wrong...?

Did I use "-1" anywhere in my reply (which you didn't quote)?
First of all, don't use ^, instead use the recursion which you
already have. Second, use -1 only where needed.

And third, use recursion intelligently. You won't see any improvement
in run time if you write, e.g.,

return power(x,n/2) * power(x,n/2)

because you're making two identical chains of recursive calls.

 

[Kaz Kylheku]

so you mean in that way:

double power(double x, int n)
{
if (n==0)
return 1.0;

if (0 == n%2)
{
return (x^((n-1)/2))*(x^((n-1)/2))[/QUOTE]

The ^ operator performs a bitwise exclusive or.

In the standard C library, there is a function called pow for
exponentiation.

#include <cmath>

 double p = pow(x, n);
[QUOTE]
or did i interpret something wrong...?[/QUOTE]

I think Victor was just pulling your leg. It would be pretty dumb to
call pow() twice on the halved exponent, and then multiply the two
results together.

  // silly!
  double p = pow(x, n/2) * pow(x, n/2);

Firstly, there are the extra divisions and multiplication. These not
only add overhead but possible loss of precision due to truncation
errors. Secondly, the compiler might not optimize the redundant call to
pow away, and so the program may actually end up exponentiating twice.