## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.07

## Problem

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

## Solution

Here is `good-enough?` as implemented in section 1.1.7:

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

`good-enough?` uses an absolute error metric, i.e., its error
threshold is the same regardless of the magnitude of argument `x`.
For values of `x` near the threshold, 0.001, the `good-enough?` test may
perform poorly. For example, if `x` is 0.002, any guess whose
square falls in the interval (0.003, 0.001) will pass the
`good-enough?` test, despite the fact that the square root of 0.003
and the square root of 0.001 are poor approximations of the square
root of 0.002. In fact, for values of `x` less than the threshold,
the `good-enough?` test will pass for any guess whose square is also
less than the threshold; e.g., (`good-enough?` 0.001 0.000000001) would
the test and produce a value of 0.001 for the square root of
0.000000001.

When performing arithmetic operations with limited precision, the
difference between two successive numbers increases as the magnitude
of the numbers increases. It's common to call this difference
ε. For any number x(n) and its limited-precision successor
x(n+1) whose ε is greater than or equal to 0.001, `good-enough?`
will never return `#t`, meaning that a square root implementation
which uses `good-enough?` will never find a value for numbers >= x(n).

Returning to the question:

*An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and 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's one way to implement such a procedure:

(define (sqrt-iter guess prev-guess x) (if (good-enough? guess prev-guess) guess (sqrt-iter (improve guess x) guess x))) (define (improve guess x) (average guess (/ x guess))) (define (average x y) (/ (+ x y) 2)) (define (good-enough? guess prev-guess) (< (abs (- guess prev-guess)) (* 0.001 guess)))

We can seed the calculation with the initial `guess` equal to 1 and
`prev-guess` equal to 0.

This alternative strategy for finding square roots does work better for small numbers. For small numbers, each successive guess gets smaller, so comparing the new guess to a fraction of the previous guess means that the process will converge.

However, extremely small numbers with limited precision may still
produce poor approximations of the real square root when the number
of significant digits in the guess approaches the precision limits
of the value of the expression `(* 0.001 guess)`.

This alternative strategy for finding square roots is a mixed bag
for large numbers. As long as the computer's limited-precision
arithmetic is sufficient to guarantee that the ratio of a
number and its successor is always less than 0.001,
this implementation of `good-enough?` doesn't have termination
problem that the original implementation has.

However, because this `good-enough?` implementation only requires that
a guess is within 1/1000th of the previous guess to be good enough,
`good-enough?` has a relative error margin of +/- 0.1%. (It's 0.1%
because we multiply the guess by a scale factor 0.001 to determine
the guess's "goodness"; different scale factors would have a
different margin of error). For large numbers, this error margin
might be unacceptable. In fact, for numbers greater than 1, the
relative error version of the `good-enough?` procedure might be quite a bit less
accurate than the absolute error `good-enough?` procedure.