Skip to content

William Kahan and IEEE 754

Abstract

Every number with a decimal point that a computer has handled since the mid-1980s follows rules written largely by one man. William Kahan (born 1933), a numerical analyst at Berkeley, was hired by Intel in 1976 to design the arithmetic of the 8087 coprocessor, turned that design into the draft of IEEE Standard 754, and spent the next eight years arguing DEC and the rest of the industry into it. He also fixed Hewlett-Packard’s calculators, invented compensated summation in 1965, and received the 1989 Turing Award. He took no money for the standard, so that nobody could say he had worked for one company against the others.

William Kahan 2008
William Kahan in 2008. Image: George Bergman, CC BY-SA 4.0, via Wikimedia Commons.

Toronto and the Anomalies

William Morton Kahan was born in Toronto on 5 June 1933 and took all three of his degrees in mathematics at the University of Toronto: a BS in 1954, an MS in 1956 and a PhD in 1958. In 1968 he moved to Berkeley to help build its newly created computer science department, and he has been there since.

His subject was error: what happens to a calculation when every intermediate result is rounded to a fixed number of bits. In January 1965 he published a one-page note in Communications of the ACM, “Further Remarks on Reducing Truncation Errors,” describing what is now called Kahan summation. When adding a long list of floating-point numbers, keep a second variable that records the low-order bits lost at each step and feed them back in; the worst-case error stops growing with the length of the list. It is four lines of code and is in every serious numerical library.

Through the 1960s and 1970s Kahan catalogued the arithmetic of commercial machines and showed how their quirks (numbers that were not equal to themselves, subtractions that lost every significant digit, underflows that silently became zero) drove up the cost of writing reliable software. He coined the “table-maker’s dilemma,” the fact that correctly rounding a transcendental function can require an unbounded amount of extra precision. He also acquired a sideline in calculators. Hewlett-Packard consulted him on the accuracy of the HP-35 and its successors, and his algorithms went into the Voyager series of the 1980s (The Pocket Calculator).

Intel, 1976

Intel 8087 die
The die of an Intel 8087, the coprocessor for which Kahan designed the arithmetic. Image: Pauli Rautakorpi, CC BY 3.0, via Wikimedia Commons.

In 1976 Intel decided to build a floating-point coprocessor for its 8086. The project manager, John Palmer, had heard Kahan lecture at Stanford a decade earlier and hired him as a consultant. Kahan’s first suggestion was to copy the arithmetic of the DEC VAX, the most respectable of the day. Palmer refused: Intel was aiming at a market larger than anyone had contemplated, and he wanted the best arithmetic, not the most familiar. The design they produced for the 8087 had two features that would be argued over for years: an 80-bit extended format for intermediate results, so that a calculation could carry more precision than its inputs and outputs, and gradual underflow, which fills the gap between the smallest normal number and zero with “subnormal” numbers instead of letting results fall off a cliff. Intel had a budget of about 40,000 transistors and wanted most of a maths library on the one chip.

Kahan’s own summary of the design goal was that it was for a mass market: “A lot of code involving a little floating-point will be written by many people who have never attended my numerical analysis classes.” The arithmetic had to be safe for people who did not know what they were doing.

The Standard

In November 1977 the IEEE’s p754 working group held its second meeting in San Francisco, and Kahan attended. He asked Palmer for permission to propose a standard based on the 8087 design; Intel agreed, on condition that he disclose the formats and basic operations but not the implementation or the transcendental functions. With his graduate student Jerome Coonen and a visiting professor, Harold Stone, he wrote what the committee called the K-C-S draft: an 11-bit exponent for double precision, signed infinities, NaN values for invalid results, and gradual underflow.

DEC put forward a competing proposal based on the VAX and fought gradual underflow for four years, on the grounds that it could not be built fast. The exponent biases of the two proposals differed by only two; the argument was about the subnormals. Two things settled it. George Taylor, a Berkeley student supervised by David Patterson (Hennessy and Patterson), built the K-C-S arithmetic into an accelerator board for a VAX and showed it ran at speed. Then, in Boston in 1981, DEC commissioned the error analyst G. W. “Pete” Stewart to assess gradual underflow, expecting him to condemn it. Stewart delivered his report verbally: on balance, gradual underflow was the right thing to do. DEC stopped fighting.

Intel had announced the 8087 in 1980, implementing the draft before it was approved, and by 1984 Intel, AMD, Apple, Motorola, IBM and others were all shipping conforming arithmetic. The standard sat in limbo for over a year at the IEEE Microprocessor Standards Committee and was ratified as IEEE 754-1985, by which point it was already, in Kahan’s phrase, “a de facto standard, the best kind.” Kahan refused any payment for the standards work so that he could not be accused of acting for Intel against anyone else, and he later singled out IBM’s Fred Ris, who supported the effort knowing that IBM’s own equipment would not conform. The ACM Turing Award followed in 1989, “for his fundamental contributions to numerical analysis,” with a citation that quoted his own description of his life’s work: making the world safe for numerical computations.

Paranoia and Java

Kahan did not stop policing. In the 1980s he wrote Paranoia, a test program that exercises a machine’s floating point and reports every deviation from correct rounding; it became the standard way to find out what a vendor had got wrong. When Sun’s Java arrived, he wrote, with his student Joseph Darcy, “How Java’s Floating-Point Hurts Everyone Everywhere” (1998), a sustained complaint that Java had adopted IEEE 754’s formats while forbidding the extended precision and the flags that made the standard safe, in the name of identical results on every machine. He was elected to the National Academy of Engineering in 2005 and became professor emeritus at Berkeley; the standard he wrote was revised in 2008 and 2019, and he contributed to the revisions.

Dead End: The Arithmetic Nobody Uses

The 8087’s 80-bit extended format was, by his own account, the part of the design Kahan cared about most, and it is the part the world quietly discarded. The idea was that intermediate results should carry more precision than the stored variables, so that ordinary code written by people who did not understand rounding would still get the right answer. It worked on the x87 stack, and it caused endless confusion, because the same program gave different results depending on which values the compiler happened to spill to memory. When the SSE2 instructions arrived in the early 2000s they gave the new registers only single and double precision, compilers moved to them, and extended precision became a legacy feature that most languages cannot even name. Kahan’s view, argued at length in his papers, is that this made floating-point arithmetic less safe for exactly the mass audience the standard was designed for. The rest of IEEE 754 won so completely that nobody remembers there was ever an alternative; the part he thought was the point lost.

📚 Sources