On Average Bit Complexity of Interval Arithmetic

In many practical situations, we know only the intervals which contain the actual (unknown) values of physical quantities. If we know the intervals [x] for a quantity x and [y] for another quantity y, then, for every arithmetic operation *, the set of possible values of x*y also forms an interval; the operations leading from [x] and [y] to this new interval are called interval arithmetic operations. For addition and subtraction, corresponding interval operations consist of two corresponding operations with real numbers, so there is no hope of making them faster. The best known algorithms for interval multiplication consists of 3 real-number multiplications and several comparisons. We describe a new algorithm for which the average time is equivalent to using only 2 multiplications of real numbers