SICP 1.3 exercises cont. 2

1.33

(define (filtered-accumulate combiner null-value term a next b filter)
  (if (> a b)
      null-value
      (if (filter a)
          (combiner (term a)
                    (filtered-accumulate combiner null-value term (next a) next b filter))
        (filtered-accumulate combiner null-value term (next a) next b filter))))

(define (sum-prime-squares a b)
  (filtered-accumulate + 0 square a inc b prime?))

(define (relative-primes n)
  (define (rel-prime? x)
    (= (gcd n x) 1))
  (filtered-accumulate * 1 identity 2 inc n rel-prime?))

Comments: Again, decently straightforward as long as prime? and gcd are available.

1.34

I’ll just use substitution to illustrate what happens.

(f f)
(f 2)
(2 2)

And 2 is not a valid operator, so the interpreter throws an error.

Comments: That took just a little bit of thinking. The way the question was posed I expected it to run forever/cause a stack overflow but using simple substitution makes it explicit what happens.

1.35

1 + \frac{1}{\phi} = 1 + \frac{1}{\frac{1 + \sqrt{5}}{2}}  = \frac{3 + \sqrt{5}}{1 + \sqrt{5}}  = \frac{\frac{2}{1+\sqrt{5}}(3 + \sqrt{5})}{2}  = \frac{\frac{6 + 2\sqrt{5}}{1+\sqrt{5}}}{2}  = \frac{\frac{(1+\sqrt{5})^2}{1+\sqrt{5}}}{2} \\  = \frac{1 + \sqrt{5}}{2}

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
1.61803278688525

Comments: I just realized that wordpress supports LaTeX although it’s ugly since align is not supported. Good enough for me though. Anyway this exercise was doing simple math, although I’m not sure I did this in the most intelligent way.

1.36

Modified procedure:

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

Without average damping:

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
2.0
9.96578428466209
3.00447220984121
6.27919575750716
3.75985070240154
5.2158437849259
4.1822071924014
4.82776509834459
4.38759338466268
4.6712500857639
4.48140361689505
4.6053657460929
4.52308496787189
4.57711468204734
4.54138248015145
4.56490324523083
4.54937267930334
4.55960649191329
4.55285387578827
4.55730552974826
4.55436906443618
4.556305311533
4.55502826357355
4.55587039670285
4.55531500119208
4.55568126354333
4.55543971573685
4.55559900999829
4.55549395753139
4.55556323729288
4.55551754841765
4.5555476793064
4.55552780851625
4.55554091291796
4.55553227080365

With average damping:

(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0)
2.0
5.98289214233104
4.92216872130834
4.62822431819546
4.56834651313624
4.5577305909237
4.55590980904513
4.55559941161062
4.555546552147374.55553755199982

Comments: This exercise forced me to reread the relevant sections, which was a definite plus. I am quite impatient so aiming to answer exercises seems to have been the best way to keep focused.

1.37

A recursive procedure is decently straightforward to write.

(define (cont-frac n d k)
  (define (run i)
    (if (= i k)
        (/ (n i) (d i))
      (/ (n i) (+ (d i) (run (+ i 1))))))
  (run 1))

As usual, iterative is a bit harder.

(define (cont-frac-2 n d k)
  (define (run i current)
    (if (= i 1)
        current
      (run (- i 1) (/ (n (- i 1) (+ (d (- i 1) current)))))
  (run k (/ (n k) (d k))))

Either way, it takes 13 steps to get accurate to 4 decimal places, which seems pretty good to me.

(/ 1 (cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0) 13))
1.61803713527851

(/ 1 (cont-frac-2 (lambda (i) 1.0)
           (lambda (i) 1.0) 13))
1.61802575107296

Comments: Again, a straightforward implementation exercise, which is always fun and confidence-building.

Edit: I made an off by one error in the iterative version.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s