×
Matula, David W.; McFearin, Lee D.

A \(p\times p\) bit fraction model of binary floating point division and extremal rounding cases. (English) Zbl 1064.68006

Theor. Comput. Sci. 291, No. 2, 159-182 (2003).
Summary: We introduce the ordered series \(F_{p\times p}\) of irreducible \(p\times p\) bit fractions as a model of \(p\)-bit precision binary floating point division. We employ and extend results from the number theoretic literature on Farey fractions and continued fractions to provide a foundation for generation and analysis of the series \(F_{p\times p}\). An algorithm for ordered on-the-fly enumeration of a consecutive subsequence of \(F_{p\times p}\) over a selected interval is introduced which requires only a couple of integer additions and/or subtractions per \(p\times p\) bit fraction enumerated. We characterize two extremal rounding boundary sets, \(RN_{p},\) respectively \(RD_{p},\) of irreducible \(p\times p\) bit fractions over the standard binade \([1,2)\) whose \(2^{p+O(1)}\) member fractions have rational values that are each comparably close to a boundary for rounding to a normalized \(p\)-bit floating point number by round-to-nearest, respectively, by a directed rounding. A transformation is shown allowing either set \(RN_{p}, RD_{p}\), to be simply computed from the other. We determine properties of these extremal rounding boundary sets \(RN_{p}, RD_{p}\), and describe their use in the testing of floating point division implementations.

Cited in 1 Document

MSC:

68M07 Mathematical problems of computer architecture

Keywords:

Floating point; Division; Rounding; Extremal rounding cases; Farey series; Tree traversal; Binary numbers; Mediant fraction
Cite Review PDF
Full Text: DOI

References:

[1] R.C. Agarwal, F.G. Gustavson, M.S. Schmookler, Series approximation methods for divide and square root in the power3 processor, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 116-123.; R.C. Agarwal, F.G. Gustavson, M.S. Schmookler, Series approximation methods for divide and square root in the power3 processor, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 116-123.
[2] M. Cornea-Hasegan, Proving the IEEE correctness of iterative floating-point square root, divide, and remainder algorithms, Intel Technol. J. (Intel Corporation) (April 1998).; M. Cornea-Hasegan, Proving the IEEE correctness of iterative floating-point square root, divide, and remainder algorithms, Intel Technol. J. (Intel Corporation) (April 1998).
[3] M. Cornea-Hasegan, R. Golliver, P. Markstein, Correctness proofs outline for Newton-Raphson based floating-point divide and square root algorithms, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 96-105.; M. Cornea-Hasegan, R. Golliver, P. Markstein, Correctness proofs outline for Newton-Raphson based floating-point divide and square root algorithms, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 96-105.
[4] R.W. Gosper, Item 101 in Hakmem, AIM239, MIT, Cambridge, MA, February 1972, pp. 37-44.; R.W. Gosper, Item 101 in Hakmem, AIM239, MIT, Cambridge, MA, February 1972, pp. 37-44.
[5] Hardy, C. H.; Wright, E. M., An Introduction to the Theory of Numbers (1979), Oxford University Press: Oxford University Press London, England · Zbl 0423.10001
[6] IEEE Standard 754 for Binary Floating Point Arithmetic, ANSI/IEEE Standard No. 754, American National Standards Institute, Washington, DC, 1988.; IEEE Standard 754 for Binary Floating Point Arithmetic, ANSI/IEEE Standard No. 754, American National Standards Institute, Washington, DC, 1988.
[7] C. Iordache, D.W. Matula, On infinitely precise rounding for division, square root, reciprocal, and square root reciprocal, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 233-240.; C. Iordache, D.W. Matula, On infinitely precise rounding for division, square root, reciprocal, and square root reciprocal, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 233-240.
[8] W. Kahan, Checking whether floating point division is correctly rounded, monograph, April 11, 1987 (see http://http.cs.berkeley.edu/ wkahan; W. Kahan, Checking whether floating point division is correctly rounded, monograph, April 11, 1987 (see http://http.cs.berkeley.edu/ wkahan
[9] A.Y. Khinchin, Continued Fractions, 1935 (translated from Russian by P. Wynn, P. Noordhoff Ltd., Grooningen, 1963).; A.Y. Khinchin, Continued Fractions, 1935 (translated from Russian by P. Wynn, P. Noordhoff Ltd., Grooningen, 1963). · JFM 63.0924.02
[10] Knuth, D. E., The Art of Computer Programming, Seminumerical Algorithms, vol. 2 (1981), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0477.65002
[11] Kornerup, P.; Matula, D. W., Finite precision rational arithmetican arithmetic unit, IEEE Trans. Comput., C-32, 4, 378-387 (1983) · Zbl 0515.65042
[12] P. Kornerup, D.W. Matula, Finite precision lexicographic continued fraction number systems, Proc. 7th IEEE Symp. on Computer Arithmetic, 1985, pp. 207-214.; P. Kornerup, D.W. Matula, Finite precision lexicographic continued fraction number systems, Proc. 7th IEEE Symp. on Computer Arithmetic, 1985, pp. 207-214.
[13] Kornerup, P.; Matula, D. W., An algorithm for redundant binary bit-piplined rational arithmetic, IEEE Trans. Comput., 39, 8, 1106-1115 (1990)
[14] V. Leferve, J. Muller, A. Tisserand, Towards correctly rounded transcendentals, Proc. 13th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1997, pp. 132-137.; V. Leferve, J. Muller, A. Tisserand, Towards correctly rounded transcendentals, Proc. 13th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1997, pp. 132-137.
[15] Matula, D. W.; Kornerup, P., Foundations of finite precision rational arithmetic, Computing, 2, Suppl., 88-111 (1980) · Zbl 0445.65027
[16] D.W. Matula, P. Kornerup, An order preserving finite binary encoding of the rationals, Proc. 6th IEEE Symp. on Computer Arithmetic, 1983, pp. 201-209.; D.W. Matula, P. Kornerup, An order preserving finite binary encoding of the rationals, Proc. 6th IEEE Symp. on Computer Arithmetic, 1983, pp. 201-209. · Zbl 0556.94012
[17] L.D. McFearin, D.W. Matula, Analysis of hard to round test cases for binary floating point division, Proc. 15th IEEE Symp. on Computer Arithmetic, 2001, pp. 119-127.; L.D. McFearin, D.W. Matula, Analysis of hard to round test cases for binary floating point division, Proc. 15th IEEE Symp. on Computer Arithmetic, 2001, pp. 119-127.
[18] L.D. McFearin, D.W. Matula, Selecting test suites for IEEE standard floating point division, Proc. of IEEE Internat. Conf. on Computer Design, 2001, pp. 89-96.; L.D. McFearin, D.W. Matula, Selecting test suites for IEEE standard floating point division, Proc. of IEEE Internat. Conf. on Computer Design, 2001, pp. 89-96.
[19] S.F. Oberman, Floating point division and square root algorithms and implementation in the AMD K7 Microprocessor, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 106-115.; S.F. Oberman, Floating point division and square root algorithms and implementation in the AMD K7 Microprocessor, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 106-115.
[20] M. Parks, Number-theoretic test generation for directed rounding, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 241-248.; M. Parks, Number-theoretic test generation for directed rounding, Proc. 14th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1999, pp. 241-248.
[21] M. Schulte, E.E. Swartzlander, Exact rounding of certain elementary functions, Proc. 11th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1993, pp. 138-145.; M. Schulte, E.E. Swartzlander, Exact rounding of certain elementary functions, Proc. 11th IEEE Symp. on Computer Arithmetic, IEEE, New York, 1993, pp. 138-145.
[22] R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, Massachusetts, 1989.; R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, Massachusetts, 1989. · Zbl 0668.00003
[23] L.D. McFearin, A \(p\); L.D. McFearin, A \(p\)
[24] H.P. Sharangpani, M.L. Barton, Statistical Analysis of Floating Point Flaw in the Pentium Processor, Intel Corporation, 1994.; H.P. Sharangpani, M.L. Barton, Statistical Analysis of Floating Point Flaw in the Pentium Processor, Intel Corporation, 1994.
[25] D.W. Matula, Home Page, May 2002, see http://www.engr.smu.edu/ matula; D.W. Matula, Home Page, May 2002, see http://www.engr.smu.edu/ matula
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.