hilfingr@tully.Berkeley.EDU (Paul Hilfinger) (07/05/90)
A Berkeley Tech Report will soon appear on the subject of supporting
fixed-point arithmetic with arbitrary scales ('SMALL values)---specifically,
values that are not simple powers of 2. It's a bit dense, but may be
of interest to implementors and the generally curious.
--------------------------------------------------------------------------
Paul N. Hilfinger, "Implementing Ada Fixed-point Types having
Arbitrary Scales." Berkeley Report No. UCB/CSD 90/582, June, 1990.
30 pages, $5.00.
Abstract (LaTeX source form):
Ada implementations have the option of supporting fixed-point
arithmetic with arbitrary scale---that is, in which the safe numbers
are of the form $m \sigma$ for a fixed, arbitrary rational $\sigma>0$,
with $m$ in some contiguous range of integers. The major difficulty
with providing such support is the implementation of the mixed-type
operations, multiplication and division. If $x$ and $y$ are the
integer values representing the operands, these operations reduce to
finding integer approximations of $\alpha xy$ or $\beta x/y$ with an
absolute error less than~1 for a fixed-point result type, an absolute
error less than or equal to~1/2 for an integer result type, or a
relative error of less than one safe interval for a floating-point
result type. The static constants $\alpha$ and $\beta$ may be
arbitrary positive rational numbers, depending on the scales of the
two operand types and on the result type. I present reasonably fast
ways to compute appropriate fixed-point results for all values of
$\alpha$ or $\beta$. For integer result types, I give algorithms for
$\alpha$ and $\beta$ that have the form $2^ma/b$, where $a$ and $b$
are positive, single-precision integer constants. Finally, I give
algorithms to produce floating-point results for a variety of
architectures, including the~VAX, the IBM~370, and those conforming to
IEEE Standard~754.
---------------------------------------------------------------------------
The address for ordering (for those of you that don't receive them
free) is
Publications Office
571 Evans Hall
University of California at Berkeley
Berkeley, CA 94720.
Paul N. Hilfinger
Electrical Engineering and Computer Sciences Dept.
University of California at Berkeley