SICP exercise 1.36

From Drewiki

Problem

Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise 1.22. Then find a solution to by finding a fixed point of . (Use Scheme's primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)

Solution

Here's a modified fixed-point that prints its progress and a running count of guesses attempted:

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess guess-num)
    (let ((next (f guess)))
      (display "guess ")
      (display guess-num)
      (display ": ")
      (display next)
      (newline)
      (if (close-enough? guess next)
          next
          (try next (+ guess-num 1)))))
  (try first-guess 1))

Using this definition to find the fixed point of with an initial guess of 2.0 requires 34 guesses on Chicken Scheme 3.1:

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)

Output:

guess 1: 9.96578428466209
guess 2: 3.00447220984121
guess 3: 6.27919575750716
guess 4: 3.75985070240154
guess 5: 5.2158437849259
guess 6: 4.1822071924014
guess 7: 4.82776509834459
guess 8: 4.38759338466268
guess 9: 4.6712500857639
guess 10: 4.48140361689505
guess 11: 4.6053657460929
guess 12: 4.52308496787189
guess 13: 4.57711468204734
guess 14: 4.54138248015145
guess 15: 4.56490324523083
guess 16: 4.54937267930334
guess 17: 4.55960649191329
guess 18: 4.55285387578827
guess 19: 4.55730552974826
guess 20: 4.55436906443618
guess 21: 4.556305311533
guess 22: 4.55502826357355
guess 23: 4.55587039670285
guess 24: 4.55531500119208
guess 25: 4.55568126354333
guess 26: 4.55543971573685
guess 27: 4.55559900999829
guess 28: 4.55549395753139
guess 29: 4.55556323729288
guess 30: 4.55551754841765
guess 31: 4.5555476793064
guess 32: 4.55552780851625
guess 33: 4.55554091291796
guess 34: 4.55553227080365
4.55553227080365

Now with average damping:

(define (average x y) (/ (+ x y) 2))
 
(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0)

Output:

guess 1: 5.98289214233104
guess 2: 4.92216872130834
guess 3: 4.62822431819546
guess 4: 4.56834651313624
guess 5: 4.5577305909237
guess 6: 4.55590980904513
guess 7: 4.55559941161062
guess 8: 4.55554655214737
guess 9: 4.55553755199982
4.55553755199982

This computation requires only 9 guesses using the same Scheme environment.