Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
BKM algorithm
open-in-new
<p> The BKM algorithm is a <a href="/facts/Shift-and-add_algorithm/68xf6EdK">shift-and-add algorithm</a> for computing <a href="/facts/Elementary_function_(differential_algebra)/wVFyDwu8">elementary functions</a>, first published in 1994 by Jean-Claude Bajard, Sylvanus Kla, and Jean-Michel Muller. BKM is based on computing complex <a href="/facts/Logarithm/QeXaV97q">logarithms</a> (<i>L-mode</i>) and <a href="/facts/Exponential_function/ewlYxvR2">exponentials</a> (<i>E-mode</i>) using a method similar to the algorithm <a href="/facts/Henry_Briggs_(mathematician)/ctMJIVNG">Henry Briggs</a> 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. </p><p>BKM is similar to <a href="/facts/CORDIC/sQqTjkd2">CORDIC</a>, but uses a table of <a href="/facts/Logarithm/QeXaV97q">logarithms</a> rather than a table of <a href="/facts/Arctangent/bVwU9FPG">arctangents</a>. 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. </p><p>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 <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> or <a href="/facts/Rational_function/2nJGu0Ko">rational</a> approximations will depend on the availability of fast multi-bit shifts (i.e. a <a href="/facts/Barrel_shifter/bHuSGHwH">barrel shifter</a>) or hardware <a href="/facts/Floating_point/eIckahxe">floating point</a> arithmetic. </p>