Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.14

From Drewiki
Jump to: navigation, search

Problem

After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two algebraically equivalent ways. He has written the following two programs, each of which computes the parallel-resistors formula differently:

(define (par1 r1 r2) 
  (div-interval (mul-interval r1 r2) 
                (add-interval r1 r2))) 
 
(define (par2 r1 r2) 
  (let ((one (make-interval 1 1))) 
    (div-interval one 
                  (add-interval (div-interval one r1) 
                                (div-interval one r2)))))

Lem complains that Alyssa's program gives different answers for the two ways of computing. This is a serious complaint.

Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals A and B, and use them in computing the expressions A/A and A/B. You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see exercise 2.12).

Solution

Here are the relevant routines from exercise 2.12 and from the text:

(define (make-interval a b) (cons a b))
 
(define (lower-bound i) (car i))
 
(define (upper-bound i) (cdr i))
 
(define (interval-width i)
  (/ (- (upper-bound i)
        (lower-bound i))
     2))
 
(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))
 
(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))
 
(define (make-center-percent center percent)
  (let ((width (* center ( / percent 100.0))))
    (make-center-width center width)))
 
(define (percent i)
  (* (/ (interval-width i) (center i)) 100.0))
 
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
 
(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))
 
(define (div-interval x y)
  (mul-interval x
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))
 
(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))
 
(define (par2 r1 r2)
  (let ((one (make-interval 1 1)))
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))

Here are a few tests that demonstrate Lem's findings:

(define R1 (make-center-width 40000 0.001))
 
(define R2 (make-center-width 80000 0.001))
 
(center (par1 R1 R2))

Output:

26666.6666666667


(percent (par1 R1 R2))

Output:

5.41666667231765e-06


(center (par2 R1 R2))

Output:

26666.6666666667


(percent (par2 R1 R2))

Output:

2.08333332238908e-06


Note that the percent tolerances are different.

Personal tools