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?

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

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.

  • $\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 '13 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$ – Yuval Filmus May 29 '13 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 '13 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$ – Yuval Filmus May 30 '13 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 '13 at 9:03

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.