Exercise 1.36 asks us to modify
fixed-pointso that it prints the sequence of approximations it generates. We can do that with the
displayprimitives we saw in exercise 1.22.
Next we're asked to find a solution to xx = 1000 by finding a fixed point of x → log(1000) / log(x). We can use Scheme's primitive
logprocedure to compute natural logarithms.
Finally, we need to compare the number of steps it takes to find the fixed point with and without average damping. We'll use the simple
averageprocedure defined in the lecture notes.
(define (average x y)
(/ (+ x y) 2))
We'll start with the
fixed-pointprocedure we used in the last exercise. The
trysub-procedure looks like a good place to print each guess.
(define tolerance 0.00001)
(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)
Now we can find the value of x for xx = 1000 using this procedure. The book warns us not to use 1.0 as a starting value or else the procedure will attempt to divide by log(1) = 0, so let's start with an initial guess of 2.0.
> (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
The procedure took 35 steps to arrive at an answer of 4.555532270803653 without using average damping.
In order to use average damping we just need to modify the input function to average the input value of x with the computed value.
> (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0)
This time it took only 10 steps to come up with approximately the same answer. We can check the two answers by simply raising each result to itself using Scheme's
> (expt 4.555532270803653 4.555532270803653)
> (expt 4.555537551999825 4.555537551999825)
So in this case, the procedure using average damping not only arrived at an solution in a fewer number of steps, but the final result happened to be slightly more accurate as well. That won't always be the case, but it's good to know that we're not sacrificing accuracy by using averaging damping.
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.