C++ Finding square root without sqrt function loop glitching

Question

So I am making this as a homework assignment. I understand that there are so many ways that this code could be more efficient and accurate but this is the way my professor wants it done.

I am having problems with the loop. When I ask for the square root of 67 it does find it but it loops the correct answer 3 times.

Enter a value to be square rooted: 
67
33.5
guess = 17.75
guess = 10.7623
guess = 8.49387
guess = 8.19096
guess = 8.18535
guess = 8.18535
guess = 8.18535
The program took 7 guess to find an estimation.

When I try to find the square root of 5 it finds it but continues to loop indefinitely

using namespace std;

int main()
{
double guess2;
double squarenumber;
double guess1;
int numofguess = 0;

cout << "Enter a value to be square rooted: " << endl;
cin >> squarenumber;
guess1 = squarenumber/2;
cout << guess1 << endl;

do 
{

guess2 = (guess1 - (((guess1 * guess1) - squarenumber)/(2* guess1)));
guess1 = guess2;

cout << "guess = " << guess2 << endl;

numofguess = numofguess + 1;

} while ((guess2 * guess2) > squarenumber);

cout<< "The program took "<< numofguess <<" guess to find an estimation.";

return 0;
}

What did you observe, while stepping through your code, line by line, in a debugger? — Algirdas Preidžius, Feb 16 '17 at 00:04
Try printing `guess2 * guess2` each time through the loop. Make sure to print it with lots of digits of precision. — Barmar, Feb 16 '17 at 00:05
A double holds more than 6 decimal digits, so there is probably a difference in the digits you don't display. Check this post [Is floating point math broken?](http://stackoverflow.com/questions/588004/is-floating-point-math-broken) — Bo Persson, Feb 16 '17 at 00:05

Mickaël C. Guimarães · Answer 1 · 2017-02-16T01:19:30.327

1

I think that what you are missing is a proper exit condition. Your code is written to loop indefinitely until the guess is "perfect". You should have an exit condition checking if current guess is the same as previous guess, which obviously means that you won't do any better. Here is my suggestion based on your code :

using namespace std;

int main()
{
double guess2;
double squarenumber;
double guess1;
int numofguess = 0;

cout << "Enter a value to be square rooted: " << endl;
cin >> squarenumber;
guess2 = guess1 = squarenumber/2;
cout << guess1 << endl;

const double epsilon = squarenumber * 1E-6;
do 
{
 guess1 = guess2;
guess2 = (guess1 - (((guess1 * guess1) - squarenumber)/(2* guess1)));


cout << "guess = " << guess2 << endl;

numofguess = numofguess + 1;

} while ((guess2 * guess2) > squarenumber && fabs(guess2-guess1) > epsilon);

cout<< "The program took "<< numofguess <<" guess to find an estimation.";

return 0;
}

edited Feb 16 '17 at 01:19

answered Feb 16 '17 at 00:13

Mickaël C. Guimarães

1,020
2
14
32

this will not work obviously, because after the `guess1=guess2;` line, `fabs(guess2-guess1)` is always zero – user31264 Feb 16 '17 at 00:18
You're right... I edited the code to fix this stupid mistake. – Mickaël C. Guimarães Feb 16 '17 at 00:22
I'd use `if (fabs(...) – user31264 Feb 16 '17 at 00:23
`epsilon` needs to be a fraction of `squarenumber` (`squarenumber * 1E-6`, depending on how accurate you want your root to be), not a constant. Consider what happens when `squarenumber` is really large (2E30) or really small (5E-20). – 1201ProgramAlarm Feb 16 '17 at 00:50
Yes, I didn't think about epsilon value on all range of possible values... I fixed the answer (also considered @user31264 improvement to remove unneeded variable) – Mickaël C. Guimarães Feb 16 '17 at 01:21

Jason Lang · Answer 2 · 2017-02-16T08:25:12.943

Mickaël C. Guimarães's answer is basically correct, check for an episolon value (absolute difference from the correct answer and your answer). But the "(guess2 * guess2) > squarenumber" should be dropped completely. That's because the value could in theory overshoot and be too low. The algorithm actually goes upwards if the value is too low. e.g. if you want SQRT(25) and your "guess1" prediction is way too low at 2, then guess2 would equal

(2 - (((2 * 2) - 25)/(2* 2))) = 7.25;

And on the next iteration then falls to 6.725624, so heads in the right direction. Low values actually get boosted up and eventually approach the target. By stopping if the value drops below the true SQRT then you might get "false positives" where too low values are accepted as accurate enough.

The times when the system got "stuck" were basically like the story Acchiles and the Tortoise. At each step, the system was dividing the remaining distance to go by some amount, but the change was therefore smaller each step, and could in theory never converge on the exact value, therefore you decide how much accuracy you want so that it finishes in a set time.

Additionally, the issue where the system seemed to take too many steps to converge is because floating point numbers are stored in higher precision, but cout has limited display precision. You can control that by sending setting values to cout before the print commands:

std::cout << std::fixed; // force all values to show to the same decimals
std::cout << std::setprecision(6); // set how many places to show

These code can be streamed to cout in one command before the value to print as well:

std::cout << std::fixed << std::setprecision(6) << "guess = " << guess2 << endl;

C++ Finding square root without sqrt function loop glitching

2 Answers2