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.
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.
In order to solve the equation the BKM algorithm takes advantage of a basic property of logarithms Using Pi notation, this identity generalizes to Because any number can be represented by a product, this allows us to choose any set of values
which multiply to give the value we started with.
In computer systems, it's much faster to multiply and divide by multiples of 2, but because not every number is a multiple of 2, using
, allowing the product to approach any value between 1 and ~4.768, depending on which subset of
reduces the computational complexity of the product from repeated multiplication to simple addition and bit-shifting depending on the implementation.
in a table, calculating the solution is also a simple matter of addition.
Iteratively, this gives us two separate sequences.
One sequence approaches the input value
is strictly increasing, it can be shown by induction and convergence that for any
For calculating the output, we first create the reference table Then the output is computed iteratively by the definition
Similar to the input, this sequence is also strictly increasing, so it can be shown that for any
Because the algorithm above calculates both the input and output simultaneously, it's possible to modify it slightly so that
Since x becomes an unknown in this case, the conditional changes from to To calculate the logarithm function (L-mode), the algorithm in each iteration tests if
iterations the value of the function is known with an error of
Example program for natural logarithm in C++ (see A_e for table): Logarithms for bases other than e can be calculated with similar effort.
Example program for binary logarithm in C++ (see A_2 for table): The allowed argument range is the same for both examples (1 ≤ Argument ≤ 4.768462058…).
In the case of the base-2 logarithm the exponent can be split off in advance (to get the integer part) so that the algorithm can be applied to the remainder (between 1 and 2).
Since the argument is smaller than 2.384231…, the iteration of k can start with 1.
Working in either base, the multiplication by s can be replaced with direct modification of the floating point exponent, subtracting 1 from it during each iteration.
This results in the algorithm using only addition and no multiplication.
To calculate the exponential function (E-mode), the algorithm in each iteration tests if
iterations the value of the function is known with an error of