SICP 1.3 exercises cont. 2Posted: January 21, 2013
(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.
I’ll just use substitution to illustrate what happens.
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.
(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.
(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.
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.