Multiplication of two intervals

Question

As per the below question picked from self training exercise:

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 ***"

I could analyse that, below is the pattern of results:

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

But above pattern does not show those nine cases.

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 interval arithmetic!!!

Answer 1

I'm not sure I fully understand, but there are 3 cases for an interval (a1,b1): a<b<=0, a<0<b, and 0<=a<b. So for two intervals (a1,b1) and (a2,b2), there are 3x3 = 9 cases. The most problematic as far as multiplication goes would be the case where a1<0<b1 and a2<0<b2. Then you need to know the min and max of a1*a2, b1*b2, a1*b2, and a2*b1 whereas the other cases are just scaling for which you need to know the two endpoints.

Answer 2

You can check those cases: Investigate whether or not the intervals overlap zero, or are always positive or negative you can break the problem down into cases where a maximum of two multiplies are needed.

Note the original question assumes that x[0] < x[1] and y[0] < y[1]

For example:

if (x[1] <= 0) {
   if (y[1] <= 0) {} // both negative
   if (y[0] >= 0) {} // one negative ane positive
   else {} // y is both negative and positive, x is only negative
}

if (x[0] >= 0) {
   if (y[1] <= 0) {} // one negative ane positive
   if (y[0] >= 0) {} // both positive
   else {} // y is both negative and positive, x is only positive
}
else {} //both overlap zero