Exercise 2.16 of SICP

2009-08-01

sicp

Exercise 2.16: Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

The errors are a lot tighter for par2than 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%. Even though the fraction is algebraically equivalent to A evaluating the intervals gives very different answers.

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

In order to devise a system that doesn’t have this problem would mean it would have to be smart enough to detect duplicate entries and rewrite them in a more interval arithmetic efficient manner. At a minimum it would have to analyze code of this form:

(div-interval (interval-pow A 7) (interval-pow A 6))

and reduce it to A and than evaluate it. Transforming the resistor example is even tougher.

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

The program would have to recognize division and simplify it by dividing the numerator and denominator by r1 and r2. Both the exponent and parallel resistor examples would have to be transformed symbolically since simplifying arithmetically would only introduce errors. I do not think it is feasible to write a program like this with the current lisp knowledge learned in the book so far.

Contents