[SICP 1.3.1] Exercise 1.29-1.32 Memo

SICP Exercise 1.29 – Create more accurate method of numerical integration using Simpson’s Rule.
The following process works.

(define (sympson f a b n)
(define (term-num x)
(if (even? x) 2 4)
)
(define (y k) ( f (+ a (* k h))))
(define h (/ (- b a) n))
(define (next x) (+ x 1))

(define (term x)
(* (term-num x) ( y x ))
)

(* (/ h 3.0) (+ (y 0) (sum term 1 next (- n 1)) (y n)))
)
[shell]
Then let's compare this method to the one which isn't using Simpson's Rule. First we write the code as follows:
[shell]
(integral cube 0 1 0.001)
(sympson cube 0 1 10)
(sympson cube 0 1 100)

And we’ll get the following output.

0.24999987500000073
0.25
0.25

It looks like the new one outperforms the previous one.

SICP Exercise 1.30 – Rewrite sum method as a linear iterative process.
You can easily solve this by using what we’ve learned so far.

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

SICP Exercise 1.31(a) – 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 approximationas to PI using the formula: PI/4 = (2*4*4*6*6*8*…) / (3*3*5*5*7*7*…)

We can get the definition of product by changing sum method we’ve created just before.

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

Then the definition of factorial is:

(define (factorial n)
(product (lambda (x) x) 1 (lambda (x) (+ x 1)) n)
)

And the definition of the quarter of PI is:

(define (qrt-pi)
(define (term x)
(if (even? x) (/ (+ x 2.0) (+ x 1)) (/ (+ x 1.0) (+ x 2)))
)
(define (next x) (+ x 1) )
(product term 1 next 30000)
)

To confirm these codes, we write as follows:

; Factorial
(factorial 7) ; 5040
; PI
(* 4.0 (qrt-pi)) ; 3.14.....

It looks like this works well.

SICP Exercise 1.32(a) – Show that sum and product 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)

So let’s create this by using linear iterative process. We can easily get the abstraction by watching two functions( sum, product ) and extracting the common points.

(define (accumulate 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 two functions will be as follows:

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

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

Now let’s check their behavior.

(define (total term from to)
(sum term from (lambda (x) (+ x 1)) to)
)

(define (factorial n)
(product (lambda (x) x) 1 (lambda (x) (+ x 1)) n)
)

(total (lambda (x) x) 1 10) ; 55
(total (lambda (x) (* x x)) 1 5) ; 55
(factorial 7) ; 5040

Voila.

<<

Top

>>

Leave a Reply