SICP 2.16 interval-arithmetic (scheme)

Question

This isn't a homework question, I'm just left unsatisfied with my understanding of interval arithmetic and the implications of exercise 2.16.

The interval arithmetic defined by section 2.14 does not exhibit the properties of normal arithmetic. Two should be equivalent operations, (r1*r2)/(r1 + r2) and 1/(1/r1 + 1/r2), give different results. The exercise asks why this is the case, and if it is possible to construct an interval-arithmetic system in which this is not the case.

The section is addressing the calculation of error margins of resistance of electrical components. I'm not sure I understand what it would mean, in these terms, to multiply and divide intervals. What is the application to multiplying two intervals together?

Is it possible to construct an interval-arithmetic system without the problem in this example?

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.4

(define (make-interval a b)
  (cons a b))

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))

(define (make-center-percent c p)
  (make-center-width c (* c (/ p 100.0))))

(define (lower-bound i)
  (car i))

(define (upper-bound i)
  (cdr i))

(define (center i)
  (/ (+ (upper-bound i) (lower-bound i)) 2))

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

(define (percent i)
  (* 100.0 (/ (width i) (center i))))

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

(define (sub-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) (lower-bound y)))
        (p3 (* (lower-bound x) (lower-bound y)))
        (p4 (* (lower-bound x) (lower-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

(define (div-interval x y)
  (if (= (width y ) 0) 
      (error "division by interval with width 0")
      (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))))

(define (parl1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))

(define (parl2 r1 r2)
  (let ((one (make-interval 1 1)))
              (div-interval one
                           (add-interval (div-interval one r1)
                                         (div-interval one r2))))

(define (r1 (make-interval 4.0 3.2)))
(define (r2 (make-interval 3.0 7.2)))

(center (parl1 r1 r2))
(width (parl1 r1 r2))
(newline)
(center (parl2 r1 r2))
(width (parl2 r1 r2))

Answer 1

This happens because the operations in the interval arithmetic do not have the arithmetic structure of a field.

As Sussman says, the exercise is difficult -- you need to check each of the operations of the field structure, and see which one is not satisfied.

The exercise asks us to show that the interval arithmetic is not the arithmetic of the ranges of functions.

A function like f (x) = x^2 defined on a domain [-1, 1] has the range [0,1], which is included in [-1,1] * [-1,1] = [-1,1], obtained by replacing the symbol x by the domain of the symbol x.

If we define a similar function that uses a different variable for each dimension, like in f(x,y) = x * y, then the range of this function, when defined on the domain [-1,1] * [-1,1], is the same as the interval [-1,1] * [-1,1] = [-1, 1], because x is used once, and so with y.

It happens that all the time when the function f(.., x, ..) is continous in each variable x we have the range arithmetics to be identical with interval arithmetics if each symbol is used only once in definition of f.

In the first formula of Alice, parallel resistor is computed repeating 2 times the variable R1, and 2 times the variable R2, and using the same argument the range of this function is included in the product of the corresponding intervals obtained from the formula of the function, by replacing each name by corresponding domain interval, but it is not strictly the same.

We are asked either to rewrite any function such that the range of the rewritten function be the same as the interval obtained by applying the rewritten function's formula, wih names replaced by intervals equal to the domain of the corresponding name from the rewritten function, or to show that this is not possible for each possible function.

This problem is called dependency problem, and it is a large problem, whose understanding is out of the purpose of SICP, and requires differential equations in multiple variables to solve it.

The purpose of this exercise is , as Sussman himself said, just to show that data can be encoded in multiple ways. The focus is not on mathematics , but on data abstraction.

Answer 2

The easiest way to understand the problem is looking at the very simple expression e = x/x where x is in [2,3]. If we use interval arithmetic, we get that e is in [2/3, 3/2], however second grade arithmetic shows that e=x/x=1. So what gives?

Well it is actually very simple: when using interval arithmetic I made the mistake of assuming x can have two different values at the same time. the maximum value of e is given when the numerator is 3 and the denominator is 2, however since both should always be the same this is not possible.

So, is it ever possible to use interval arithmetic? Yes, when all intervals appear only once, since then you would not have the problem of different values for the same variable in different interval calculations.

Is it possible to create an arithmetic package which does not have this problem? No, since not every function can be written where every variable appears only once. This problem is known as the dependency problem.