BKM Algorithm
   HOME

TheInfoList



OR:

The BKM algorithm is a shift-and-add algorithm for computing
elementary function In mathematics, an elementary function is a function of a single variable (typically real or complex) that is defined as taking sums, products, roots and compositions of finitely many polynomial, rational, trigonometric, hyperbolic, and exponen ...
s, first published in 1994 by Jean-Claude Bajard, Sylvanus Kla, and Jean-Michel Muller. BKM is based on computing complex
logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number  to the base  is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
s (''L-mode'') and
exponential Exponential may refer to any of several mathematical topics related to exponentiation, including: *Exponential function, also: **Matrix exponential, the matrix analogue to the above * Exponential decay, decrease at a rate proportional to value *Exp ...
s (''E-mode'') using a method similar to the algorithm
Henry Briggs Henry Briggs may refer to: *Henry Briggs (mathematician) (1561–1630), English mathematician *Henry Perronet Briggs (1793–1844), English painter *Henry George Briggs (1824–1872), English merchant, traveller, and orientalist *Henry Shaw 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 CORDIC (for "coordinate rotation digital computer"), also known as Volder's algorithm, or: Digit-by-digit method Circular CORDIC (Jack E. Volder), Linear CORDIC, Hyperbolic CORDIC (John Stephen Walther), and Generalized Hyperbolic CORDIC (GH C ...
, but uses a table of
logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number  to the base  is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
s rather than a table of
arctangent In mathematics, the inverse trigonometric functions (occasionally also called arcus functions, antitrigonometric functions or cyclometric functions) are the inverse functions of the trigonometric functions (with suitably restricted domains). Spec ...
s. 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 In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
or
rational Rationality is the quality of being guided by or based on reasons. In this regard, a person acts rationally if they have a good reason for what they do or a belief is rational if it is based on strong evidence. This quality can apply to an abili ...
approximations will depend on the availability of fast multi-bit shifts (i.e. a
barrel shifter A barrel shifter is a digital circuit that can shift a data word by a specified number of bits without the use of any sequential logic, only pure combinational logic, i.e. it inherently provides a binary operation. It can however in theory also ...
) or hardware
floating point In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
arithmetic.


Overview

In order to solve the equation :\ln(x) = y the BKM algorithm takes advantage of a basic property of logarithms :\ln(ab) = \ln(a)+\ln(b) Using
Pi notation Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being addit ...
, this identity generalizes to :\ln\left(\prod_^n a_k\right) = \sum_^n\ln(a_k) Because any number can be represented by a product, this allows us to choose any set of values a_k 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 a_k = 1+2^m is a better option than a more simple choice of a_k = 2^m. Since we want to start with large changes and get more accurate as k increases, we can more specifically use a_k = 1+2^, allowing the product to approach any value between 1 and ~4.768, depending on which subset of a_k we use in the final product. At this point, the above equation looks like this: :\ln\left(\prod_ 1+2^\right) = \sum_\ln(1+2^) This choice of a_k reduces the computational complexity of the product from repeated multiplication to simple addition and bit-shifting depending on the implementation. Finally, by storing the values \ln(1+2^) 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 x while the other approaches the output value \ln(x)=y: x_k = \begin 1 & \text k = 0 \\ x_\cdot (1+2^) & \text x_k \text \leq x \\ x_ & \text \end Given this recursive definition and because x_k is strictly increasing, it can be shown by
induction Induction, Inducible or Inductive may refer to: Biology and medicine * Labor induction (birth/pregnancy) * Induction chemotherapy, in medicine * Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
and
convergence Convergence may refer to: Arts and media Literature *''Convergence'' (book series), edited by Ruth Nanda Anshen * "Convergence" (comics), two separate story lines published by DC Comics: **A four-part crossover storyline that united the four Wei ...
that :\lim_x_k = x for any 1 \leq x \lesssim 4.768. For calculating the output, we first create the reference table :A_k = \ln(1+2^) Then the output is computed iteratively by the definition y_k = \begin 0 & \text k = 0 \\ y_ + A_k & \text x_k \text \leq x \\ y_ & \text \end The conditions in this iteration are the same as the conditions for the input. Similar to the input, this sequence is also strictly increasing, so it can be shown that :\lim_y_k = y for any 0 \leq y \lesssim 1.562. Because the algorithm above calculates both the input and output simultaneously, it's possible to modify it slightly so that y is the known value and x is the value we want to calculate, thereby calculating the exponential instead of the logarithm. Since x becomes an unknown in this case, the conditional changes from :\dots \text x_k \text \leq x to :\dots \text y_k \text \leq y


Logarithm function

To calculate the logarithm function (L-mode), the algorithm in each iteration tests if x_n \cdot (1+2^) \le x. If so, it calculates x_ and y_. After N iterations the value of the function is known with an error of \Delta \ln(x) \le 2^. Example program for natural logarithm in C++ (see A_e for table): double log_e (const double Argument, const int Bits = 53) // 1 <= Argument <= 4.768462058 Logarithms for bases other than e can be calculated with similar effort. Example program for binary logarithm in C++ (see A_2 for table): double log_2 (const double Argument, const int Bits = 53) // 1 <= Argument <= 4.768462058 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.


Exponential function

To calculate the exponential function (E-mode), the algorithm in each iteration tests if y_n + \ln(1+2^) \le y. If so, it calculates x_ and y_. After N iterations the value of the function is known with an error of \Delta \exp(x) \le 2^. Example program in C++ (see A_e for table): double exp (const double Argument, const int Bits = 54) // 0 <= Argument <= 1.5620238332


Tables for examples

static const double A_e [] = // A_e[k] = ln (1 + 0.5^k) ; static const double A_2 [] = // A_2[k] = log_2 (1 + 0.5^k) ;


Notes


References

* * (5 pages

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.7521&rep=rep1&type=pdf] * (8 pages

* (1+15 pages

https://dl.acm.org/doi/10.1023/A%3A100812720822

*

(1+11 pages) *

* *


Further reading

* * * * (14 pages
https://web.archive.org/web/20171221172147/http://perso.ens-lyon.fr/nathalie.revol/publis/RY00.pdf-->
{{mathanalysis-stub Computer arithmetic Shift-and-add algorithms Digit-by-digit algorithms 1994 introductions 1994 in science