Exercises 1.29 thro 1.37

SICP today.org

Exercise 29

Simpson’s Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson’s Rule, the integral of a function f between a and b is approximated as

$$ \frac{h}{3} \left( y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + \ldots + 2yn-2 + 4yn-1 + y_n \right) $$

where $h = \frac{b - a}{n}$, for some even integer $n$, and $y_k = f ( a + k h )$ . (Increasing $n$ increases the accuracy of the approximation.) Define a procedure that takes as arguments $f$, $a$, $b$, and $n$ and returns the value of the integral, computed using Simpson’s Rule. Use your procedure to integrate cube between 0 and 1 (with $n$ = 100 and $n$ = 1000 ), and compare the results to those of the integral procedure shown above.

Solution

I’m going to regroup the terms for ease of computation into those multiplied by 1, 2 and 4. I’ll re-use the sum function that’s in the chapter.

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (cube x) (* x x x))

;; This will assume that n is even, which is fine for the tasks we
;; have been given of 100 and 1000. I'm not going to bother doing
;; e.g. Simpson's 3/8 rule.
(define (int-simpson f a b n)
  (define h (/ (- b a) n))
  (define (add-2h x) (+ x h h))
  (* (+ (f a)
        (* 2 (sum f (add-2h a) add-2h (- b h)))
        (* 4 (sum f (+ a h) add-2h b))
        (f b))
     (/ h 3)))


(display (int-simpson cube 0 1.0 100)) (newline)
(display (int-simpson cube 0 1.0 1000)) (newline)
;; 0.25000000000000044
;; 0.25000000000000083

For the same number of steps this gives a little more accuracy on the input values we have.

Exercise 30

Now do it iteratively.

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))

Reasonably straight forward one here.

Exercise 31

Did this for Zach ahead of time, will copy the question in later.

1. Defining product

(define (product f a g b)
  (if (> a b)
      1
      (* (f a)
         (product f (g a) g b))))

1. Need to still rewrite it as tail recursive but for approximating π we can use Wallis’ formula as shown

(define (approx n)
  (define (f n)
    (* (/ (* 2 n)
          (- (* 2 n) 1))
       (/ (* 2 n)
          (+ (* 2 n) 1))))
  (product f 1.0 inc n))

Doing it iteratively.

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

Exercise 32

Show that sum and product (Exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:

(accumulate combiner null-value term a next b)

Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate.

If your accumulate procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Solution

Using the bits developed in the previous exercise:

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

(define (accumulate-iter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))

Then

(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (sum-iter term a next b)
  (accumulate-iter + 0 term a next b))

(define (product term a next b)
  (accumulate * 1 term a next b))

(define (product-iter term a next b)
  (accumulate-iter * 1 term a next b))

Exercise 33

You can obtain an even more general version of accumulate (Exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following using filtered-accumulate:

1. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)
2. the product of all the positive integers less than n that are relatively prime to n (i.e., all positive integers i<n such that GCD(i,n)=1).

Solution

;; filtered accumulate
(define (filtered-accumulate predicate? combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner
       (if (predicate? a) (term a) null-value)
       (filtered-accumulate predicate? combiner null-value term (next a) next b))))


;; sum of squares of primes in an interval
(define (inc n) (+ n 1))

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


;; product of all positive integers less than n that are relatively prime to n
;; define the predicate to check for being relatively prime
(define (relative-prime? i n)
  (= (gcd i n) 1))

(define (id x) x)

;; predicate in filtered-accumulate only has one argument so we need some faffery
;; to get access to the namespace to get n
(define (product-of-relative-prime n)
  (define (relative-prime? i)
    (= (gcd i n) 1))
  (filtered-accumulate relative-prime? * 1 identity 1 inc (- n 1)))

Let and lambda

Exercise 34

Suppose we define the procedure

(define (f g) (g 2))

Then we have

(f square)
;; 4

(f (lambda (z) (* z (+ z 1))))
;; 6

What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain.

Solution

The evaluation steps will be

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

And will fail, since 2 is not an function.

Procedures as general methods

Exercise 35

Show that the golden ratio φ is a fixed point of the transformation $x \mapsto 1 + \frac{1}{x}$, and use this fact to compute φ by means of the fixed-point procedure.

Solution

The fixed point for $x \mapsto 1+\frac{1}{x}$ is defined as:

$$ x = 1 + \frac{1}{x} $$

Which we can reformulate as $x^2 - x - 1 = 0$. Using the standard discriminant approach of solving this we see

$$ x = \frac{1+ \sqrt{5}}{2} = \varphi $$

Now do it programatticaly.

(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)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(display (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
;; 1.6180327868852458

Exercise 36

Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in Exercise 1.22. Then find a solution to $x^x = 1000$ by finding a fixed point of $x \mapsto \frac{log(1000)}{log(x)}$. (Use Scheme’s primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)

Solution

Rewriting the above fixed-point definition to do what we need

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

;; undamped
(display (fixed-point (lambda (x) (/ (log 1000) (log x))) 2))
;; 2
;; 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


;; damped
(display (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2))

;; 2
;; 5.9828921423310435
;; 4.922168721308343
;; 4.628224318195455
;; 4.568346513136242
;; 4.5577305909237005
;; 4.555909809045131
;; 4.555599411610624
;; 4.5555465521473675
;; 4.555537551999825

Damping causes it to take a lot fewer steps to converge in this case.

Exercise 37

I’m not writing that one out. Hot damn.

recursive version

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

Estimating $\frac{1}{\varphi}$

k	result
4	0.6000000000000001
5	0.625
6	0.6153846153846154
7	0.6190476190476191
8	0.6176470588235294
9	0.6181818181818182
10	0.6179775280898876
11	0.6180555555555556
12	0.6180257510729613

Calculating $\frac{1}{\varphi}$ we get approximately 0.61803398875 so k must be at least 11 in order to have an approximation accurate to 4 decimal places.

Iterative

Start at the lowest fraction and work up:

(define (cont-frac-iter n d k)
  (define (iter i result)
    (if (= 0 i)
        result
        (iter (sub i) (/ (n i) (+ result (d i))))))
  (iter (sub k) (/ (n k) (d k))))