William Kahan

Last updated
William Morton Kahan
William Kahan 2008.jpg
Kahan in 2008
Born (1933-06-05) June 5, 1933 (age 91)
Alma mater University of Toronto
Known for IEEE 754
Kahan summation algorithm
Awards Turing Award (1989)
IEEE Emanuel R. Piore Award [1] (2000)
National Academy of Engineering
ACM Fellow
Scientific career
Fields Mathematics
Computer Science
Institutions University of California, Berkeley
Thesis Gauss–Seidel Methods Of Solving Large Systems Of Linear Equations  (1958)
Doctoral advisor Byron Alexander Griffith
Doctoral students James Demmel
Ren-Cang Li

William "Velvel" Morton Kahan (born June 5, 1933) is a Canadian mathematician and computer scientist, who received the Turing Award in 1989 for "his fundamental contributions to numerical analysis ", [2] was named an ACM Fellow in 1994, [2] and inducted into the National Academy of Engineering in 2005. [2]

Contents

Biography

Born to a Canadian Jewish family, [2] he attended the University of Toronto, where he received his bachelor's degree in 1954, his master's degree in 1956, and his Ph.D. in 1958, all in the field of mathematics. Kahan is now emeritus professor of mathematics and of electrical engineering and computer sciences (EECS) at the University of California, Berkeley.

Kahan was the primary architect behind the IEEE 754-1985 standard for floating-point computation (and its radix-independent follow-on, IEEE 854). He has been called "The Father of Floating Point", since he was instrumental in creating the original IEEE 754 specification. [2] Kahan continued his contributions to the IEEE 754 revision that led to the current IEEE 754 standard.

In the 1980s he developed the program "paranoia", a benchmark that tests for a wide range of potential floating-point bugs. [3] He also developed the Kahan summation algorithm, an important algorithm for minimizing error introduced when adding a sequence of finite-precision floating-point numbers. He coined the term "Table-maker's dilemma" for the unknown cost of correctly rounding transcendental functions to some preassigned number of digits. [4]

The Davis–Kahan–Weinberger dilation theorem is one of the landmark results in the dilation theory of Hilbert space operators and has found applications in many different areas. [5]

He is an outspoken advocate of better education of the general computing population about floating-point issues and regularly denounces decisions in the design of computers and programming languages that he believes would impair good floating-point computations. [6] [7] [8]

When Hewlett-Packard (HP) introduced the original HP-35 pocket scientific calculator, its numerical accuracy in evaluating transcendental functions for some arguments was not optimal. HP worked extensively with Kahan to enhance the accuracy of the algorithms, which led to major improvements. This was documented at the time in the Hewlett-Packard Journal . [9] [10] He also contributed substantially to the design of the algorithms in the HP Voyager series and wrote part of their intermediate and advanced manuals.

See also

Related Research Articles

<span class="mw-page-title-main">Floating-point arithmetic</span> Computer approximation for real numbers

In computing, floating-point arithmetic (FP) is arithmetic that represents subsets of real numbers using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. Numbers of this form are called floating-point numbers. For example, 12.345 is a floating-point number in base ten with five digits of precision:

IEEE 754-1985 is a historic industry standard for representing floating-point numbers in computers, officially adopted in 1985 and superseded in 2008 by IEEE 754-2008, and then again in 2019 by minor revision IEEE 754-2019. During its 23 years, it was the most widely used format for floating-point computation. It was implemented in software, in the form of floating-point libraries, and in hardware, in the instructions of many CPUs and FPUs. The first integrated circuit to implement the draft of what was to become IEEE 754-1985 was the Intel 8087.

<span class="mw-page-title-main">PA-RISC</span> Instruction set architecture by Hewlett-Packard

Precision Architecture RISC (PA-RISC) or Hewlett Packard Precision Architecture, is a general purpose computer instruction set architecture (ISA) developed by Hewlett-Packard from the 1980s until the 2000s.

<span class="mw-page-title-main">Reverse Polish notation</span> Mathematics notation where operators follow operands

Reverse Polish notation (RPN), also known as reverse Łukasiewicz notation, Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands, in contrast to prefix or Polish notation (PN), in which operators precede their operands. The notation does not need any parentheses for as long as each operator has a fixed number of operands.

A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The development of the computer algebra systems in the second half of the 20th century is part of the discipline of "computer algebra" or "symbolic computation", which has spurred work in algorithms over mathematical objects such as polynomials.

In computing, especially digital signal processing, the multiply–accumulate (MAC) or multiply-add (MAD) operation is a common step that computes the product of two numbers and adds that product to an accumulator. The hardware unit that performs the operation is known as a multiplier–accumulator ; the operation itself is also often called a MAC or a MAD operation. The MAC operation modifies an accumulator a:

The IEEE Standard for Floating-Point Arithmetic is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in the diverse floating-point implementations that made them difficult to use reliably and portably. Many hardware floating-point units use the IEEE 754 standard.

<span class="mw-page-title-main">Scientific calculator</span> Calculator designed to calculate problems in science, engineering, and mathematics

A scientific calculator is an electronic calculator, either desktop or handheld, designed to perform calculations using basic and complex mathematical operations and functions. They have completely replaced slide rules as well as books of mathematical tables and are used in both educational and professional settings.

<span class="mw-page-title-main">HP-35</span> First pocket scientific calculator

The HP-35 was Hewlett-Packard's first pocket calculator and the world's first scientific pocket calculator: a calculator with trigonometric and exponential functions. It was introduced in 1972.

<span class="mw-page-title-main">C99</span> C programming language standard, 1999 revision

C99 is an informal name for ISO/IEC 9899:1999, a past version of the C programming language standard. It extends the previous version (C90) with new features for the language and the standard library, and helps implementations make better use of available computer hardware, such as IEEE 754-1985 floating-point arithmetic, and compiler technology. The C11 version of the C programming language standard, published in 2011, updates C99.

<span class="mw-page-title-main">HP-42S</span> Scientific calculator by Hewlett-Packard

The HP-42S RPN Scientific is a programmable RPN Scientific hand held calculator introduced by Hewlett-Packard in 1988. It has advanced functions suitable for applications in mathematics, linear algebra, statistical analysis, computer science and others.

<span class="mw-page-title-main">CORDIC</span> Algorithm for computing trigonometric, hyperbolic, logarithmic and exponential functions

CORDIC, Volder's algorithm, Digit-by-digit method, Circular CORDIC, Linear CORDIC, Hyperbolic CORDIC, and Generalized Hyperbolic CORDIC, is a simple and efficient algorithm to calculate trigonometric functions, hyperbolic functions, square roots, multiplications, divisions, and exponentials and logarithms with arbitrary base, typically converging with one digit per iteration. CORDIC is therefore also an example of digit-by-digit algorithms. CORDIC and closely related methods known as pseudo-multiplication and pseudo-division or factor combining are commonly used when no hardware multiplier is available, as the only operations they require are additions, subtractions, bitshift and lookup tables. As such, they all belong to the class of shift-and-add algorithms. In computer science, CORDIC is often used to implement floating-point arithmetic when the target platform lacks hardware multiply for cost or space reasons.

<span class="mw-page-title-main">HP-12C</span> Financial calculator made by Hewlett-Packard

The HP-12C is a financial calculator made by Hewlett-Packard (HP) and its successor HP Inc. as part of the HP Voyager series, introduced in 1981. It is HP's longest and best-selling product and is considered the de facto standard among financial professionals. There have been multiple revisions over the years, with newer revisions moving to an ARM processor running a software emulator of the original Nut processor. Critics claim that its 1980s technology is antiquated, but proponents point out that it is still the de facto and de jure in high finance.

<span class="mw-page-title-main">HP calculators</span> Calculator product line by Hewlett-Packard

HP calculators are various calculators manufactured by the Hewlett-Packard company over the years.

<span class="mw-page-title-main">Hewlett-Packard Voyager series</span> Programmable calculator, 1982–1984

The Hewlett-Packard Voyager series of calculators were introduced by Hewlett-Packard in 1981. All members of this series are programmable, use Reverse Polish Notation, and feature continuous memory. Nearly identical in appearance, each model provided different capabilities and was aimed at different user markets.

Extended precision refers to floating-point number formats that provide greater precision than the basic floating-point formats. Extended precision formats support a basic format by minimizing roundoff and overflow errors in intermediate values of expressions on the base format. In contrast to extended precision, arbitrary-precision arithmetic refers to implementations of much larger numeric types using special software.

In computing HP Roman is a family of character sets consisting of HP Roman Extension, HP Roman-8, HP Roman-9 and several variants. Originally introduced by Hewlett-Packard around 1978, revisions and adaptations were published several times up to 1999. The 1985 revisions were later standardized as IBM codepages 1050 and 1051. Supporting many European languages, the character sets were used by various HP workstations, terminals, calculators as well as many printers, also from third-parties.

<span class="mw-page-title-main">France Rode</span> Slovenian engineer and inventor

France Rode was a Slovenian engineer and inventor best known for his work on the HP-35 pocket calculator. He was one of the four lead engineers at Hewlett-Packard assigned to this project.

<span class="mw-page-title-main">HP-21</span> Scientific calculator by Hewlett-Packard

The HP-21 was a scientific calculator produced by Hewlett-Packard between 1975 and 1978. It was designed as a replacement for the HP-35, and was one of a set of three calculators, the others being the HP-22 and HP-25, which were similarly built but aimed at different markets.

Floating-point error mitigation is the minimization of errors caused by the fact that real numbers cannot, in general, be accurately represented in a fixed space. By definition, floating-point error cannot be eliminated, and, at best, can only be managed.

References

  1. "IEEE Emanuel R. Piore Award Recipients" (PDF). IEEE. Archived from the original (PDF) on November 24, 2010. Retrieved March 20, 2021.
  2. 1 2 3 4 5 Haigh, Thomas (1989). "William ("Velvel") Morton Kahan". A. M. Turing Award. Retrieved 2017-05-27.
  3. Karpinski, Richard (1985), "Paranoia: A floating-point benchmark", Byte Magazine, 10 (2): 223–235
  4. Kahan, William. "A Logarithm Too Clever by Half" . Retrieved 2008-11-14.
  5. Davis, Chandler; Kahan, W. M.; Weinberger, H. F. (1982). "Norm-Preserving Dilations and Their Applications to Optimal Error Bounds". SIAM Journal on Numerical Analysis. 19 (3): 445–469. Bibcode:1982SJNA...19..445D. doi:10.1137/0719029. hdl: 10338.dmlcz/128534 .
  6. Kahan, William (1 March 1998). "How Java's Floating-Point Hurts Everyone Everywhere" (PDF). Retrieved 1 March 2021.
  7. Haigh, Thomas (March 2016). "An interview with William M. Kahan" (PDF). Retrieved 1 March 2021.
  8. Kahan, William (31 July 2004). "Matlab's Loss is Nobody's Gain" (PDF). Retrieved 1 March 2021.
  9. Kahan, William M. (December 1979). "Personal Calculator Has Key to Solve Any Equation f(x) = 0" (PDF). Hewlett-Packard Journal. 30 (12): 20–26. Retrieved 2023-06-16.
  10. Kahan, William M. (August 1980). "Handheld Calculator Evaluates Integrals" (PDF). Hewlett-Packard Journal. 31 (8): 23–32. Retrieved 2023-06-16.