Exercise 2.9 of SICP
Exercise 2.9: The width of an interval is half of the difference between its upper and lower
bounds. The width is a measure of the uncertainty of the number specified by the interval. For
some arithmetic operations the width of the result of combining two intervals is a function
only of the widths of the argument intervals, whereas for others the width of the combination
is not a function of the widths of the argument intervals. Show that the width of the sum
(or difference) of two intervals is a function only of the widths of the intervals being added
(or subtracted). Give examples to show that this is not true for multiplication or division.
$$ (a-\epsilon_1,a+\epsilon_1) \pm (b-\epsilon_2,b+\epsilon_2) $$
$$ w_a=\frac{1}{2}(a+\epsilon_1-(a-\epsilon_1))=\epsilon_1 $$
$$ w_b=\frac{1}{2}(b+\epsilon_2-(b-\epsilon_2))=\epsilon_2 $$
Addition:
$$ (a-\epsilon_1,a+\epsilon_1)+(b-\epsilon_2,b+\epsilon_2) $$
$$ \left((a+b)-(\epsilon_1+\epsilon_1),(a+b)+(\epsilon_1+\epsilon_1))\right) $$
$$ w_{a+b} = \epsilon_1+\epsilon_2 = w_a + w_b $$
Subtraction:
$$ (a-\epsilon_1,a+\epsilon_1)-(b-\epsilon_2,b+\epsilon_2) $$
$$ \left((a-b)-(\epsilon_1+\epsilon_2),(a-b)+(\epsilon_1+\epsilon_2)\right) $$
$$ w_{a-b}=\epsilon_1+\epsilon_2= w_a+w_b $$
Multiplication:
$$ (a-\epsilon_1,a+\epsilon_1) \cdot (b-\epsilon_2,b+\epsilon_2) $$
- $$ (a+\epsilon_1)\cdot(b+\epsilon_2)=ab+a\epsilon_2+b\epsilon_1+\epsilon_1\epsilon_2 $$
- $$ (a+\epsilon_1)\cdot(b-\epsilon_2)=ab-a\epsilon_2+b\epsilon_1-\epsilon_1\epsilon_2 $$
- $$ (a-\epsilon_1)\cdot(b+\epsilon_2)=ab+a\epsilon_2-b\epsilon_1-\epsilon_1\epsilon_2 $$
- $$ (a-\epsilon_1)\cdot(b-\epsilon_2)=ab-a\epsilon_2-b\epsilon_1+\epsilon_1\epsilon_2 $$
If any of the four intervals expressions are used as interval endpoints their width formula will not give the tidy results of addition/subtraction.
Division:
$$ (a-\epsilon_1,a+\epsilon_1) \cdot (\frac{1}{b+\epsilon_2},\frac{1}{b-\epsilon_2}) $$
- $$ (a-\epsilon_1)\cdot\frac{1}{b+\epsilon_2}=\frac{a-\epsilon_1}{b+\epsilon_2} $$
- $$ (a+\epsilon_1)\cdot\frac{1}{b+\epsilon_2}=\frac{a+\epsilon_1}{b+\epsilon_2} $$
- $$ (a-\epsilon_1)\cdot\frac{1}{b-\epsilon_2}=\frac{a-\epsilon_1}{b-\epsilon_2} $$
- $$ (a+\epsilon_1)\cdot\frac{1}{b-\epsilon_2}=\frac{a+\epsilon_1}{b-\epsilon_2} $$
Examples:
$w_1$=0.68
$w_2$=0.235
$w_{total}$=0.915
> (print (add-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[10.585,12.415]
$w_{actual}$=0.915
$w_1$=0.68
$w_2$=0.235
$w_{total}$=0.915
> (print (sub-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[1.1850000000000005,3.0150000000000006]
$w_{actual}$=0.915 (ignoring the floating point number errors)
$w_1$=0.68
$w_2$=0.235
$w_{naive_total}$=0.15980
Of course this doesn’t make sense since accuracy cannot be magically gained by multiplying two interval together. More on this in the division example.
> (print (mul-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[1.1850000000000005,3.0150000000000006]
$w_{actual}$=4.794
$w_1$=0.68
$w_2$=0.235
$w_{naive_total}$=2.89361702127659574468
> (print (div-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[1.2401215805471126,1.6752519596864504]
$w_{actual}$=.2175651895696689
How is it that wactual is smaller than each $w_1$, $w_2$? wnaive_total is just plain wrong and should be discarded.
The answer is that $w_{actual}$ isn’t smaller. It’s actually larger. The percentage of error that $w_{actual}$ represents, for it’s interval, is actually greater than either $w_1$=10% and $w_2$=5%. $w_{actual}$ = 14.9%.
$$ 6.8 \pm 0.68 $$
$$ 0.68 = \frac{0.68}{6.8}=10% $$
$$ 4.7 \pm 0.235 $$
$$ 0.235 = \frac{0.235}{4.7}=5% $$
$$ 0.2175651895696689 = \frac{.2175651895696689}{\left(\frac{1}{2}\cdot(1.2401215805471126+1.6752519596864504)\right)}=14.9% $$
As expected the error is actually higher even though the aggregate number for $w_{actual}$ looks smaller.