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?