What every computer scientist should know about floating-point arithmetic

ABSTRACT

Floating-point arithmetic is considered as esoteric subject by many people. This is rather surprising, because floating-point is ubiquitous in computer systems: Almost every language has a floating-point datatype; computers from PCs to supercomputers have floating-point accelerators; most compilers will be called upon to compile floating-point algorithms from time to time; and virtually every operating system must respond to floating-point exceptions such as overflow. This paper presents a tutorial on the aspects of floating-point that have a direct impact on designers of computer systems. It begins with background on floating-point representation and rounding error, continues with a discussion of the IEEE floating point standard, and concludes with examples of how computer system builders can better support floating point.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: ANSI 1978. American National Standard Programming Language FORTRAN, ANSI Standard X3.9-1978. American National Standards Institute, New York.
• 3: BARNETT, D. 1987. A portable floating-point environment. Unpublished manuscript.
• 4: W. S. Brown, A Simple but Realistic Model of Floating-Point Computation, ACM Transactions on Mathematical Software (TOMS), v.7 n.4, p.445-480, Dec. 1981 [doi>10.1145/355972.355975]
• 5: CARDELLI, L., DONAHUE, J., GLASSMAN, L., JORDAN, M., KASLOW, B., AND NELSON, G. 1989. Modula-3 Report (revised). Digital Systems Research Center Report *~52, Palo Alto, Calif.
• 6: CODY, W. J. et al. 1984. A proposed radix- and word-length-independent standard for floatingpoint arithmetic. IEEE Micro 4, 4, 86-100.
• 7: W. J. Cody, Floating-point standards—theory and practice, Reliability in computing: the role of interval methods in scientific computing, Academic Press Professional, Inc., San Diego, CA, 1988
• 8: Jerome Toby Coonen, Contributions to a proposed standard for binary floating-point arithmetic (computer arithmetic), 1984
• 9: DEKKER, T. J. 1971. A floating-point technique for extending the available precision. Numer. Math. 18, 3, 224-242.
• 10: DEMMEL, J. 1984. Underflow and the reliability of numerical software. SIAM J. Sci. Stat. Cornput. 5, 4, 887-919.
• 11: Charles Farnum, Compiler support for floating-point computation, Software—Practice & Experience, v.18 n.7, p.701-709, July 1988 [doi>10.1002/spe.4380180709]
• 12: FORSYTHE, G. E., AND MOLER, C. B. 1967. Computer Solutmn of Linear Algebraic Systems. Prentice-Hall, Englewood Cliffs, N.J.
• 13: I. Bennett Goldberg, 27 bits are not enough for 8-digit accuracy, Communications of the ACM, v.10 n.2, p.105-106, Feb. 1967 [doi>10.1145/363067.363112]
• 14: GOLDBERC, D. 1990. Computer arithmetic. In Computer Architecture: A Quantitative Approach, David Patterson and John L. Hennessy, Eds. Morgan Kaufmann, Los Altos, Calif., Appendix A.
• 15: GOLUB, G. H., AND VAN LOAN, C. F. 1989. Matrix Computations. The Johns Hopkins University Press, Baltimore, MD.
• 16: HEWLETT PACKARD 1982. HP-15C Advanced Functions Handbook.
• 17: IEEE 1987. IEEE Standard 754-1985 for Binary Floating-Point Arithmetic, IEEE. Reprinted in SIGPLAN 22, 2, 9-25.
• 18: KASAN, W. 1972. A Survey of Error Analysis. In Information Processing 71, (Ljubljana, Yugoslavia), North Holland, Amsterdam, vol. 2, pp. 1214-1239.
• 19: KAHAN, W. 1986. Calculating Area and Angle of a Needle-like Triangle. Unpublished manuscript.
• 20: KAHAN, W. 1987. Branch cuts for complex elementary functions. In The State of the Art in Numerical Analyszs, M. J. D. Powell and A Iserles, Eds., Oxford University Press, N.Y., Chap. 7.
• 21: KAnAN, W. 1988. Unpublished lectures given at Sun Microsystems, Mountain View, Calif.
• 22: KAHAN, W., AND COONEN, J. T. 1982. The near orthogonality of syntax, semantics, and diagnostics in numerical programming environments. In The Relationship between Numerical Computation and Programmi,g Languages, J. K. Reid~ Ed. North-Holland~ Amsterdam~ pp 103 115.
• 23: KAI~AN, W., AND LEBLANC, E. 1985. Anomalies in the IBM acrith package. In Proceedings of the 7th IEEE Symposium on Computer Arithmetic (Urbana, Ill.), pp. 322-331.
• 24: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 25: KIRCHNER, R., AND KULISCH, U 1987 Arithmetic for vector processors. In Proceedings of the 8th IEEE Symposium on Computer Arithmetic (Como, Italy), pp. 256-269.
• 26: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 27: U W Kulisch , W L Miranker, The arithmetic of the digital computer: A new approach, SIAM Review, v.28 n.1, p.1-40, March 1986 [doi>10.1137/1028001]
• 28: MATULA, D. W., AND KORNERUP, P. 1985. Finite Precision Rational Arithmetic: Slash Number Systems. IEEE Trans. Comput. C-34, 1, 3-18.
• 29: REISER, J. F., A2CD KNUTH, D E. 1975. Evading the drift in floating-point addition. Inf. Process. Lett 3, 3, 84-87
• 30: STERBETZ, P. H. 1974. Floating-Point Computation. Prentice-Hall, Englewood Cliffs, N.J.
• 31: SWARTZLANDER, E. E , AND ALEXOPOULOS, G. 1975. The sign/logarithm number system. IEEE Trans. Comput. C-24, 12, 1238-1242
• 32: WALTHER, J. S. 1971. A unified algorithm for elementary functions. Proceedings of the AFIP Spr~ng Joint Computer Conference, pp. 379- 385.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

  K. Computing Milieux
  K.1 THE COMPUTER INDUSTRY
      Subjects: Standards

General Terms:
Algorithms, Design, Languages, Standardization

Keywords:
NaN, denormalized number, exception, floating-point, floating-point standard, gradual underflow, guard digit, overflow, relative error, rounding error, rounding mode, ulp, underflow