2
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ (-3, -1)? I have taken permutations of signs for given (1, 3) and (5, 7). I don't know what are you saying above? $\endgroup$ – overexchange Apr 23 '15 at 13:22
  • 1
    $\begingroup$ 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)$". $\endgroup$ – Hans Lundmark Apr 23 '15 at 13:56
  • $\begingroup$ You have made me understand, what an interval is? Thank you!!! $\endgroup$ – overexchange Apr 23 '15 at 14:14
  • $\begingroup$ 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.) $\endgroup$ – Hans Lundmark Apr 23 '15 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.