Square root program

This is a discussion on Square root program within the C Programming forums, part of the General Programming Boards category; This is a program to compute square root of a positive number. Code: double sqrt(double num) { if (num < ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Location
    New York, NY
    Posts
    7

    Post Square root program

    This is a program to compute square root of a positive number.

    Code:
    double sqrt(double num)
    {
        if (num < 0)
            return 0;
    
        double guess = num/2, oldguess = 0;
    
        while(guess != oldguess) {
            oldguess = guess;
            guess = (num/guess + guess)/2;
        }
    
        return guess;
    }
    How do I prevent this program to loop forever?

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    You should never use the == or != operators on floating point values. The reason is that they will not be exactly equal to each other, thus your program loops forever. It is better to check if the numbers are within a certain amount of each other.

    Code:
    if(abs(guess - oldguess) < 0.01)
    bit∙hub [bit-huhb] n. A source and destination for information.

  3. #3
    Registered User
    Join Date
    Oct 2009
    Location
    New York, NY
    Posts
    7
    Thank you for your expert advise.

  4. #4
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    I've tried to run this function and have not found any case where it will continue forever.
    I can see how intermediate results could oscillate some tiny number +/-, but I have not found one yet. I've run through numbers 1 through to 10,000 in 0.001 increments (10 million numbers) with no problem.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Code:
    if(abs(guess - oldguess) < 0.01)
    Will do a partially decent job for your typical cases, but it's far from ideal. For example it will cause the function to fail miserably at calculating the sqrt of 1.0E-40 for example. Worse still, for very large numbers that epsilon wont be sufficient to prevent an infinite loop due to rounding.

    One way to prevent infinite looping due to rounding whilst still making sure that the function obtains maximum accuracy is to perform two iterations per loop:
    Code:
        while (guess != oldguess) {
            oldguess = guess;
            guess = (num/guess + guess) * 0.5;
            oldguess = guess;
            guess = (num/guess + guess) * 0.5;
        }
    Accuracy problem gone!

    I think a more obvious problem is that it will go into an infinite loop for NANs. In that case, the while loop evaluates NAN != NAN which is always true. For that, a special test for NANs should be performed beforehand.

    However that's still not enough because if num is infinity then guess and oldGuess turn into a NAN during the loop and it still ends up looping forever, so we need a test for infinity as well.

    The square root of a negative number is also supposed to be a NAN, not zero.
    Thus I suggest this:
    Code:
    double sqrt(double num)
    {
        if (num != num) // Test for NANs
            return num;
    
        if (num < 0)
            return std::numeric_limits<double>::quiet_NaN();
    
        if (num == std::numeric_limits<double>::infinity())
            return num;
    
        double guess = num/2, oldguess = 0;
    
        while(guess != oldguess) {
            oldguess = guess;
            guess = (num/guess + guess) * 0.5;
            oldguess = guess;
            guess = (num/guess + guess) * 0.5;
        }
    
        return guess;
    }
    There are ways of getting a more accurate initial guess too, but I think I've covered enough already.


    Having said that, I was also lucky enough for it to not go into an infinite loop when running to code myself over millions of numbers, and I'm increasing by the minimum amount possible using the equivalent of nextafter. Of course I was looking at small numbers, and the problem may be more likely with larger numbers.
    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"

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Ah drat, just realised this is the C board!
    Well I'll leave it as an exercise for the reader to look up how to obtain a NAN and an INF in C instead of C++.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. c program that accepts and executes commands?
    By Cimposter in forum C Programming
    Replies: 3
    Last Post: 09-30-2009, 03:58 PM
  2. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 11:17 PM
  3. Replies: 3
    Last Post: 09-05-2005, 09:57 AM
  4. Square Root ?!?
    By Tm687 in forum C++ Programming
    Replies: 1
    Last Post: 02-29-2004, 04:38 PM
  5. Square root
    By Unregistered in forum C Programming
    Replies: 8
    Last Post: 07-05-2002, 07:35 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21