# Interval arithmetic - faster version

As per the below question picked from self training exercise:

Q4: In passing, Ben also cryptically comments, "By testing the signs of the endpoints of the intervals, it is possible to break mul_interval into nine cases, only one of which requires more than two multiplications." Write a fast multiplication function using Ben's suggestion:

def mul_interval_fast(x, y):
"""Return the interval that contains the product of any value in x and any
value in y, using as few multiplications as possible.

>>> str_interval(mul_interval_fast(interval(-1, 2), interval(4, 8)))
'-8 to 16'
>>> str_interval(mul_interval_fast(interval(-2, -1), interval(4, 8)))
'-16 to -4'
>>> str_interval(mul_interval_fast(interval(-1, 3), interval(-4, 8)))
'-12 to 24'
>>> str_interval(mul_interval_fast(interval(-1, 2), interval(-8, 4)))
'-16 to 8'
"""
"*** YOUR CODE HERE ***"


With normal version of mul_interval the solution is:

def mul_interval(x, y):
"""Return the interval that contains the product of any value in x and any
value in y.

>>> str_interval(mul_interval(interval(-1, 2), interval(4, 8)))
'-8 to 16'
"""
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)
return interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4))


Based on the signs of endpoints of interval, to analyse those nine cases, I got below pattern of results by taking an example:

(1, 3)(5, 7)  ---> [min(5, 7, 15, 21), max(5, 7, 15, 21)]              --->   (5, 21)
(-1, -3)(-5, -7)  --->  [min(5, 7, 15, 21), max(5, 7, 15, 21)]         --->   (5, 21)
Result pattern is (lowerbound(itrvl1) * lowerbound(itrvl2), higherbound(itrvl1) * higherbound(itrvl2))
+++++++++++++++++++++++++
(1, 3)(5, -7)  --->  [min(5, -7, 15, -21), max(5, -7, 15, -21)]        --->   (-21, 15)
(-1, 3)(5, -7)  --->  [min(-5, 7, 15, -21), max(-5, 7, 15, -21)]       --->   (-21, 15)
(1, -3)(-5, 7)  --->  [min(-5, 7, 15, -21), max(-5, 7, 15, -21)]       --->   (-21, 15)
(-1, -3)(-5, 7)  --->  [min(5, -7, 15, -21), max(5, -7, 15, -21)]      --->   (-21, 15)
Result pattern is (higherbound(itrvl1) * higherbound(itrvl2), higherbound(itrvl1) * lowerbound(itrvl2))
+++++++++++++++++++++++++++++++++++
(1, 3)(-5, 7)  --->  [min(-5, 7, -15, 21), max(-5, 7, -15, 21)]        --->   (-15, 21)
(-1, 3)(-5, 7)  --->  [min(5, -7, -15, 21), max(5, -7, -15, 21)]       --->   (-15, 21)
(1, -3)(5, -7)  --->  [min(5, -7, -15, 21), max(5, -7, -15, 21)]       --->   (-15, 21)
(-1, -3)(5, -7)  --->  [min(-5, 7, -15, 21), max(-5, 7, -15, 21)]      --->   (-15, 21)
Result pattern is (higherbound(itrvl1) * lowerbound(itrvl2), higherbound(itrvl1) * higherbound(itrvl2))
++++++++++++++++++++++++++++++++
(1, 3)(-5, -7)   ---> [min(-5, -7, -15, -21), max(-5, -7, -15, -21)]   --->   (-21, -5)
(-1, -3)(5, 7)  --->  [min(-5, -7, -15, -21), max(-5, -7, -15, -21)]   --->   (-21, -5)
Result pattern is (higherbound(itrvl1) * higherbound(itrvl2), lowerbound(itrvl1) * lowerbound(itrvl2))
++++++++++++++++++++++++++++++
(-1, 3)(5, 7)   ---> [min(-5, -7, 15, 21), max(-5, -7, 15, 21)]        --->   (-7, 21)
(1, -3)(-5, -7)  --->  [min(-5, -7, 15, 21), max(-5, -7, 15, 21)]      --->   (-7, 21)
Result pattern is (lowerbound(itrvl1) * higherbound(itrvl2), higherbound(itrvl1) * higherbound(itrvl2))
+++++++++++++++++++++++++++++++
(-1, 3)(-5, -7) --->   [min(5, 7, -15, -21), max(5, 7, -15, -21)]      --->   (-21, 7)
(1, -3)(5, 7)  --->  [min(5, 7, -15, -21), max(5, 7, -15, -21)]        --->   (-21, 7)
Result pattern is (higherbound(itrvl1) * higherbound(itrvl2), lowerbound(itrvl1) * higherbound(itrvl2))


But I could not link the above pattern with nine cases that is mentioned in the question.

So, In specific, I would like to understand this point: By testing the signs of the endpoints of the intervals, it is possible to break mul_interval into nine cases,

Please help me on this approach to perform interval arithmetic.

• am stuck at this homework from past 2 days!!! Please help me!!! – overexchange Apr 23 '15 at 10:27

## 1 Answer

Your first case (or "result pattern" as you call it):

(1, 3)(5, 7)      --->  [min(5, 7, 15, 21), max(5, 7, 15, 21)]  --->  (5, 21)
(-1, -3)(-5, -7)  --->  [min(5, 7, 15, 21), max(5, 7, 15, 21)]  --->  (5, 21)
Result pattern is
(lowerbound(itrvl1) * lowerbound(itrvl2), higherbound(itrvl1) * higherbound(itrvl2))


Here the second line looks strange. The interval $(-1,-3)$ should rather be written as $(-3,-1)$, i.e., its lower bound is $-3$, not $-1$. So the result pattern for that line is actually

(higherbound(itrvl1) * higherbound(itrvl2), lowerbound(itrvl1) * lowerbound(itrvl2))


instead, so line 1 and line 2 belong to different cases.

This mistake is probably the explanation for why you're getting 6 cases instead of 9 (although I haven't checked all 16 lines myself).

• (-3, -1)? I have taken permutations of signs for given (1, 3) and (5, 7). I don't know what are you saying above? – overexchange Apr 23 '15 at 13:22
• An interval $(a,b)$ is a set of the form $a < x < b$, so you need to have $a<b$ to begin with. (When you say "lowerbound" and "higherbound" you really mean the left and right endpoints of the interval on the number line, right?) Since $-1$ lies to the right of $-3$ on the line, it's not meaningful to talk about the interval "$(-1,-3)$". – Hans Lundmark Apr 23 '15 at 13:56
• You have made me understand, what an interval is? Thank you!!! – overexchange Apr 23 '15 at 14:14
• You're welcome! (Note that in interval computations it might be more common to use closed intervals $[a,b]$ where the endpoints are included: $a \le x \le b$. And the two sign cases should perhaps be nonnegative/negative rather than positive/negative, so that you also take into account that one or both of the endpoints can be zero.) – Hans Lundmark Apr 23 '15 at 14:32