SICP Exercise 1.36: Fixed points and Average damping

From SICP section 1.3.3 Procedures as General Methods

Exercise 1.36 asks us to modify fixed-point so that it prints the sequence of approximations it generates. We can do that with the newline and display primitives we saw in exercise 1.22.

Next we're asked to find a solution to x^x = 1000 by finding a fixed point of x → log(1000) / log(x). We can use Scheme's primitive log procedure 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 average procedure defined in the lecture notes.

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

We'll start with the fixed-point procedure we used in the last exercise. The try sub-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)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

Now we can find the value of x for x^x = 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)
2.0
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
4.555532270803653

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)
2.0
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
4.555537551999825

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 primitive.

> (expt 4.555532270803653 4.555532270803653)
999.9913579312362
> (expt 4.555537551999825 4.555537551999825)
1000.0046472054871

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.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.