By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,131 Members | 1,945 Online
Bytes IT Community
+ Ask a Question
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
  1. double power(double x, int n) {
  2. if (n < 0)
  3. return 1/power(x, -n);
  4. else if (n == 0)
  5. return 1.0;
  6. else
  7. return x * power(x, n-1);
  8. }
  9.  
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
Share this Question
Share on Google+
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
  1. double power(double x, int n) {
  2.  if (n < 0)
  3.    return 1/power(x, -n);
  4.  else if (n == 0)
  5.    return 1.0;
  6.  else
  7.    return x * power(x, n-1);
  8. }
  9.  

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
  1. double power(double x, int n)
  2. {
  3. if (n==0)
  4. return 1.0;
  5.  
  6. if (0 == n%2)
  7. {
  8. return (x^((n-1)/2))*(x^((n-1)/2))
  9. }
  10. else
  11. {
  12. return x*(x^((n-1)/2))*(x^((n-1)/2))
  13. }
  14. }
  15.  
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
  1. double power(double x, int n)
  2. {
  3.    if (n==0)
  4.        return 1.0;
Expand|Select|Wrap|Line Numbers
  1.  
  2. You could also create a few other predefined return values,
  3. for example for 'n==1' or 'n==2', just to optimize a bit.
  4.  
  5.         
  6.                 >
  7.   if (0 == n%2)
  8.   {
  9.        return (x^((n-1)/2))*(x^((n-1)/2))
  10.   }
  11.    else
  12.   {
  13.       return x*(x^((n-1)/2))*(x^((n-1)/2))
  14.   }
  15. }
  16.  
  17.  
>
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
  1. double power(double x, int n)
  2. {
  3.    if (n==0)
  4.        return 1.0;
Expand|Select|Wrap|Line Numbers
  1. You could also create a few other predefined return values,
  2. for example for 'n==1' or 'n==2', just to optimize a bit.
  3.         
  4.                 >  if (0 == n%2)
  5.   {
  6.        return (x^((n-1)/2))*(x^((n-1)/2))
  7.   }
  8.    else
  9.   {
  10.       return x*(x^((n-1)/2))*(x^((n-1)/2))
  11.   }
  12. }
  •  
  •  
  • >>
    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 <cmath>

    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.