# Multiplying intervals in Two's complement

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?

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

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.
• 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. – Yuval Filmus May 29 '13 at 18:54