Thread: The Babylonian algorithm

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    67

    Question The Babylonian algorithm

    Estimate a square root of a number n:
    1.make a guess (you can pick n/2);
    2.compute r=n/guess;
    3.set guess=(guess+r)/2;
    4.Go back for step 2 and 3,until the guess is within 1% of the previous guess.the more,the closer.
    OK,so we need a program to do it!
    Code:
    #include<iostream>
    using namespace std;
    int main()
    {
         double n,r,gue,gue1;
         cout<<"enter n:";
         cin>>n;
         gue=n/2;
      
        
         do
       {  
          r=n/gue;
          gue1=gue;
          gue=(gue+r)/2;
        }while(gue>=0.01*gue1)
    
    cout<<"It is "<<gue;
    return 0;
    }

    Look,I make gue1 to be the previous guess,so we can stop the program,but when I run it,it
    is a infinite loop.Why?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    The problem is with your loop condition (aside from the fact that you are missing a terminating semi-colon around there as well). You need to correctly express the negation of "the guess is within 1&#37; of the previous guess" in the loop condition.

    Incidentally, just use guess as a variable name instead of gue. Two characters more does not hurt and can improve readability.
    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

  3. #3
    Registered User
    Join Date
    May 2007
    Posts
    67
    But I think I am correct,where is wrong?Could anyone tell me?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    But I think I am correct,where is wrong?
    Suppose gue1 is 100 and gue is 99. So, current guess is within 1&#37; of the previous guess.

    Substituting into your loop condition:
    gue >= 0.01 * gue1
    99 >= 0.01 * 100
    99 >= 1
    true

    So, when the current guess is within 1% of the previous guess, the loop continues to the next iteration. This is clearly wrong.

    In fact, your current loop condition makes the loop loop until the current guess is less than 1% of the previous guess. However, the current guess cannot be less than 50% of the previous guess since r should be non-negative. As such, the loop is an infinite loop as the current guess cannot be less than 1% of the previous guess.
    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

  5. #5
    Registered User
    Join Date
    May 2007
    Posts
    67
    Yes,you are right!So there must be something wrong with this problem!Since it said within 1&#37;,but
    actually gue=gue1/2+r/2means gue must be more than 50% of gue1,so it will never end!

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Yes,you are right!So there must be something wrong with this problem!Since it said within 1&#37;,but
    actually gue=gue1/2+r/2means gue must be more than 50% of gue1,so it will never end!
    You are reading the problem incorrectly. 99 is within 1% of 100, but it is certainly more than 50% of 100.
    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
    Registered User
    Join Date
    May 2007
    Posts
    67
    ok,thx!I am so silly!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM