CODEWITHSUNDEEP
c++algorithmsquare-root
Anthony Santiago
Anthony Santiago

Reputation: 51

Getting an infinite loop in Babylonian Algorithm for square roots in C++

I have thoroughly searched for this topic all over the internet, and the threads are either dead, or use a different method than what is described in my book.

For example, http://www.geeksforgeeks.org/square-root-of-a-perfect-square/ . This doesn't work for me because my algorithm needs to loop until it reaches 1% of the last "guess".

Here is the question from the text.

The Babylonian algorithm to compute the square root of a number n is as follows:

  1. Make a guess at the number (you can pick n/2 as your initial guess).
  2. Compute r = n / guess
  3. Set guess = (guess + r) / 2
  4. Go back to step 2 for as many iterations as necessary. The more that steps 2 and 3 are repeated, the closer guess will become to the square root of n.

Write a program that inputs an integer for n, iterates through the Babylonian algorithm until guess is within 1% of the previous guess, and outputs the answer as a double.

I have written the following code:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{
int  n;
double r, guess(4), lastGuess;

cout << "Enter a number to find the square root of: ";
cin >> n;

do
{

    r = n / guess;
    lastGuess = guess;
    guess = ( guess + r ) / 2;

//  cout <<"Guess: " << guess << endl;
//  cout <<"Last Guess: " << lastGuess << endl;

    cout << "Guess : " << guess  << endl;
    cout << "Last Guess 1% = " << lastGuess + ( lastGuess * 0.01 ) << endl;
    cout << "r = " << r << endl;

} while( guess >= lastGuess * 0.01 );
cout << r;

return 0;
}

The program computes the right answer for r, but the loop doesn't terminate despite guess being greater than 1% added to lastGuess.

This program produces the following output when inputting 144 as n.

....
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
....

The root (r) is correct (12). The guess is LESS than lastGuess (12 < 12.12), which should return a false to the condition, correct?. Why is the loop not ending?

Upvotes: 4

Views: 7249

Answers (4)

FrankGray
FrankGray

Reputation: 1

I had the same problem in my book. This is what I wrote and it works perfect.

#include <iostream>
using namespace std;
int main()
{
    double guess, root, previousGuess;
    int number;
    cout << "Enter a number to find the Babylonian square root.\n";
    cin >> number;
    cout << "You want to find the square root of " << number << ".\n";
    cout << "Enter a guess for the square root.\n";
    cin >> guess;

    do
    {
        root = number / guess;
        previousGuess = guess;
        guess = (guess + root ) / 2;

    } while(guess < 0.99*previousGuess || guess > 1.01*previousGuess);

    cout << "The answer is " << guess << ".\n";
    return 0;
}

Upvotes: 0

Ashot Madatyan
Ashot Madatyan

Reputation: 81

To properly exit the loop, use something similar to this.

void f(int N)
{
    double x = N / 4;
    double prev = 0.0f;

    while(1)
    {
        x = 0.5 * (x + N / x);
        if (prev == x)
            break;

        prev = x;
        printf("val: %f\n", x);
    }

    printf("SQRT(%d) = %f\n", N, x);
}

Upvotes: 0

John Kugelman
John Kugelman

Reputation: 362087

If you want to add 1% you need to multiply by 1.01, not 0.01.

while( guess >= lastGuess * 1.01 );

By the way, this iterates while guess is growing by more than 1%. You should also allow for the opposite, that it may have shrunk by more than 1%. The approximation could approach the answer from either direction. (It will approach positive roots from the right and negative roots from the left.)

Upvotes: 4

Hemant Gangwar
Hemant Gangwar

Reputation: 2272

While printing your lastGuess you are using 

 lastGuess + ( lastGuess * 0.01 )

But while checking loop condition you are using

lastGuess*0.01

So in loop condition use the same equation which you are using for printing lastGuess value.

Upvotes: 3

Related Questions