Exercise 2.15 of SICP

Exercise 2.15: Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa’s system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, par2 is a “better” program for parallel resistances than par1. Is she right? Why?

> (print (div-interval (make-center-percent 6.8 1) (make-center-percent 6.8 1)))
[1.0002000200020003,1.9998000199979908]
> (print (div-interval (make-center-percent 6.8 .1) (make-center-percent 6.8 .1)))
[1.000002000002,.19999980000021655]
> (print (div-interval (make-center-percent 6.8 .1) (make-center-percent 3.4 .1)))
[2.000004000004,.19999980000021655]
> (print (div-interval (make-center-percent 6.8 .1) (make-center-percent 1.7 .1)))
[4.000008000008,.19999980000021655]
> (print (div-interval (make-center-percent 6.8 .1) (make-center-percent 1.7 .01)))
[4.000000440000004,.1099999890000035]
> (print (par1 (make-center-percent 6.8 .1) (make-center-percent 1.7 .01)))
[1.3600022771855311,.19199981581619266]
> (print (par2 (make-center-percent 6.8 .1) (make-center-percent 1.7 .01)))
[1.3599998237438813,.028000014256019334]
> (print (par1 (make-center-percent 6.8 .1) (make-center-percent 6.8 .1)))
[3.4000136000136,.2999992000024115]
> (print (par2 (make-center-percent 6.8 .1) (make-center-percent 6.8 .1)))
[3.4000000000000004,.10000000000000857]
> (print (par1 (make-center-percent 6.8 10) (make-center-percent 4.7 5)))
[2.844199964577264,**22.613352145193346**] 
> (print (par2 (make-center-percent 6.8 10) (make-center-percent 4.7 5)))
[2.777440701636504,**7.05260392723452**]
(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)))))

Alyssa’s system will produce tighter error bounds. The errors are a lot tighter for par2 than par1. The reason that this is true is due to the fact that any operation between two intervals will increase errors. If two algebraically equivalent statements are evaluated, the statement with the least operations between intervals will produce less errors.

Here’s a slightly exaggerated example:

$$ A = 10 \pm 0.1 $$

$$ A = \frac{A^7}{A^6} = \frac{A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A}{A \cdot A \cdot A \cdot A \cdot A \cdot A} $$

> (define A (make-center-percent 10 1))
> (print A) 
[10.,.9999999999999963]
> (print (div-interval (interval-pow A 7) (interval-pow A 6)))
[10.084120477031101,12.92768447766068]

The most noticeable difference is between percent errors of 1% and 13%.

(define (interval-pow x n)
  (define (square i)
	(mul-interval i i))
  (cond ((= n 1) x)
		((= 0 (remainder n 2)) (square (interval-pow x (/ n 2))))
		((= 1 (remainder n 2)) (mul-interval x (interval-pow x (- n 1))))))