Interval arithmetic - faster version

Question

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.

Answer 1

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