SICP Exercise 1.7: Not Quite Good-Enough Square Roots

The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?

Here we're using the following procedure definitions from section 1.1.7:

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (sqrt x)
  (sqrt-iter 1.0 x))

"Very small" numbers (i.e. numbers <0.001), have correspondingly "very small" square roots. As a result, good-enough? is not precise enough to allow sqrt-iter to loop enough times to get to an accurate solution for such numbers. As x tends towards 0, the guess at which good-enough? will return #t tends towards 0.03125, the square root of 0.0009765625 (which is less than 0.001). For example, using DrRacket:

> (sqrt 0.0000000000000000004)
0.03125

It should be noted, of course, that assuming that the usual fixed-width mantissa and exponent method of representing floating point numbers is used by the interpreter, it is not always possible for the interpreter to perform calculations with two numbers that differ by many orders of magnitude and still retain precision. As the initial guess is set at 1.0, when the x passed is small enough, as in the example above, this loss of precision will result in the initial invocation of improve evaluating to 0.5, and thereafter it will follow the path to 0.03125.

Further examples of how the approximation tends towards 0.03125 follow:

> (sqrt 0.001)
0.04124542607499115
> (sqrt 0.0001)
0.03230844833048122
> (sqrt 0.00001)
0.03135649010771716
> (sqrt 0.000001)
0.031260655525445276
> (sqrt 0.0000001)
0.03125106561775382
> (sqrt 0.00000001)
0.03125010656242753
> (sqrt 0.000000001)
0.03125001065624928
> (sqrt 0.0000000001)
0.03125000106562499

The inability to accurately perform calculations with numbers that are many orders of magnitude different also affects the calculation of sqrt with very large numbers. However, in this case the problem is that it is not possible for interpreter to represent a number that is within 0.001 of the original x, unless it is x itself. As a result, unless the evaluation of improve results in the exact square root of x and the subsequent calculation of (square guess) in good-enough? does manage to accurately produce x, an infinite loop will occur.

For example, using DrRacket, (sqrt 11730317098663263) results in an infinite loop.

To resolve this issue we could redefine good-enough? as follows so that it considers a guess good enough if refining the guess via improve changes the guess by less than a millionth of the guess:

(define (good-enough? guess x)
  (< (abs (- guess (improve guess x))) (/ guess 1000000)))

Using this redefined good-enough? gives, for example, the following results:

> (sqrt 11730317098663263)
22373979042.98612
> (sqrt 0.0000000001)
9.999999999999999e-006