Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 339
Anthony Santiago Avatar asked Mar 19 '23 10:03

Anthony Santiago


1 Answers

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

like image 118
John Kugelman Avatar answered Apr 09 '23 00:04

John Kugelman