BKM algorithm

The BKM algorithm is a shift-and-add algorithm for computing elementary functions, first published in 1994 by Jean-Claude Bajard, Sylvanus Kla, and Jean-Michel Muller. BKM is based on computing complex logarithms (L-mode) and exponentials (E-mode) 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.

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.

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 approximations will depend on the availability of fast multi-bit shifts (i.e. a barrel shifter) or hardware floating point arithmetic.

References
    • Bajard, Jean-Claude; Kla, Sylvanus; Muller, Jean-Michel (August 1994). "BKM: A new hardware algorithm for complex elementary functions" (PDF). IEEE Transactions on Computers. 43 (8): 955–963. doi:10.1109/12.295857. ISSN 0018-9340. Archived (PDF) from the original on 2017-12-21. Retrieved 2017-12-21.
    • Bajard, Jean-Claude; Imbert, Laurent (1999-11-02). Luk, Franklin T. (ed.). "Evaluation of Complex Elementary Functions: A New Version of BKM" (PDF). SPIE Proceedings, Advanced Signal Processing Algorithms, Architectures, and Implementations IX. Advanced Signal Processing Algorithms, Architectures, and Implementations IX. Society of Photo-Optical Instrumentation Engineers (SPIE). 3807: 2–9. Bibcode:1999SPIE.3807....2B. doi:10.1117/12.367631. Retrieved 2020-06-09.
    • Imbert, Laurent; Muller, Jean-Michel; Rico, Fabien (2006-05-24) [2000-06-01, September 1999]. "Radix-10 BKM Algorithm for Computing Transcendentals on Pocket Computers". Journal of VLSI Signal Processing (Research report). Kluwer Academic Publishers / Institut national de recherche en informatique et en automatique (INRIA). 25 (2): 179–186. doi:10.1023/A:1008127208220. ISSN 0922-5773. RR-3754. INRIA-00072908. Theme 2. Archived from the original on 2018-07-11. Retrieved 2018-07-11.
    • Muller, Jean-Michel (2006). Elementary Functions: Algorithms and Implementation (2 ed.). Boston, MA, USA: Birkhäuser. ISBN 978-0-8176-4372-0. LCCN 2005048094.
    • Muller, Jean-Michel (2016-12-12). Elementary Functions: Algorithms and Implementation (3 ed.). Boston, MA, USA: Birkhäuser. ISBN 978-1-4899-7981-0.

    Further reading
    • Revol, Nathalie; Yakoubsohn, Jean-Claude. "Accelerated Shift-and-Add algorithms" (PDF). Boston, USA: Laboratoire d'Analyse Numérique et d'Optimisation (ANO) de l'Université des Sciences et Technologies de Lille; Kluwer Academic Publishers. Archived (PDF) from the original on 2017-12-21. Retrieved 2017-12-21.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.