# sicp-ex-2.14-2.15-2.16

Tengs

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.

To say more detailedly:

Here since we have division, we assume R1 and R2 are both positive intervals (definition see Exercise 2.11). Then R1R2 take the minimum when both R1 and R2 take minimum. But 1/(R1+R2) takes minimum when both R1 and R2 take maximum. So the minimum of the 1st method result by multiplying these 2 minimums is wrong and can't be reached.

So here the book says

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

since this can make R1R2 and 1/(R1+R2) almost one number. Then these 2 methods have almost same center value. Otherwise, 1/(R1_max+R2_max) (R1_max means the upper bound of R1. Similar for others) and 1/(R1_min+R2_min) will differ a lot, which will cause R1R2/(R1+R2) result far from the right result. This is implied by https://web.archive.org/web/20141122102312/http://wqzhang.wordpress.com/2009/06/18/sicp-exercise-2-14/ and https://github.com/xxyzz/SICP/blob/2decd1017f898529340dd07e73224f2e750b65b8/2_Building_Abstractions_with_Data/2.1_Introduction_to_Data_Abstraction/Exercise_2_14.rkt#L67-L74.

jz

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

This link https://web.archive.org/web/20200128110657/http://wiki.drewhess.com/wiki/SICP_exercise_2.16 is very helpful. The 1st paragraph says the essence of the problem.

I skipped https://web.archive.org/web/20200201041202/http://cs.utep.edu/interval-comp/main.html since there are too many links. I tried searching "diff" (differential) referred to by the Stack Overflow link but there is none directly (maybe in some link but I won't spend too much time to search for it).

I skipped the 2nd since as the summary says it seems have no feasible implementation available.

The 3rd invalid link is not archived by wayback machine. But I found one valuable paper https://www.researchgate.net/publication/2766014_Constrained_Interval_Arithmetic which is based on complementary slackness https://www.cse.iitb.ac.in/~sundar/linear_optimization/lecture15.pdf which is beyond my maths knowledge.

voom4000

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.

I have edited this comment by changing it to multiple paragraphs and adding some emphasis without changing its contents. Hope it can help you understand it.

---

https://web.archive.org/web/20141122102312/http://wqzhang.wordpress.com/2009/06/18/sicp-exercise-2-14/ (it seems only 2-14 in 2-14~16 is archived by wayback machine.)

notes:

1. > but with a percentage tolerance twice as big as the percentage tolerance of A This can be proved. Let center be \$c\$ and width be \$w\$. Then A/A will be [(c-w)/(c+w),(c+w)/(c-w)]. So the new percentage will be \$2w/(c+w)\$. Since w is very small. The result can be reduced to \$2w/c\$.

2. A/B works fine since A and B are independent (I didn't dig into calculating the algebraic result).

---

TODO why min/max?

HannibalZ

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

I think it is inappropriate to use "cross product" as the analogue here.

pt

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.

IMHO it is better to use

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

to show R1/(R1R2) when reducing the 1st formula to the 2nd. Here the example means x/x doesn't equal to 1.

vi

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.

Tree3

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?

cat

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.

I tried to create inverse object for intervals. It looks like illegal move resembling trick with imaginary unit (I'm not really worldly-wise in math however) this solution works great for me:

ex.2.16

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

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

(define (par2 r1 r2)
(let ((one (make-interval 1 1)))
(div-interval
(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)
```

This is a great work which use the trick on the order of "lower" bound and "upper" bount. However, when it comes to division on two different numbers, which will indeed make a interval, this method will put the wrong interval:

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

This is as expected since r1/r2=1 when r1=r2.

Although you test of `inverse-obj` seems to work, the logic of `mul-interval` is wrong. I don't know why you define the else case of `if` as what it is. It will output differently for the following:

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

Maybe you imply the corresponding relation between these 2 intervals. More specifically, let A=[2,1] and B=[1,2]. Then take a and b from A and B. When a=2, b must be 1. But this is not always true to have such a corresponding relation, i.e. these 2 intervals are not always dependent.

LisScheSic