1
$\begingroup$

I want to perform some interval-operations, and for addition, subtraction, and logic-/shift-operators, that works very well.

The only problem I have is the multiplication.

An interval $[a, b]$ denotes all two's complement numbers $x$ with the property $a \leq x \leq b$.

An interval-operation means that if i have a binary operation $\circ$ and two intervals $[a, b]$ and $[c, d]$, then $[a, b] \circ [c, d] = [e, f]$ means that for for an arbitrary $x \in [a, b]$ and $y \in [c, d]$: $$x \circ y \in [e, f].$$

But additionally, I want to have the most precise or a very precise interval.

"The most precise" means that there are the values $w,x \in [a, b]$ and $y,z \in [c, d]$ for which holds that $w \circ y = e$ and $x \circ z = f$

An example of an interval-operation:

  • $A = [7,14]$
  • $B = [-6, 77]$
  • $A + B = [1, 91]$

It's correct, because there is no value outside of $[1, 91]$ that can be reached, when adding numbers out of $A$ and $B$.

Also it's precise, because $7+(-6) = 1$ and $14+77 = 91$

It seems impossible to find an efficient algorithm that handles all the overflows correctly and finds the precise (or at least a good) interval.

Is there a good algorithm?

$\endgroup$
12
  • $\begingroup$ What are interval operations? $\endgroup$ May 29, 2013 at 15:57
  • $\begingroup$ @YuvalFilmus I added a definition and an example, does that help? $\endgroup$
    – Odin
    May 29, 2013 at 16:36
  • $\begingroup$ $7+(-6)=1$, not $-1$ $\endgroup$ May 29, 2013 at 16:52
  • $\begingroup$ What is the relevance of the numbers being represented using two's complement? $\endgroup$ May 29, 2013 at 17:10
  • 1
    $\begingroup$ @Odin It is impossible since the correct product interval is out of range. $\endgroup$ Jun 6, 2013 at 7:13

1 Answer 1

1
$\begingroup$

If $0 \leq a,b,c,d$ then $[a,b] [c,d] = [ac,bd]$. The trouble begins when numbers can be negative. If $a,b<0$ then $[a,0][b,0]=[0,ab]$. If $a<0<b$ then $[a,0][0,b] = [ab,0]$. And so on. To consider intervals straddling $0$, partition them into their positive and negative parts.

Summarizing, I wouldn't say that it is "impossible" to find an algorithm for multiplying intervals, only that you have to consider numerous cases. Good luck.

$\endgroup$
5
  • $\begingroup$ You missed the problem. I know how to multiply intervals, but i don't know how to multiply twos complement intervals, especially the overflows. $\endgroup$
    – Odin
    May 29, 2013 at 17:37
  • $\begingroup$ So is your problem the following: "given $a,b$, compute $ab$"? If $ab$ overflows, then $ab$ is not a number in the range you consider, and the only thing you can do is resort to arbitrary-precision arithmetic. But then it's more of a programming problem, and there are libraries for that such as GMP. $\endgroup$ May 29, 2013 at 18:54
  • $\begingroup$ I want to know, how the algorithm for that works, therefore I cannot use libraries. Also it is not easy, since I know no efficient algorithm to find the maximum, when the factors are in the middle of the interval due to overflows $\endgroup$
    – Odin
    May 30, 2013 at 11:23
  • $\begingroup$ Odin, I'm not sure what you mean by "efficient algorithm". These algorithms are very efficient. The libraries are open source (at least GMP), if you're worried about that. There is no overflow if you work in arbitrary-precision arithmetic, since it is handled by adding a new "limb" to the number. $\endgroup$ May 30, 2013 at 14:31
  • $\begingroup$ The point is that I want to do it for Two's complement integers. It is absolutely useless for me to do it with arbitrary precision arithmetic because that is child's play. $\endgroup$
    – Odin
    Jun 5, 2013 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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