Elamur Research⌕
☰
home / papers / 1991 / What every computer scientist should know about floating-point arithmetic

What every computer scientist should know about floating-point arithmetic

Paper · 1991 · David Goldberg

Summary

Goldberg addresses a gap in computer science training. Floating-point arithmetic appears in almost every language, processor and operating system, yet system builders rarely get a rigorous account of how it behaves. The paper is a self-contained tutorial with proofs that rely only on elementary calculus. It has three parts. The first explains how real numbers are approximated with a base β and a precision p, and how rounding error is measured in ulps and relative error. It also shows why guard digits matter when nearly equal values cancel. The second part examines the IEEE floating-point standard, including its exactly rounded basic operations, special quantities such as NaN and infinity, denormalized numbers, and exceptions, flags and trap handlers. The third part links these ideas to instruction set design, compiler optimization and exception handling. The author's main argument is that floating-point behaviour can be analysed precisely, and that hardware and language support make reliable numerical software much easier to build.

Key points

  • Decimal 0.1 has no finite binary representation, so with β = 2 it always falls between two representable numbers. Values beyond the exponent limits (e_max, e_min) lead to overflow and underflow, which the paper handles through infinity and denormalized numbers.
  • IBM considered guard digits important enough to add one to System/360 double precision in 1968. It also retrofitted machines already installed in the field.
  • The IEEE standard specifies the results of addition, subtraction, multiplication, division and square root. Compliant machines therefore give bit-identical results for these operations, which simplifies porting.
  • In naive summation, the error is bounded by roughly nε·Σ|x_j|. The Kahan summation formula (Theorem 8, with a proof drawn from Knuth 1981) achieves about a 2ε bound. IEEE double precision, where 1/ε ≈ 10^16, can do even better.
  • Double rounding in binary–decimal conversion can be avoided by using the inexact flag together with round-to-zero. The tutorial grew out of W. Kahan's 1988 course at Sun Microsystems, which was organized by David Hough.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🔬Palo Alto Research CenterPalo Alto · United States15 works · 9,914 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputational Theory and Mathematics · 321 worksEngineering · 188 worksElectrical and Electronic Engineering · 33 works

Cite

Cite as David Goldberg. 1991. What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys 23(1):5–48; reprinted by Sun/Oracle.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{goldberg1991what,
  title = {{What every computer scientist should know about floating-point arithmetic}},
  author = {David Goldberg},
  booktitle = {ACM Computing Surveys 23(1):5–48; reprinted by Sun/Oracle},
  year = {1991},
  doi = {10.1145/103162.103163},
  url = {https://doi.org/10.1145/103162.103163}
}

References

34 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aho, Alfred V., Sethi, R., and Ullman J. D. 1986. Compilers: Principles, Techniques and Tools, Addison-Wesley, Reading, MA. find
  2. ANSI 1978. American National Standard Programming Language FORTRAN, ANSI Standard X3.9-1978, American National Standards Institute, New York, NY. find
  3. Barnett, David 1987. A Portable Floating-Point Environment, unpublished manuscript. find
  4. Brown, W. S. 1981. A Simple but Realistic Model of Floating-Point Computation, ACM Trans. on Math. Software 7(4), pp. 445-480. find
  5. Cody, W. J et. al. 1984. A Proposed Radix- and Word-length-independent Standard for Floating-point Arithmetic, IEEE Micro 4(4), pp. 86-100. find
  6. Cody, W. J. 1988. Floating-Point Standards — Theory and Practice, in “Reliability in Computing: the role of interval methods in scientific computing”, ed. by Ramon E. Moore, pp. 99-107, Academic Press, Boston, MA. find
  7. Coonen, Jerome 1984. Contributions to a Proposed Standard for Binary Floating-Point Arithmetic, PhD Thesis, Univ. of California, Berkeley. find
  8. Dekker, T. J. 1971. A Floating-Point Technique for Extending the Available Precision, Numer. Math. 18(3), pp. 224-242. find
  9. Demmel, James 1984. Underflow and the Reliability of Numerical Software, SIAM J. Sci. Stat. Comput. 5(4), pp. 887-919. find
  10. Farnum, Charles 1988. Compiler Support for Floating-point Computation, Software-Practice and Experience, 18(7), pp. 701-709. find
  11. Forsythe, G. E. and Moler, C. B. 1967. Computer Solution of Linear Algebraic Systems, Prentice-Hall, Englewood Cliffs, NJ. find
  12. Goldberg, I. Bennett 1967. 27 Bits Are Not Enough for 8-Digit Accuracy, Comm. of the ACM. 10(2), pp 105-106. find
  13. Goldberg, David 1990. Computer Arithmetic, in “Computer Architecture: A Quantitative Approach”, by David Patterson and John L. Hennessy, Appendix A, Morgan Kaufmann, Los Altos, CA. find
  14. Golub, Gene H. and Van Loan, Charles F. 1989. Matrix Computations, 2nd edition,The Johns Hopkins University Press, Baltimore Maryland. find
  15. Graham, Ronald L. , Knuth, Donald E. and Patashnik, Oren. 1989. Concrete Mathematics, Addison-Wesley, Reading, MA, p.162. find
  16. Hewlett Packard 1982. HP-15C Advanced Functions Handbook. find
  17. IEEE 1987. IEEE Standard 754-1985 for Binary Floating-point Arithmetic, IEEE, (1985). Reprinted in SIGPLAN 22(2) pp. 9-25. find
  18. Kahan, W. 1972. A Survey Of Error Analysis, in Information Processing 71, Vol 2, pp. 1214 - 1239 (Ljubljana, Yugoslavia), North Holland, Amsterdam. find
  19. Kahan, W. 1986. Calculating Area and Angle of a Needle-like Triangle, unpublished manuscript. find
  20. Kahan, W. 1987. Branch Cuts for Complex Elementary Functions, in “The State of the Art in Numerical Analysis”, ed. by M.J.D. Powell and A. Iserles (Univ of Birmingham, England), Chapter 7, Oxford University Press, New York. find
  21. Kahan, W. 1988. Unpublished lectures given at Sun Microsystems, Mountain View, CA. find
  22. Kahan, W. and Coonen, Jerome T. 1982. The Near Orthogonality of Syntax, Semantics, and Diagnostics in Numerical Programming Environments, in “The Relationship Between Numerical Computation And Programming Languages”, ed. by J. K. Reid, pp. 103-115, North-Holland, Amsterdam. find
  23. Kahan, W. and LeBlanc, E. 1985. Anomalies in the IBM Acrith Package, Proc. 7th IEEE Symposium on Computer Arithmetic (Urbana, Illinois), pp. 322-331. find
  24. Kernighan, Brian W. and Ritchie, Dennis M. 1978. The C Programming Language, Prentice-Hall, Englewood Cliffs, NJ. find
  25. Kirchner, R. and Kulisch, U. 1987. Arithmetic for Vector Processors, Proc. 8th IEEE Symposium on Computer Arithmetic (Como, Italy), pp. 256-269. find
  26. Knuth, Donald E., 1981. The Art of Computer Programming, Volume II, Second Edition, Addison-Wesley, Reading, MA. find
  27. Kulisch, U. W., and Miranker, W. L. 1986. The Arithmetic of the Digital Computer: A New Approach, SIAM Review 28(1), pp 1-36. find
  28. Matula, D. W. and Kornerup, P. 1985. Finite Precision Rational Arithmetic: Slash Number Systems, IEEE Trans. on Comput. C-34(1), pp 3-18. find
  29. Nelson, G. 1991. Systems Programming With Modula-3, Prentice-Hall, Englewood Cliffs, NJ. find
  30. Reiser, John F. and Knuth, Donald E. 1975. Evading the Drift in Floating-point Addition, Information Processing Letters 3(3), pp 84-87. find
  31. Sterbenz, Pat H. 1974. Floating-Point Computation, Prentice-Hall, Englewood Cliffs, NJ. find
  32. Swartzlander, Earl E. and Alexopoulos, Aristides G. 1975. The Sign/Logarithm Number System, IEEE Trans. Comput. C-24(12), pp. 1238-1242. find
  33. Walther, J. S., 1971. A unified algorithm for elementary functions, Proceedings of the AFIP Spring Joint Computer Conf. 38, pp. 379-385. find
  34. Theorem 14 and Theorem 8 This section contains two of the more technical proofs that were omitted from the text. Theorem 14 find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/goldberg-1991-what-every-computer-scientist-should/