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).
 

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 a successful dress design business and his father ran a factory. He was known within his family as Velvel, or “little wolf,” a name still favored by his friends over the Anglicized “William.” As a young man Kahan loved to fix mechanical and electronic devices, an inclination fostered by a summer job repairing surplus wartime equipment. He retained this love of tinkering throughout his life. He kept a pair of customized 1984 Peugeot 505s running for more than twenty years, and for a long time he eschewed laser printers in favor of a homebrew system optimized for printing equations on a dot matrix printer.

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 team at Cambridge University.

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 the Kahan summation algorithm to correct for rounding errors. 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. His best known work includes 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 take part in the prestigious 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. During a long and productive relationship with Intel he specified the arithmetic design for a number of its chips, most importantly the 8087 floating point coprocessor that was released in 1980. Thanks to the success of IBM’s Personal Computer, the 8087 and its direct descendants (the 80287, the 80387, on which Kahan directly worked, and the floating point unit built into the 80486) were used on millions of computers. When Intel redesigned its floating point implementation for the Pentium processor, launched in 1994, it introduced high profile bug that Kahan helped to locate and fix.

Kahan takes personal credit for just two aspects of the 8087: its “inexact flag” that programmers could test to see if a result could not be fully relied upon, and the provision of a NaN (Not a Number) code to report the results for which no numerical representation is possible (such as the square root of a negative number). “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 users1.

In 1977 Kahan became active in the fledgling IEEE effort to define a standard for computer arithmetic. Variations in floating point arithmetic implementations on different kinds of computers meant that even when programs were written in a standard language such as FORTRAN they might not work as efficiently or even give the same results. The sudden proliferation of microprocessors and workstation systems threatened to make matters worse.

Most people expected the IEEE committee to endorse the existing approach of some particular manufacturer, such as DEC or IBM. Instead, Kahan persuaded his colleagues to endorse an entirely new design modeled on his still-secret work for Intel. Their doubts about efficient implementation of the approach were eventually overcome. By the time the standard was officially adopted as IEEE 754 in 1985, it had already been widely implemented based on drafts published from 1979 onward. 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”.

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 as a just 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. Kahan remained active in the development of floating point standards, leading a successful effort from 2000 to 2008 to create a revised version of IEEE 754.

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 superficial1”.

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 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.

Author: Thomas Haigh

 

Notes:

1 From an oral interview with the author for SIAM – the full interview will be posted on line in the future.