SICP. 1.3/1.3.1
2023-02-05 Sun

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} (y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + ... + 2y_{n-2} + 2y_{n-1} + y_n)\),

where \(h = (b - a) / n\), for some even integer \(n\), and \(y_k = 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:

#lang sicp
(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 (integral f a b n)

  (define (f-mod x)
    (define (f2 x)
      (* 2 (f x)))
    (define (f4 x)
      (* 4 (f x)))
    (cond ((= x a) (f x))
          ((= (- (/ x (/ (- b a) n)) a) n) (f x))
          ((= (remainder (- (/ x (/ (- b a) n)) a) 2) 0) (f2 x))
          (else (f4 x))))

  (define (next x)
    (+ x
       (/ (- b a) n)))

  (* (/ (/ (- b a) n) 3)
     (sum f-mod
          a
          next
          (+ a (* n (/ (- b a) n))))))

(integral cube 0 1 100);; => 1/4
(integral cube 0 1 1000);; => 1/4

Exercise:

The sum procedure above generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition:

(define (sum term a next b)
  (define (iter a result)
    (if ⟨??⟩
        ⟨??⟩
        (iter ⟨??⟩ ⟨??⟩)))
  (iter ⟨??⟩ ⟨??⟩))

Answer:

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

Exercise:

1. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.[fn: The intent of Exercise 1.31 through Exercise 1.33 is to demonstrate the expressive power that is attained by using an appropriate abstraction to consolidate many seemingly disparate operations. However, though accumulation and filtering are elegant ideas, our hands are somewhat tied in using them at this point since we do not yet have data structures to provide suitable means of combination for these abstractions. We will return to these ideas in 2.2.3 when we show how to use sequences as interfaces for combining filters and accumulators to build even more powerful abstractions. We will see there how these methods really come into their own as a powerful and elegant approach to designing programs.] Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. Also use product to compute approximations to π using the formula…

   \(\frac{\pi}{4} = \frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdot \dots}{3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdot \dots}\)

2. If your product 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.

Answer:

Here is product.

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

Here is factorial defined in terms of product.

(define (factorial n)
  (define (inc x) (+ 1 x))
  (define (indentity x) x)
  (product identity 1 inc n))  

Here is one way of computing an approximation to \(\pi\).

(define (product* begin end)
  (define (identity x) x)
  (define (inc2 x) (+ 2 x))
  (product identity begin inc2 end))

(* (/ (* 2 (product* 4 8) (product* 4 6))
      (square (product* 3 7)))
   4.0)

My product procedure generates a recursive process (\(\Theta(n)\) in time and space). Here is a product that generates an iterative process (\(\Theta(n)\) in time, \(\Theta(1)\) in space — assuming tail call optimization).

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

1. 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.

2. 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.

Answer:

By looking at the recursive version of sum and product, we can observe that only certain elements in the two bodies are different. Those elements are:

• The first expression after the if;
• The procedure applied in the tail call;

As far as I can tentatively see, this means that the concepts expressed sum and product belong to a more general concept.

This latter concept abstracts over the two parts of the body mentioned. The first abstraction is an abstraction over a numeric value. The second abstraction is an abstraction over a procedure.

This is the procedure I would write to express the concept sum and product are instances of:

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

(sum identity 1 inc 5) ;; => 15
(accumulate + 0 identity 1 inc 5) ;; => 15

(product identity 2 inc 9) ;; => 362880
(accumulate * 1 identity 2 inc 9) ;; => 362880

My accumulate generate a recursive process. Here is an iterative version:

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

Exercise:

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$j (i.e., all positive integers \(i < n\) such that \(GCD(i,n)=1\)).

Answer:

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

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

(define (product-int-less-than-rel-prime-to n)
  (define (rel-prime-to-n x)
    (= (gcd x n)
       1))
  (filtered-accumulate * rel-prime-to-n 1 1 inc1 (- n 1)))