sicp-ex-2.14-2.15-2.16

Mathematical Explanation:

We can see it as a problem of finding extrema of n-variate functions. for R1, R2, R_, ... these are variables, The interval of R1, R2, R_, ... are the definition fields. The operations on variables are the function. And we want to find the maximum and minimum of the function in the definition fields.

For the general questions, It's very clear that for most functions, their extrema won't be found in the border, so we can't simple get the result by operating on lower and upper bound.

For the specific question there, the problem is that the functions Lem wrote assume the variables are independent. If the variables are dependent, the result is wrong.

For example, R1 = [1, 2]; R2 = R1 + 1=[2, 3], then R1 and R2 are dependent, so R1 - R2 = 1, and (sub-interval R1 R2) = [0, 2] is wrong.

Here, for par1, R1*R2 and R1+R2 are dependent, so (div-interval R1*R2 R1+R2) got wrong answer.

But, for pa2, [1,1] and R1; [1,1] and R2; 1/R1 and 1/R2; [1,1] and 1/R1 + 1/R2; they are all independent, so the result is right.

If we want let the result be correct, either we change the code fundamentally, or we need to ensure for each operation, their operands should be independent.

You will get the most insight by using intervals whose width is a ''small percentage of the center value''.

All 3 problems point to the difficulty of "identity" when dealing with intervals. Suppose we have two numbers A and B which are contained in intervals:

  A = [2, 8]
  B = [2, 8]

A could be any number, such as 3.782, and B could be 5.42, but we just don't know.

Now, A divided by itself must be 1.0 (assuming A isn't 0), but of A/B (the same applies to subtraction) we can only say that it's somewhere in the interval

  [0.25, 4]

Unfortunately, our interval package doesn't say anything about identity, so if we calculated A/A, we would also get

  [0.25, 4]

So, any time we do algebraic manipulation of an equation involving intervals, we need to be careful any time we introduce the same interval (e.g. through fraction reduction), since our interval package re-introduces the uncertainty, even if it shouldn't.

So:

2.14. Lem just demonstrates the above.

2.15. Eva is right, since the error isn't reintroduced into the result in par2 as it is in par1.

2.16. A fiendish question. They say it's "very difficult" as if it's doable. I'm not falling for that. Essentially, I believe we'd have to introduce some concept of "identity", and then have the program be clever enough to reduce equations. Also, when supplying arguments to any equation, we'd need to indicate identity somehow, since [2, 8] isn't necessarily the same as [2, 8] ... unless it is. Capiche?

A better explanation and some pointers to the interesting world of interval arithmetic http://wiki.drewhess.com/wiki/SICP_exercise_2.16

We have to leave the realm of interval arithmetic as soon as we start to talk about functions that have extrema somewhere inside intervals, or about functions like (A+B)/(A+C), which in principle cannot be reduced to the form with one occurrence of each variable. This is the meaning of dependency problem. By using interval arithmetic we will always get wrong results for such functions.

We cannot find correct answers using interval arithmetic, but we can find them by using analytical or numerical methods, e.g. Monte Carlo method. It's the problem of finding global minimum of a function of several variables. I saw the proposal to use MC in Weiqun Zhang's blog (in fact it is a standard method of finding extrema for very complex functions).

MC works even when all analytical methods fail. Dependency problem does not exist for these methods. For example, when you calculate A/A with Monte Carlo method, you just submit the same random value inside the interval to ALL occurrences of A in the formula, e.g. for A/A the value of the function will be 1, no matter how many random values you generate. Do not work with intervals that span zero if you want to get correct result for that formula. Then you take the min/max of all function values (all of them were 1), and voila, final result is 1 with ZERO TOLERANCE or zero width. Well, you could cancel numerator and denominator from the very beginning, MC and analytical methods allow it.

This is just my intuition: I think it is impossible, just like (A*B)*C != A*(B*C) if * represents cross product.

The problem about these algebraically equivalent ways of writing a formula is, that there is no inverse element (and no identity) in our interval multiplication, e.g.:

   (define x (make-interval 1 10))
   (mul-interval x (div-interval (make-interval 1 1) x))
   => (0.1 . 10.0)

The interval division is defined as if we had an inverse element. The algebraic transformations by Lem suppose that there was an inverse element in our interval multiplication.

 (div-interval (mul-interval (make-interval 1 1) x) x) 

https://stackoverflow.com/a/14131196/1449443 gives some good pointers to further study. I think it's difficult at my level of math knowledge to say that this problem is impossible to solve. At the same time, I don't want to go down the multi-variable diffeq rabbit whole far enough to solve it at the moment.

I think this problem depends on the functional relationship between the two variables. If the variables in the two intervals are independent of each other, then this problem will not occur. So is it possible to consider introducing the relationship between the two variables into the interval operator in some form?

Well guess my answer is no, this is not possible. I think the basic problem here is with identity interval and reverse operation. Suppose A and C are two intervals, then (A * C / C) equals A algebratically but not interval arithmetically. This is the same for (A + C - C). Let C be interval of (lc,uc), and suppose I have a new implementation of interval arithmetic. When I do subtraction in the case of (A + C - C), I have to subtract lower-bound by lc(not uc) and subtract upper-bound by uc(not lc). See the problem is our simple implementation doesn't remember things or record what has been added before, so we really dont know if we should subtract by uc or lc. So, eh not possible.

  (define (make-interval a b)
    (cons a b))
  
  (define (lower-bound i)
    (car i))
  
  (define (upper-bound i)
    (cdr i))
  
  (define (width i)
    (/ (- (upper-bound i) (lower-bound i)) 2))
  
  (define (center i)
    (/ (+ (lower-bound i) (upper-bound i)) 2))
  
  (define (make-center-percent c p)
    (make-interval (- c (* c p)) (+ c (* c p))))
  
  (define (percent i)
    (/ (width i) (center i)))
  
  (define (add-interval x y)
    (make-interval (+ (lower-bound x) (lower-bound y))
                   (+ (upper-bound x) (upper-bound y))))
  
  (define (max a b)
    (if (> a b)
        a
        b))
  
  (define (min a b)
    (if (< a b)
        a
        b))
  
  (define (mul-interval x y)
    (if (and (>= (upper-bound x) (lower-bound x)) (>= (upper-bound y) (lower-bound 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 (min p1 p2) (min p3 p4))
                         (max (max p1 p2) (max p3 p4))))
        (make-interval (min (* (lower-bound x) (lower-bound y))
                            (* (upper-bound x) (upper-bound y)))
                       (max (* (lower-bound x) (lower-bound y))
                            (* (upper-bound x) (upper-bound y))))))
         
  (define inverse-obj
    (lambda (i) (cons (/ 1 (lower-bound i)) (/ 1 (upper-bound i)))))        
  
  (define (div-interval x y)
    (if (<= (* (upper-bound y) (lower-bound y)) 0)
        (display "error")
        (mul-interval
         x
         (inverse-obj 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)))))
  
  (define r1 (make-center-percent  500 0.88))
  (define r2 (make-center-percent 3000 0.42))
  
  (par1 r1 r2)
  (par2 r1 r2)

  (define r1 (make-center-percent  500 0.88))
  (define r2 (make-center-percent  500 0.88))
  ; this will produce a zero width interval
  (div-interval r1 r2)

 (define (old-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 (min p1 p2) (min p3 p4)) 
                     (max (max p1 p2) (max p3 p4))))) 
  
 (define test_x (make-interval 2 1)) 
 (define test_y (make-interval 1 2)) 
 (old-mul-interval test_x test_y) 
 (mul-interval test_x test_y) 

Summary of history comments:

extrema problem is said in Tengs's, voom4000's comment.

dependency problem is said in Tengs's, voom4000's and Tree3's comments. It is also said in https://github.com/xxyzz/SICP/blob/master/2_Building_Abstractions_with_Data/2.1_Introduction_to_Data_Abstraction/README.md#exercise-216. It is implied in jz's, vi's and cat's comments.

reverse operation is said in pt's and cat's comments.