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.

SICP Exercise 1.45: Damp Roots

We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of y→x/y does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped y→x/y². Unfortunately, the process does not work for fourth roots -- a single average damp is not enough to make a fixed-point search for y→x/y³ converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of y→x/y³) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute n^th roots as a fixed-point search based upon repeated average damping of y→x/y^n-1. Use this to implement a simple procedure for computing n^th roots using fixed-point, average-damp, and the repeated procedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

First of all we know that the n^th root of x can be calculated as the fixed point of the equation y→x/y^n-1, so let's define a procedure that generates the equivalent lambda expression:

(define (nth-root-function x n)
  (lambda (y) (/ x (expt y (- n 1)))))

And then we can produce some test code for figuring how many average damps we need for a particular root. To do this we want to apply average-damp some number of times to the appropriate nth-root-function expression, and then use that to try to calculate a fixed point. If we're not doing enough average damping then the algorithm will never converge and the interpreter will hang. Here's the test code:

(define (damped-nth-root x n a)
  (if (= a 0)
      (nth-root-function x n)
      ((repeated average-damp a) (nth-root-function x n))))

(define (test-nth-root-damping x n a)
  (fixed-point (damped-nth-root x n a) 1.0))

When we start experimenting with this we quickly find a pattern:

n	2 - 3	4 - 7	8 - 15	16 - 31	32 - 63
Required Average Damps	1	2	3	4	5

Note how the required average damps increases by one each time n reaches the next power of 2. In other words, we want to average damp ⌊log₂n⌋ times.

Now let's define a procedure that does this:

(define (nth-root x n)
  (let ((damps (floor (/ (log n) (log 2)))))
    (fixed-point (damped-nth-root x n damps) 1.0)))

And we can check it works:

> (nth-root 4 2)
2.000000000000002
> (nth-root 4 4)
1.414213562373095
> (nth-root 4 8)
1.1892071150032364
> (nth-root 4 16)
1.0905077327148582
> (nth-root 4 32)
1.0442737827236872
> (nth-root 4 64)
1.0218971491473008
> (nth-root 4 128)
1.0108892864974073
> (nth-root 4 256)
1.0054299014117003
> (nth-root 4 512)
1.002711275223178
> (nth-root 4 1024)
1.001354719985141
> (nth-root 4 2048)
1.000677130741309
> (nth-root 4 4096)
1.0003386176117304

The Mystery of the Missing Exercises

I've noted before that I'm playing catch-up with writing up my solutions to the SICP exercises. As I'm writing this (well, technically, as of Tuesday coming if you count our weekly meeting) I've got as far as exercise 2.58. That's a grand total of 104 exercises. I've just finished writing up exercise 1.44, which means I've not long passed 40% of the backlog and, if I'm lucky, I might have got halfway caught up by the end of today!

While I'm playing catch-up writing up a solution is, for the most part, just a case of finding the work I did for the exercise at the time and wrapping it in some hopefully intelligible prose. However, disaster's just struck! I can't find my notes for exercises 1.45 or 1.46!

This is a catastrophe!

I'm going to have to... do them again from scratch!

However will I cope?

You never know, my write-ups might be more sensible for these two exercises as I'll actually be working them out as I'm writing them rather than regurgitating notes that are several weeks old.