BKM algorithm とは

BKMアルゴリズムは、1994年にJean-Claude Bajard、Sylvanus Kla、Jean-Michel Mullerによって最初に出版された、基本関数を計算するためのシフト・アンド・アロッドアルゴリズムです。 BKMは、ヘンリー・ブリッグス(Henry Briggs)が対数を計算するために使用したアルゴリズムと同様の方法を使用して、複雑な対数(Lモード)および指数関数(Eモード)を計算することに基づいています。 BKMアルゴリズムは、負の2乗の対数の事前計算テーブルを使用することによって、整数加算、シフト、および比較演算のみを使用して基本関数を計算します。
BKMはCORDICに似ていますが、アークタンジェントの表ではなく対数の表を使用します。各反復において、係数の選択は、9つの複素数の組である1,0、-1、i、-i、1 + i、1-i、-1 + i、-1-iから行われる。 CORDICが使用する-1または+1のみ。 BKMは、いくつかの基本関数を計算する簡単な方法を提供し、CORDICとは異なり、BKMは結果スケーリング係数を必要としません。 BKMの収束率は、CORDICのように反復ごとに約1ビットですが、複雑なオペランドの対数がテーブルに格納されるため、BKMは同じ精度で事前計算されたテーブル要素を多く必要とします。
shift-and-addクラスの他のアルゴリズムと同様に、BKMはハードウェアの実装に特に適しています。多項式または有理数近似のような他の方法と比較したソフトウェアBKM実装の相対的性能は、高速マルチビットシフト(すなわち、バレルシフタ)またはハードウェア浮動小数点演算の利用可能性に依存する。