SICP Exercise 2.14 parallel resistors

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:



and



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.


Exercise 2.14.  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

 The code and tests are here.

 (The tests are also pasted below with some observations highlighted.)

 ; Tests

 Welcome to DrRacket, version 6.11 [3m].
Language: racket, with debugging; memory limit: 128 MB.
> (define R1 (make-center-percent 25 0.2))
> (show-int R1)
Center: 25.0
Width: 0.05000000000000071
> ; Expressions that algebraically evaluate to 1
(show-int (div-interval R1 R1))
Center: 1.0000080000320002
Width: 0.0040000160000639995
> ; Expressions that algebraically evaluate to 1
(show-int (div-interval (div-interval (mul-interval R1 R1) R1) R1))
Center: 1.0000320002560015
Width: 0.008000096000640056
> ; Expressions that algebraically evaluate to 1
(show-int (div-interval (div-interval (div-interval (mul-interval (mul-interval R1 R1) R1) R1) R1) R1))
          
Center: 1.0000720010560094
Width: 0.012000304003264128

 ; We can see that as intervals get repeated, the error bounds become looser and the center shifts too

 > ; Expressions that algebraically evaluate to 0
(show-int (sub-interval R1 R1))
Center: 0.0
Width: 0.10000000000000142
> ; Expressions that algebraically evaluate to 0
(show-int (sub-interval (sub-interval (add-interval R1 R1) R1) R1))
Center: 0.0
Width: 0.20000000000000284
> (show-int (sub-interval (mul-interval R1 R1) (mul-interval R1 R1)))
Center: 0.0
Width: 5.000000000000114

  We can see that as intervals get repeated, the error bounds become looser


 > (define R2 (make-center-percent 45 0.1))
> (par1 R1 R2)
'(16.001530066338542 . 16.14158143194335)
> (par2 R1 R2)
'(16.045021815320794 . 16.09782794778515)
> (show-int (par1 R1 R2))
Center: 16.07155574914095
Width: 0.07002568280240418
> (show-int (par2 R1 R2))
Center: 16.07142488155297
Width: 0.026403066232177252
> ; we can see that par2 above produces tighter error bounds

 (show-int (div-interval R1 R1))
Center: 1.0000080000320002
Width: 0.0040000160000639995
> (show-int (div-interval R2 R2))
Center: 1.000002000002
Width: 0.002000002000001999
> (show-int (div-interval R1 R2))
Center: 0.5555572222238889
Width: 0.0016666683333350085
> (show-int (div-interval R2 R1))
Center: 1.8000108000432
Width: 0.005400021600086347
> (show-int (mul-interval (div-interval R2 R1) (div-interval R1 R2)))
Center: 1.0000180000900003
Width: 0.006000042000186001
> (show-int (div-interval (mul-interval (div-interval R2 R1) (div-interval R1 R2)) (mul-interval (div-interval R2 R1) (div-interval R1 R2))))
Center: 1.000072001008008
Width: 0.012000300002964037
> ; the above two tests show that even though the expressions algebraically evaluate to 1, the error increases with repeated variables

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 2.56 differentiation rule

Image
Exercise 2.56.    Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the  deriv  program and defining appropriate procedures  exponentiation? ,  base ,  exponent , and  make-exponentiation . (You may use the symbol  **  to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. SOLUTION The code and tests are here .
Read more

SICP Exercise 1.28 (Miller-Rabin Test)

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st power modulo  n  using the  expmod  procedure. However, whenever we perform the squaring step in  expmod , we check to see if we have discovered a ``nontrivial square root of 1 modulo  n ,'' that is, a number not equal to 1 or  n  - 1 whose square is equal to 1 modulo  n . It is possible to prove that if such a nontrivial square root of 1 exists, then  n  is not prime. It is also possible to prove that if  n  is an odd number that is not prime, then, for at least half the numbers a < n , co
Read more

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain. SOLUTION & DISCUSSION The streams based procedure 'solve' in this exercise exposed several issues in my metacircular evaluator implementation. I discovered that streams are not at all handled properly by my evaluator. Moreover, the &
Read more