BKM-Algorithmus
# BKM-Algorithmus

Der BKM-Algorithmus ist ein iterativer Algorithmus, mit dessen Hilfe sich die Logarithmus- und Exponentialfunktion effizient in digitalen Schaltungen berechnen lassen. Er wurde 1994 von J. C. Bajard, S. Kla und Jean-Michel Muller entwickelt, wovon sich auch die Bezeichnung ableitet.

## Allgemeines

Der BKM-Algorithmus ist wie CORDIC-Algorithmus ein so genannter Shift-and-add-Algorithmus, der auf bitweisen Verschiebungen und ganzzahligen Additionen in Addierwerken basiert. Divisionen werden ausschließlich mit negativen Potenzen von 2 durchgeführt, welche sich in digitalen Schaltungen direkt als bitweise Verschiebung implementieren lassen. Der Algorithmus kommt im Gegensatz zu dem CORDIC-Verfahren ohne Skalierungsfaktor aus und verwendet Logarithmentabellen anstelle der bei CORDIC notwendigen Arkustangens-Tabelle.

Die Berechnung eines Funktionswertes erfolgt in einem Iterationsverfahren mit einer Konvergenzrate von ungefähr einem Bit pro Durchlauf. Aufgrund dieses Umstands wird dieser Algorithmus manchmal auch als Bitalgorithmus bezeichnet.

## Herleitung

Gegeben sei die Iterationsvorschrift

    $x_{n+1}=x_{n}\cdot (1+d_{n}\cdot 2^{-n})$

mit $x_{0}=1$ und $d_{n}\in \{0,1\}$. Die Iterationsvorschrift ist per Induktion identisch mit

    $x_{n+1}=\prod _{i=0}^{n}(1+2^{-i})^{d_{i}}$

Sind alle $d_{n}=0$, so sind alle $x_{n}=1$. Sind alle $d_{n}=1$ gilt $x_{\infty }\approx 4{,}768$. Tatsächlich kann mit der Iterationsvorschrift bei geeigneter Wahl der $d_{n}$ jede reelle Zahl $x$ im Bereich $1\leqq x\lessapprox 4{,}768$ als Grenzwert dargestellt werden.

Weiterhin gelte die Iterationsvorschrift

    $y_{n+1}=y_{n}+d_{n}\cdot \ln(1+2^{-n})$

mit $y_{0}=0$ oder äquivalent dazu

    $y_{n+1}=\sum _{i=0}^{n}d_{i}\cdot \ln(1+2^{-i})=\ln \left(\prod _{i=0}^{n}(1+2^{-i})^{d_{i}}\right)$.

Für numerische Berechnungen wird $A_{n}=\ln(1+2^{-n})$ durch eine vorab berechnete Tabelle realisiert.

Es folgt sofort, dass $y_{n}=\ln(x_{n})$ für alle $n$ gilt. Mit denselben Überlegungen wie oben ergibt sich für den Logarithmus der Bereich $0\leqq y=\ln(x)\lessapprox 1{,}562$.

## Logarithmusfunktion

Um die Logarithmusfunktion zu berechnen (dies wird beim BKM-Algorithmus auch als L-mode bezeichnet), wird in jedem Schritt getestet, ob $x_{n}\cdot (1+2^{-n})\leq x$ ist. Wenn ja, wird $x_{n+1}$ und $y_{n+1}$ berechnet. Nach $N$ Schritten ist der Funktionswert mit einem Fehler $\Delta \ln(x)\leq 2^{-N}$ bestimmt.

Beispiel als C++-Programm (Tabelle A_e unten):

Auch andere Logarithmen lassen sich ohne Mehraufwand berechnen. Enthält die Tabelle die Werte für einen anderen Logarithmus als den zur Basis e, dann berechnet die Funktionen eben diesen Logarithmus (Tabelle A_2 ebenfalls im Anhang):

Der erlaubte Bereich für das Argument ist der gleiche (1 ≤ Argument ≤ 4,768462058…). Im Fall des Logarithmus zur Basis 2 kann man den Exponenten vorher abtrennen (erhält damit den ganzzahligen Anteil des Logarithmus) und wendet auf das Restargument (welches zwischen 1 und 2 liegt) den Bitalgorithmus an. Da das Argument kleiner als 2,384231… ist, braucht die Iterationsschleife von k erst ab 1 anzufangen.

## Exponentialfunktion

Um die Exponentialfunktion zu berechnen (dies wird beim BKM-Algorithmus auch als E-mode bezeichnet), wird in jedem Schritt getestet, ob $y_{n}+\ln(1+2^{-n})\leq y$ ist. Wenn ja, wird $x_{n+1}$ und $y_{n+1}$ berechnet. Nach $N$ Schritten ist der Funktionswert mit einem Fehler $\Delta \exp(x)\leq 2^{-N}$ bestimmt.

Beispiel als C++-Programm (Tabelle A_e unten):

