Optimizing the representation of intervals

A representation of intervals is proposed that, instead of both endpoints, uses the lower endpoint and the width of the interval. This proposed representation is more efficient since both endpoints have many corresponding bits that are equal. Consequently, the width of the interval can be represented with a smaller number of bits than an endpoint, resulting in a better utilization of the number of bits available. Considering the case in which the total number of bits is the same as for the traditional representation (say, two double-precision floating-point numbers) we determine the number of bits of the lower endpoint and of the width so that the rounding error is minimized. The use of this combination of bits would result in a variable representation, which is difficult to implement. Alternatively, it is possible to use a fixed partition that gives good results for a variety of applications. The proposed representation is evaluated for several computations. Using a total number of 128 bits to represent the interval we conclude that it produces intervals that are substantially narrower than those obtained with the traditional representation. Alternative implementations of the calculation of the width are proposed. The interval widths produced are shown to be very similar, so that the choice of the alternative can be made by considerations such as area and delay.

keywords: Interval arithmetic, Interval representation, Floating-point representation