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))