Solution to SICP Exercise 1.7

Structure and Interpretation of Computer Programs

Solution to Exercise 1.7:

The results for small values become very inaccurate. For example, the root of the square of 0.001, which we might expect to be itself is found to be off by a factor of ~31.3 times.

> (sqrt (square 0.001))
0.031260655525445276

As the values grow larger, the precision of the guess comes into play. Eventually the computer becomes unable to represent the guess to a precision of 0.001. In such cases, the program can endlessly alternate between two guesses that are more than 0.001 away from the true square root. On my x86 machine with DrScheme, this can be seen with the following expression

> (sqrt 1e13)

Here is an implementation of good-enough/ that follows the alternative strategy given in the exercise

(define (good-enough? guess prev-guess)
(< (/ (abs (- guess prev-guess))
guess)
0.001))

The x parameter is replaced by prev-guess, which necessitates a change to sqrt-iter and sqrt, as shown here:

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

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

I’ve used an initial prev-guess of zero, which ensures that the initial guess of one is never good enough, thus forcing at least one iteration of the algorithm.

This implementation performs much better on the two troublesome examples given above:

> (sqrt (square 0.001))
0.0010000001533016628
> (sqrt 1e13)
3162277.6640104805

Advertisements