446,131 Members | 1,945 Online
Need help? Post your question and get tips & solutions from a community of 446,131 IT Pros & Developers. It's quick & easy.

# Calucalting the power

 P: n/a hi, i develeoped a recursive function for the power and it works fine 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 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 Nov 3 '06 #1
5 Replies

 P: n/a ma****@gmx.at wrote: i develeoped a recursive function for the power and it works fine 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 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 -- Please remove capital 'A's when replying by e-mail I do not respond to top-posted replies, please don't ask Nov 3 '06 #2

 P: n/a so you mean in that way: Expand|Select|Wrap|Line Numbers 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 Nov 3 '06 #3

 P: n/a ma****@gmx.at wrote: so you mean in that way: Expand|Select|Wrap|Line Numbers double power(double x, int n) {    if (n==0)        return 1.0; Expand|Select|Wrap|Line Numbers   You could also create a few other predefined return values, for example for 'n==1' or 'n==2', just to optimize a bit.                            >   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 -- Please remove capital 'A's when replying by e-mail I do not respond to top-posted replies, please don't ask Nov 3 '06 #4

 P: n/a Victor Bazarov wrote: ma****@gmx.at wrote: >so you mean in that way: Expand|Select|Wrap|Line Numbers double power(double x, int n) {    if (n==0)        return 1.0; Expand|Select|Wrap|Line Numbers You could also create a few other predefined return values, for example for 'n==1' or 'n==2', just to optimize a bit.                          >  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. Nov 3 '06 #5

 P: n/a ma****@gmx.at wrote: so you mean in that way: [code] 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)) The ^ operator performs a bitwise exclusive or. In the standard C library, there is a function called pow for exponentiation. #include double p = pow(x, n); or did i interpret something wrong...? 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. Nov 4 '06 #6

### This discussion thread is closed

Replies have been disabled for this discussion.