Exercise 1.7

The following procedures implement Newton’s method for finding square roots:

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

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

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

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

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

This implementation of the good-enough? function simply tests whether the square of the guess is within 0.001 of the original number, and is thus inadequate for very small and very large numbers. For example, on my machine this breaks for 1e48 and larger numbers, and for 0.0001 and smaller. It is obviously inadequate for finding the square root of any number smaller than that arbitrary test range because any useful answer would have to be much more precise. Likewise, with very large numbers, checking whether the guess squared is within 0.001 of the number will fail because large numbers cannot be stored with enough precision to be able to use 0.001 as a consistent test. On my machine, this led to an infinite loop for very large numbers, because the program never encountered a guess whose square was within 0.001 of the original number.

An improved implementation of good-enough? is given below:

(define (new-good-enough? current-guess last-guess)
  (< (/ (abs (- current-guess last-guess)) current-guess) 0.001))

This implementation checks the ratio of the change between the last guess and the current guess, and the current guess, and stops iterating when that ratio is very small. Because this procedure takes as arguments the current guess and the last guess, the following changes must be made to sqrt-iter:

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

This new and improved test eliminates the issues with both small and large numbers, because now the test is a function of the change in guesses, which gets smaller and smaller as they approach the square root, rather than a function of whether the difference between the square of the guess and the original number is less than some arbitrary constant.

Back to exercises