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

Question

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?

Answer 1

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.)