SICP Exercise 1.46: Iterative Improvement

Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section 1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve.

Let's look again at fixed-point:

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

This has the basis for our iterative-improve in it. The inner procedure try keeps refining the guess using f until such time as close-enough? indicates that we've reached a tolerable approximation to the result. Our procedure iterative-improve is very similar to this. The main differences are that:

• It will need to take close-enough? as a parameter, rather than having it defined as an inner procedure.
• It won't take a first-guess as a parameter...
• ...instead, it will return a single-parameter lambda expression, where the parameter is the first guess.

Here's what my implementation looks like:

(define (iterative-improve close-enough? f)
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (lambda (first-guess) (try first-guess)))

We can then use this to re-implement sqrt and fixed-point. In the case of sqrt our close-enough? procedure can ignore guess and concentrate on the value of next passed to it, checking if squaring it comes within an acceptable tolerance of the value we're trying to find a square root for. As for fixed-point, as this formed the basis for our iterative-improve, the translation is extremely straightforward:

(define (sqrt x)
  ((iterative-improve (lambda (guess next) (< (abs (- (square next) x)) 0.001))
                      (lambda (guess) (average guess (/ x guess))))
   1.0))

(define (fixed-point f first-guess)
  ((iterative-improve (lambda ( v1 v2) (< (abs (- v1 v2)) tolerance))
                      (lambda (guess) (f guess)))
   1.0))

Here they are in action (the fixed-point examples are from section 1.3.3):

> (sqrt 4)
2.0000000929222947
> (sqrt 9)
3.00009155413138
> (fixed-point cos 1.0)
0.7390822985224024
> (fixed-point (lambda (y) (+ (sin y) (cos y)))
               1.0)
1.2587315962971173

Well, there we have it! End of chapter 1... and time for a break. I've been writing-up exercises for most of the day so I think I'll have some down time for a wee bit. I might try to get a few more done in an hour or two though.