Paul N. Hilfinger

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-582
June 1990

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-582.pdf

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^m a/ 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 754.

BibTeX citation:

@techreport{Hilfinger:CSD-90-582,
    Author = {Hilfinger, Paul N.},
    Title = {Implementing Ada Fixed-point Types having Arbitrary Scales},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1990},
    Month = {Jun},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/5527.html},
    Number = {UCB/CSD-90-582},
    Abstract = {Ada implementations have the option of supporting fixed-point arithmetic with arbitrary scale -- that is, in which the safe numbers are of the form <i>m</i>-sigma for a fixed, arbitrary rational sigma > 0, with <i>m</i> 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 <i>x</i> and <i>y</i> are the integer values representing the operands, these operations reduce to finding integer approximations of alpha<i>xy</i> or beta<i>x</i>/<i>y</i> 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^m<i>a</i>/<i>b</i>, where <i>a</i> and <i>b</i> 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 754.}
}

EndNote citation:

%0 Report
%A Hilfinger, Paul N.
%T Implementing Ada Fixed-point Types having Arbitrary Scales
%I EECS Department, University of California, Berkeley
%D 1990
%@ UCB/CSD-90-582
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/5527.html
%F Hilfinger:CSD-90-582