Chapter 1, Building Abstractions with Procedures

Section - Formulating Abstractions with Higher-Order Procedures

Exercise 1.36


Modified fixed-point procedure to print guesses:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(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)))
      (display next)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))
      )
  ) 
  (try first-guess)
)

(define (average a b)
  (/ (+ a b) 2)
) 

Solving $x \mapsto \frac { \log 1000 } {\log x}$ without average-damping:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
> (fixed-point (lambda (x) (/ (log 1000) (log x))) 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
4.555532270803653

Solving $x \mapsto \frac { \log 1000 } {\log x}$ with average-damping:

1
2
3
4
5
6
7
8
9
10
11
> (fixed-point (lambda (x) (average x (/ (log 1000) (log x))) ) 2.0)
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
4.555537551999825
4.555537551999825

As we can see there are 34 guesses without avg-damping and only 9 guesses with avg-damping. Clearly we can see here how damping makes fast converge.