Checking tolerance of Newton-Raphson method to calculate square root Finding the square root of $c$ is finding the solution to:
$$x^2 - c = 0.0$$
We can use Newton's method to successively approximate the solution. 
My question is how to check whether we are within $\epsilon$ of a solution. Why checking
$$|guess^2 - c| > \epsilon$$
leads to incorrect solutions and infinite loops in some cases? If you click here and scroll all the way down to the very last exercise, they go over some of those special cases. When using SqrtBug.java to calculate the square root of $16664444$, an infinite loop ensues at the $\epsilon = 1E-15$ they are using. I tried relaxing the tolerance to $\epsilon = 1E-8$ and that made it converge, but I want to understand why the infinite loop. Also, the square root of $1E-50$ is calculated incorrectly by SqrtBug.java.
To check tolerance, they instead use:
$$|guess - c / guess| > \epsilon \cdot guess$$
in Sqrt.java, which calculates the square roots of $1E-50$ and $16664444$ correctly. That leads to my other question, shouldn't it check for:
$$|guess - c / guess| > \epsilon$$
? Thank you.
 A: The formulation of tolerance:
$$ |\text{guess} - c/\text{guess}| > \epsilon \cdot \text{guess} $$
is attractive for two reasons besides the relative precision that it imposes as a termination criterion.  Bear in mind that the above is the condition to continue iteration.  If the condition is too loose, iteration will terminate prematurely, but if too tight, iteration may never terminate.
First: If guess is the current (possibly initial) approximation, note that when guess is above the square root, $c$/guess will fall below the square root (in exact arithmetic).  Conversely if guess is below the square root, then $c$/guess will lie above it.  For this reason the true square root should be between these, and the difference of those two computed values should overestimate the actual error (but only by a constant factor $\lt 2$ as convergence approaches).
Second: The Newton iteration can be expressed:
$$ \text{guess} \gets (\text{guess} + c/\text{guess})/2 $$
So we haven't wasted a division operation by computing $c/$*guess* if the outcome of the test is to continue the iteration.  This result will be used directly in forming the updated approximation to square root.
Now we come to the application of relative precision in deciding to continue or terminate iteration.  Any computation of a positive square root is liable to contain a rounding error resulting from normal floating point operations.  The absolute size of this error depends (because of the nature of the floating point format) on the size of the value being computed.  
If you take the square root of $16664444$, the result is slightly over $4000$ and the rounding error will accordingly be several orders of magnitude greater than the square root of $1E-50$, which is $1E-25$.  So if you impose a test for the absolute value of the error, as proposed with:
$$ |\text{guess} - c/\text{guess}| > \epsilon $$
then the same value of $\epsilon$ that does a reasonable job for $16664444$ will be too loose for $1E-50$, and a value that is right for $1E-50$ will be generally impossible to meet for arguments as large as $16664444$.
Therefore testing the relative value of the error as shown at top is the way to balance accuracy over a wide range of floating point arguments.  Note that this test is equivalent (in exact arithmetic) to:
$$ \frac{|\text{guess} - c/\text{guess}|}{\text{guess}} > \epsilon $$
(which should make apparent we are comparing relative error in guess to $\epsilon$), but the form of the test trades off a division for a multiplication in the form shown at top.  This would typically be computationally faster, if it mattered (and it might since we are doing the check once for each iteration).
