Thread: Simple calculate integer power of a double using recursion program - critique

  1. #1
    Registered User
    Join Date
    Jul 2011
    Posts
    3

    Simple calculate integer power of a double using recursion program - critique

    I am trying to brush up on C after about 12+ years, which was two semesters at college. This program works, but I am poor on recursion and wonder if there are some tips that could be offered. Using Borland Turbo C++ 4.5 (yes, old) on win XP pro and win7 pro 32 bit machines.

    Code:
    /*  9.8 Mod listing 6.18 to all cases of integer powers using recursion */
    
    #include <stdio.h>
    double power(double a, int b);    /* function prototype  */
    
    int main (void)
    {
      double x, xpow;
      int n;
    
      printf("Enter a number and the integer power to which\n");
      printf("the number will be raised. Enter q to quit.\n");
    
      while(scanf("%lf%d", &x, &n) == 2)
      {
         xpow = power(x,n);
         printf("%.3e to the power %d is %.3e\n", x, n, xpow);
      }
      return 0;
    }
    
    
    double power(double a, int b)  /* POWER function  */
    {
      double pow = 1;
      int b1;
    
      if (b == 0)            /* case of any number raised to 0 is 1 */
        return 1.0;
    
      else
      if (a == 0.0)          /* case of 0 to any power but 0 is 0  */
        return 0.0;
    
      else                   /* do non 0 pos and neg powers and numbers  */
      {
         if (b > 0)           /* normalize the power to a positive number  */
    	b1 = b;            /* since fractions are not as accurate       */
         else
    	b1 = -1 * b;
    
         pow = a;                 /*  calculate power doing recursive call  */
         pow *= power(pow, b1-1);
    
         if (b < 0.0)          /* case of negative exponents  */
    	pow = 1.0/pow;
    
         return  pow;
      }
    }
    Last edited by RayW1; 07-22-2011 at 12:26 PM. Reason: Minor comment typo

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Your code is fine, but you can clean it up a bit by removing the temporary variables (b1 and pow), and eliminating some of the elses and nested if-elses. Also, you can combine some of your mathematical expressions:
    Code:
    double power2(double a, int b)
    {
        if (b == 0) {
            // base case: anything to the 0 power is 1
            return 1.0;
        }
    
    
        if (a == 0.0) {
            // save us some time, 0 to any power other than 0 is 0
            return 0.0;
        }
    
    
        if (b < 0) {
            // b is negative, take the reciprocal of the positive version
            return 1 / (a * power2(a, -1 * b - 1));
        }
    
        // b is positive, normal recursion
        return a * power2(a, b - 1);
    }
    EDIT: You could also do the following, though I didn't mention it at first since I thought you didn't want to use any library functions:
    Code:
    return 1 / (a * power2(a, abs(b) - 1));
    Last edited by anduril462; 07-22-2011 at 12:46 PM.

  3. #3
    Registered User
    Join Date
    Jul 2011
    Posts
    3
    Thanks Andruil,
    I used the elses to avoid doing the if checks if they were not required, a leftover from my assembly days when computers where slower and we watched the machine cycles.

    I can see that your way is a bit neater, but I deliberately saved the negative power division until the last since (again, it could be just my age) the use of fractional math is less precise than the integer math (especially those that have non-finite decimal representations like 1/3) , so I waited until the last calculation to convert it. As far as the use of the absolute function, I did not want to drag in another library since the book has not gotten there yet, but you are correct, that is the better way in my example.

    Ray

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Pre-optimization is the root of all evil, so they say. On a desktop machine, never count cycles unless you know that it's a serious bottleneck and the speed up will be significant. Otherwise, such optimization can easily become a maintenance nightmare. I started in real-time embedded systems over a decade ago, so I had to fight the same urge to optimize at an assembly code level when I got my second job programming enterprise level business software where resources abounded.

    Your code and my code will always have to make the same 3 comparisons in order, regardless of the use of "else". We both check a base case. If that's false, we check if a is zero (to short-circuit the recursion). If that's false too, we then check if b is positive or negative, so we can compute the right kind of exponent. Use of else if might provide a more optimized solution (e.g. jump table) if you compared b against several discreet values, like
    Code:
    if (b == 0)
    else if (b == 1)
    else if (b == 2)
    else if (b == 3)
    else if (b == 4)
    else if (b == 5)
    else
    This is similar to a switch statement. But this doesn't work for us since we have to check b, then a, then b again.

    My version is probably a little quicker since I don't do any extra comparisons (you check b for positive/negative in two places), and I don't use (and thus don't have assignments to) temporary variables. Granted these are probably pretty negligible time-savers, but if you really care...

    As for waiting until the last minute to take the reciprocal, my code does that as well, due to the parentheses around the (a * power2(a, -1 * b - 1)), which is not only mandatory for a correct answer, but it forces that to be calculated before the division. That code will only ever be executed on the first run through this function. All recursive calls after that will have a non-negative b value and thus can't execute another division. It will be the last operation before a value is returned to your main function. If you don't want to use abs(), you may do a few cycles better by using 0 - b - 1 instead of -1 * b - 1, though the compiler may optimize the multiplication out anyhow.

  5. #5
    Registered User
    Join Date
    Jul 2011
    Posts
    3
    Thanks Anduril, I did not read your code correctly. Told you I was poor on recursion. Have to study what you did a bit more since I have a feeling I will have that type of flow show up again. And now that you mention it, I remember an instructor telling us back in the early 80's that the new compilers will/should be doing that optimization, so another thing to watch for so as to not over complicate the picture.

    Thanks for taking the time to do that analysis.

    Ray

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by anduril462
    Granted these are probably pretty negligible time-savers, but if you really care...
    ... you would use a faster algorithm
    For example:
    Code:
    double power(double a, int b)
    {
        if (b == 0)
        {
            /* base case: anything to the 0 power is 1 */
            return 1.0;
        }
        else if (a == 0.0)
        {
            /* save us some time, 0 to any power other than 0 is 0 */
            return 0.0;
        }
        else if (b < 0)
        {
            /* b is negative, take the reciprocal of the positive version */
            return 1.0 / power(a, -b);
        }
        else
        {
            /* b is positive, normal recursion */
            double result = power(a, b / 2);
            result *= result;
            if (b % 2 != 0)
            {
                /* account for the truncation of b / 2 due to integer division */
                result *= a;
            }
            return result;
        }
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by laserlight View Post
    ... you would use a faster algorithm
    For example:
    Code:
            return result;
        }
        /* <------ */
    }
    Not having a return before the final brace on a function that returns something other than void, bugs the crap out of me.


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by quzah
    Not having a return before the final brace on a function that returns something other than void, bugs the crap out of me.
    Go ahead and insert unreachable code if that makes you feel better

    Or you can change the function to have a single exit point, but then anduril462 will tell you that "you can clean it up a bit by removing the temporary variable".

    Oh, but I guess the best solution for you is to remove the else so control just carries on, but you'll have to declare result far from where it will be first used according to your preferred style.
    Last edited by laserlight; 07-22-2011 at 10:28 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by laserlight View Post
    Go ahead and insert unreachable code if that makes you feel better

    Or you can change the function to have a single exit point, but then anduril462 will tell you that "you can clean it up a bit by removing the temporary variable".

    Oh, but I guess the best solution for you is to remove the else so control just carries on
    Yeah, I would have probably ditched the else. Trying to make it use no variables and a single return is ugly.

    I know it's not going to reach that point, but I can't bring myself to do that.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by laserlight View Post
    Go ahead and insert unreachable code if that makes you feel better
    LOL!
    Love that comment eh - so true!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 10
    Last Post: 03-25-2011, 09:05 AM
  2. Replies: 6
    Last Post: 08-09-2010, 06:31 PM
  3. power calculate
    By isthanblue in forum C Programming
    Replies: 11
    Last Post: 12-09-2007, 02:14 PM
  4. power of 2? without loops or recursion
    By rahuls in forum C Programming
    Replies: 8
    Last Post: 03-20-2003, 05:10 PM
  5. power recursion
    By datainjector in forum C Programming
    Replies: 2
    Last Post: 11-06-2002, 04:56 PM