Power calcualation once more :(

Discussion in 'C++' started by mathon@gmx.at, Nov 6, 2006.

  1. Guest

    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
     
    , Nov 6, 2006
    #1
    1. Advertising

  2. Steve Pope Guest

    In article <>,
    <> 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
    shouldn't appear in your code.

    Steve
     
    Steve Pope, Nov 6, 2006
    #2
    1. Advertising

  3. Guest

    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
     
    , Nov 6, 2006
    #3
  4. Steve Pope Guest

    <> 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, Nov 6, 2006
    #4
  5. Guest

    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:
    > <> 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
    > >
     
    , Nov 6, 2006
    #5
  6. Steve Pope Guest

    <> 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
    of your runtime.

    S.
     
    Steve Pope, Nov 6, 2006
    #6
  7. > Steve Pope wrote:
    >><> 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);
    >>>}
    >>>


    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
     
    Stuart Redmann, Nov 7, 2006
    #7
  8. Steve Pope Guest

    Stuart Redmann <> wrote:

    >>><> 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, Nov 7, 2006
    #8
  9. Steve Pope Guest

    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.
     
    Steve Pope, Nov 7, 2006
    #9
  10. Steve Pope wrote:

    > Stuart Redmann <> wrote:
    >
    >
    >>>><> 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.

    Sorry for giving bad advice (at least point 3 ;)

    Stuart
     
    Stuart Redmann, Nov 7, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Michael
    Replies:
    4
    Views:
    419
    Matt Hammond
    Jun 26, 2006
  2. Niv
    Replies:
    8
    Views:
    628
  3. Replies:
    8
    Views:
    371
    Mark Dickinson
    Apr 17, 2008
  4. Gancy
    Replies:
    4
    Views:
    188
    Rasto Levrinc
    Feb 3, 2005
  5. Richard Maher

    > Sandboxed power == More secure???

    Richard Maher, Apr 17, 2013, in forum: Java
    Replies:
    24
    Views:
    502
    Arne Vajhøj
    Apr 28, 2013
Loading...

Share This Page