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.

am stuck at this homework from past 2 days!!! Please help me!!! — overexchange, Apr 23 '15 at 10:27
I think there is only one case, not nine: def mul_interval(x, y): a, *_, b = sorted(u*v for u in (x.a, x.b) for v in (y.a, y.b)); return interval(a=a, b=b) — Stef, Feb 14 '24 at 11:41

score 1 · Accepted Answer · answered Apr 23 '15 at 11:36

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

answered Apr 23 '15 at 11:36

Hans Lundmark

53,395

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

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

Interval arithmetic - faster version

1 Answers1