BKM algorithm

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

BKM is similar to CORDIC, but a radix 2 BKM uses at each step a choice from a set of eight complex numbers rather than only -1 or +1 as used by CORDIC. A major advantage over CORDIC is that no result scaling factor is needed.

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.

References

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