SICP Exercise 1.29

Question

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 h3(y0+4y1+2y2+4y3+2y4++2yn2+4yn1+yn), where h=(ba)/n, for some integer n, and yk=f(a+kh). (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.

Answer

Here is the answer code:

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

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

(define (simpsons_rule f a b n)
  (define h (/ (- b a) n))
  (define (yk k count) (* count (f (+ a (* k h)))))
  (define (term k)
    (cond ((or (= k 0) (= k n)) (yk k 1))
          ((even? k) (yk k 2))
          (else (yk k 4))))
  (* (/ h 3) (sum term 0 inc n)))

(simpsons_rule cube 0 1.0 100)
(simpsons_rule cube 0 1.0 1000)

And the results. Interestingly, using n=1000 actually gives us a slightly worse accuracy. Nevertheless, both results are highly accurate.

0.24999999999999992
0.2500000000000003

Let us compare this to the results we previously received from integral (using a dx-value of 0.0000001):

0.25000000112005644

This result is much less accurate. Not only that, it took much longer to compute as well. Looks like Simpson’s rule is to be preferred for calculating integrals.