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.