A.M. TURING AWARD WINNERS BY...
BIRTH:

June 5, 1933, in Toronto, Ontario, Canada

EDUCATION:

B.Sc. 1954; M.Sc. 1956; Ph.D. 1958 (all in Mathematics, University of Toronto); Honorary Doctor of Mathematics, University of Waterloo, Canada, 1998; Honorary Doctor of Mathematics, Chalmers Inst., Goteborg, Sweden, 1993.

EXPERIENCE:

Postdoctoral fellow, Cambridge University Mathematical Laboratory (UK) 1958-1960; Assistant/Associate Professor of Mathematics, University of Toronto 1960-1968; Professor of Mathematics/Electrical Engineering & Computer Science (currently Emeritus Professor), University of California Berkeley 1968.

HONORS AND AWARDS:

First ACM George. E. Forsythe Memorial Award (1972); ACM Turing Award, 1989; ACM Fellow (1994); SIAM John von Neumann Lecture (1997); IEEE Emanuel R. Piore Award (2000); Foreign (Canadian) Associate, National Academy of Engineering (2005). Holds honorary doctorates from Goteborg, Sweden (1993) and from University of Waterloo, Canada (1998).
 

William (“Velvel”) Morton Kahan

United States – 1989
CITATION

For his fundamental contributions to numerical analysis. One of the foremost experts on floating-point computations. Kahan has dedicated himself to "making the world safe for numerical computations"!

William Kahan was born in Canada in 1933 and grew up around Toronto in a family of Jewish immigrants. His mother created dress designs for a successful factory run by his father. His family called him "Velvel", or "little wolf," a nickname still favored by his friends over the Anglicized "William." As a young man Kahan loved to fix mechanical and electronic devices, an inclination that gained him a summer job repairing electronic equipment used by Canadian Armed Forces for a while after WW-II. He has retained this love of tinkering throughout his life.He has retained this love of tinkering throughout his life. He kept a pair of customized 1984 Peugeot 505s running for more than thirty years, and long eschewed laser printers in favor of a dot matrix printer he had modified to rapidly print mathematical texts.

Kahan learned to program during the summer of 1953 as an undergraduate majoring in mathematics at the University of Toronto. The university was a center of early computer development and use, and owned FERUT, one of the world’s first commercially manufactured computers –the second Manchester Ferranti Mark I ever built. Remaining at Toronto as a graduate student, he focused his studies on numerical analysis and explored the new possibilities in applied mathematics that were opened up by the use of computers. He made extended visits to two other computing centers: he spent the summer of 1957 working on the ILLIAC I at the University of Illinois, and after completing his Ph.D. in 1958 spent two years with the EDSAC-2 at Cambridge University's Mathematical Laboratory.

He returned to Toronto in 1960 as a faculty member, where his research focused on the error-analysis of numerical computations. For Kahan this involved not just determination of the accuracy of calculated results, but also the design of new software and architectural features to improve accuracy while maintaining high performance. He created an integrated system of mathematical routines, compiler tweaks and operating system modifications for the university’s IBM 7094 computer to help programmers create accurate, high performance floating point code. Kahan played a leading role in the numerical analysis subgroup of the IBM computer user group SHARE, and spearheaded its successful campaign in 1966-1967 to force IBM to fix design flaws in the arithmetic of its new System /360 computers.

Kahan left Toronto in 1968 for the University of California, Berkeley, to bolster its newly created department of computer science. (Another Turing Award winner, Richard M. Karp, joined the same year as Kahan). Kahan credits the move to a combination of the attractions of Northern California for his children, who had been struck by its beauty during his recent sabbatical at Stanford University, and his dwindling faith in the future of high performance computing in Canada following the collapse of the country’s high technology defense sector.

Numerical analysis is at the intersection of computing and applied mathematics. Within that community Kahan is recognized as a researcher and theorist of exceptional talent. He contributed to several widely used algorithms, including the Golub-Kahan variant of the QR algorithm for singular value decomposition (used for matrix calculations fundamental to many kinds of computation) and a Compensated Summation algorithm to offset the worst rounding errors in trajectory computations.

Throughout his tenure at Berkeley, Kahan’s work involved the creation of practical tools as well as papers, algorithms and theorems. Together with his students he produced the widely used fdlibm mathematics library distributed with BSD Unix and used to implement mathematical computations for machines supporting the new IEEE 754 floating-point standard. Another widely used work was paranoia, a program that tests floating point arithmetic implementations for errors. He was also a committed, if demanding, teacher and invested considerable time tutoring undergraduates to solve problems of the kind encountered in the William Lowell Putnam Mathematics Competition.

At Berkeley, Kahan began to consult for computer manufacturers. From 1974 to 1984 he assisted Hewlett Packard with the mathematical functioning of its calculators, improving the accuracy and performance of many models, including the classic HP34C and HP12C, and adding widely used functions such as integrate and solve to package complex mathematical operations in a convenient and easy to use form. The continuing popularity of the HP12C financial calculator is testified to by its 30th anniversary edition, released in 2011.

During a long and productive relationship with Intel he specified the design for its floating-point arithmetic on several chips starting with the 8087, released in 1980, and then the 80387 and 486DX. Thanks to the success of IBM's Personal Computer and its direct descendants, those chips were used on millions of computers. When Intel redesigned its floating point implementation for the Pentium processor, launched in 1994, it introduced a high profile "Divide bug"; subsequently Kahan supplied a test program to prevent that from happening again.

In 1977 Kahan became active in the fledgling IEEE effort initiated by Robert Stewart to define a standard for computer arithmetic. Variations in floating-point arithmetics implemented on different kinds of computers often caused programs written in a standard language such as FORTRAN to give very different results when recompiled and run on another computer. The sudden proliferation of microprocessors and workstation systems threatened to worsen diversity and render uneconomical the development, testing and wide distribution of engineering and even some business software.

Most people expected the IEEE committee to endorse the existing approach of some particular manufacturer, such as DEC or IBM. Instead, Kahan persuaded the committee to endorse an entirely new design modeled on his then-secret work for Intel. The committee's doubts about efficient implementation were eventually overcome in what Kahan termed "late-night educational sessions." By the time the standard was officially adopted as IEEE 754 in 1985, it had already been implemented widely based on drafts published from 1979 onward with the help of his then graduate student Jerome Coonen. Kahan won the ACM’s Turing Award in 1989 for his work in creating that IEEE 754 standard, and he has often been called “The Father of Floating Point”.

Kahan takes personal credit for just two aspects of the 8087 and the IEEE standard that evolved from it: its “inexact flag” that programmers could test to see if a result had been approximated, and the provision of a NaN (Not a Number) code to report the creation of a result for which no numerical representation is possible (such as the quotient 0/0). These novelties, if supported by the programming language, let a programmer suspend judgment about speculatively executed operations because any serious anomalies could be detected by comparatively few tests conducted when the code was run. “Everything else” in the design, he told me, “was deduced” based on technical necessity and his decades of experience with existing computer arithmetic units and the needs of technical computation users.1

Adoption of the standard did a great deal to improve the robustness of floating point arithmetic and improve consistency of results across different computing platforms. Kahan himself regrets that IEEE 754 was generally seen only as a hardware standard, rather than as a specification for a computing environment in which hardware, compilers and application programs would interact. Some hardware features were neglected by compiler writers and language designers, which deprived programmers of their benefits and made it less likely that hardware producers would implement them effectively.

In recent decades Kahan has continued to articulately and bluntly warn of the shortcomings in the floating point implementations of environments as popular as Java and Matlab. The title of one paper, “How Java’s Floating-Point Hurts Everyone Everywhere”, gives a good idea of his willingness to play the part of curmudgeon in pointing out the deficiencies of fashionable ideas, products or technologies.

After retirement Kahan became Professor Emeritus at UC Berkeley. His career has been marked by faith in rigorous analysis and in the power of superior designs to win over skeptics. Kahan would rather be right than popular, and even as a young man he showed little deference when he thought someone was mistaken. When visiting Cambridge as a postdoctoral fellow he challenged the competence of Maurice Wilkes, the leading figure in British computing, to lecture on Numerical Analysis. Kahan’s version of the story ends with him informing Wilkes that “there is a difference between elementary and superficial”.1 He mentioned to me that Wilkes would tell the same story to make a different point.

In March 2016 he summarized his part in the later revision of the standard by proposing the following text: "Starting in 2000, Kahan participated initially in an obligatory revision of IEEE 754 subjected to an official demand that the revision cover decimal arithmetic as well as binary. As the committee grew, so did centrifugal demands for the inclusion of options that have compounded complexity. He regrets that the result released in 2008 has become so long and unreadable that it discourages the wide adoption in hardware of decimal floating-point, which is more humane than binary albeit less liked by mathematical error-analysts like him."

Unsurprisingly, Kahan finds little inherent reward in the politics and bureaucracy of committee work, so his commitment to the IEEE standards project over many years surprised some colleagues. It reflected his determination to apply the force of his intellect to end wasted effort and unnecessary frustration. Kahan’s success shows that commitment to uncompromising technical rigor and academic excellence, coupled with more than a little luck, can transform real world computer hardware and software. Sometimes an idealistic refusal to accept the deficiencies of established ways of doing things really does pay off.

Kahan is married to Sheila K. Strauss. They have two sons and four granddaughters.

Author: Thomas Haigh

Notes:

1 William Kahan, Oral History Interview With Thomas Haigh, 5-8 August 2005. Available online from SIAM.