SICP Solutions: Sections 1.3.2 and 1.3.3
Section 1.3.2 - Constructing Procedures Using Lambda
Exercise 1.34
It will blow up trying to use the number 2 in the function position. Observe:
(f f)
(f 2)
(2 2)
Section 1.3.3 - Procedures as General Methods
Exercise 1.35
We already know that:
\[\phi^2 = \phi + 1\]and dividing both parts by \(2\):
\[\phi = 1 + \frac{1}{\phi}\]So:
(define (phi x)
(fixed-point (lambda (y) (+ 1 (/ 1 y))) x))
Exercise 1.36
Here is fixed-point
now:
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(report-approx guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(define (report-approx a)
(display " *** ")
(display a)
(newline))
And we can define \(x^x\) as:
(define (x-on-x first-guess)
(fixed-point (lambda (x) (/ (log 1000) (log x))) first-guess))
(define (x-on-x-dumping first-guess)
(fixed-point (lambda (x) (+ (/ (log 1000) (* 2 (log x)))
(/ x 2))) first-guess))
Now we can call both:
(x-on-x 1.1)
=>
*** 1.1
*** 72.47657378429035
*** 1.6127318474109593
*** 14.45350138636525
*** 2.5862669415385087
*** 7.269672273367045
*** 3.4822383620848467
*** 5.536500810236703
*** 4.036406406288111
*** 4.95053682041456
*** 4.318707390180805
*** 4.721778787145103
*** 4.450341068884912
*** 4.626821434106115
*** 4.509360945293209
*** 4.586349500915509
*** 4.535372639594589
*** 4.568901484845316
*** 4.546751100777536
*** 4.561341971741742
*** 4.551712230641226
*** 4.558059671677587
*** 4.55387226495538
*** 4.556633177654167
*** 4.554812144696459
*** 4.556012967736543
*** 4.555220997683307
*** 4.555743265552239
*** 4.555398830243649
*** 4.555625974816275
*** 4.555476175432173
*** 4.555574964557791
*** 4.555509814636753
*** 4.555552779647764
*** 4.555524444961165
*** 4.555543131130589
*** 4.555530807938518
4.555538934848503
34 steps. Now with dampening:
(x-on-x-dumping 1.1)
=>
*** 1.1
*** 36.78828689214517
*** 19.352175531882512
*** 10.84183367957568
*** 6.870048352141772
*** 5.227224961967156
*** 4.701960195159289
*** 4.582196773201124
*** 4.560134229703681
*** 4.5563204194309606
*** 4.555669361784037
*** 4.555558462975639
*** 4.55553957996306
4.555536364911781
13 steps. Dampening helps a lot in this case.
Exercise 1.37
We can define cont-frac
as such:
(define (cont-frac n d k)
(cont-frac-iter n d k 1))
(define (cont-frac-iter n d k i)
(if (= i k)
(/ (n i) (d i))
(/ (n i)
(+ (d i) (cont-frac-iter n d k (inc i))))))
It takes 11 iterations to reach four-digit accuracy:
(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 11)
=>
0.6180555555555556
This was of course a recursive process. We can write an iterative now:
(define (cont-frac n d k)
(cont-frac-iter n d k k 0))
(define (cont-frac-iter n d k i)
(if (= i 0)
res
(let ((next (/ (n i) (+ (d i) res))))
(cont-frac-iter n d k (dec i) next))))
Note that the iterative solution has to calculate the result from the ground up, starting from \(k\) all the way up to \(1\).
Exercise 1.38
We need to define d
:
(define (d i)
(if (= (remainder (+ i 1) 3) 0)
(* (/ (+ i 1) 3) 2)
1))
(define (euler k)
(+ 2 (cont-frac (lambda (i) 1.0) d k)))
For \(k = 8\) the approximation is accurate to 4 decimal places.
Exercise 1.39
Again, using cont-frac
:
(define (tan-cf x k)
(cont-frac
(lambda (i) (if (= i 1) x (- (* x x))))
(lambda (i) (- (* 2 i) 1))
k))