The BKM algorithm is a shift-and-add algorithm for computing elementary functions, first published in 1994 by J.C. Bajard, S. Kla, and J.M. Muller. BKM is based on computing complex logarithms and exponentials using a method similar to the algorithm Henry Briggs used to compute logarithms. By using a precomputed table of logarithms of negative powers of two, the BKM algorithm computes elementary functions using only integer add, shift, and compare operations. In differential algebra, an elementary function is a function built from a finite number of exponentials, logarithms, constants, one variable, and roots of equations through composition and combinations using the four elementary operations (+ − × ÷). The trigonometric functions and their inverses are assumed to be included in the elementary functions by... 1994 (MCMXCIV) was a common year starting on Saturday of the Gregorian calendar, and was designated as the International Year of the Family and the International Year of the Sport and the Olympic Ideal by United Nations. ... Logarithms to various bases: is to base e, is to base 10, and is to base 1. ... The exponential function is one of the most important functions in mathematics. ... Henry Briggs (February 1556 - January 26, 1630) was an English mathematician notable for changing Napiers logarithms into common/Briggesian logarithms He was born at Warley Wood, near Halifax, in Yorkshire Enland. ...

BKM is similar to CORDIC, but uses a table of logarithms rather than a table of arctangents. On each iteration, a choice of coefficient is made from a set of nine complex numbers, 1, 0, −1, i, −i, 1+i, 1−i, −1+i, −1−i, rather than only −1 or +1 as used by CORDIC. BKM provides a simpler method of computing some elementary functions, and unlike CORDIC, BKM needs no result scaling factor. The convergence rate of BKM is approximately one bit per iteration, like CORDIC, but BKM requires more precomputed table elements for the same precision because the table stores logarithms of complex operands. CORDIC (digit-by-digit method, Volder`s algorithm) (for COordinate Rotation DIgital Computer) is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions. ...

As with other algorithms in the shift-and-add class, BKM is particularly well-suited to hardware implementation. The relative performance of software BKM implementation in comparison to other methods such as polynomial or rational aproximations will depend on the availability of fast multi-bit shifts (i.e, a barrel shifter) or hardware floating point arithmetic. In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ... In mathematics, a rational function in algebra is a function defined as a ratio of polynomials. ... A barrel shifter is a digital circuit that can shift a data word by any number of bits in a single cycle. ... A floating-point number is a digital representation for a number in a certain subset of the rational numbers, and is often used to approximate an arbitrary real number on a computer. ...

References

• J.C. Bajard, S. Kla, and J.M. Muller. BKM: A new hardware algorithm for complex elementary functions. IEEE Transactions on Computers, 43(8): 955-963, August 1994
• J.M. Muller, Elementary Functions: Algorithms and Implementation, 2nd Ed. Birkhauser 2006