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

From Drewiki
Jump to: navigation, search

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.

Personal tools