BKMアルゴリズム

BKMアルゴリズムは、1994 年に Jean-Claude Bajard、Sylvanus Kla、Jean-Michel Muller によって初めて公開された、基本関数を計算するためのシフトおよび加算アルゴリズムです。BKM は、 Henry Briggs が対数を計算するために使用したアルゴリズムに類似した方法を使用して、複素対数( L モード) と指数( E モード) を計算することに基づいています。BKM アルゴリズムは、負の 2 の累乗の対数の事前計算されたテーブルを使用して、整数の加算、シフト、および比較演算のみを使用して基本関数を計算します。

BKM はCORDICに似ていますが、逆正接テーブルではなく対数テーブルを使用します。各反復で、係数は、CORDIC で使用される -1 または +1 のみではなく、1、0、-1、i、-i、1+i、1-i、-1+i、-1-i の 9 つの複素数のセットから選択されます。BKM は、いくつかの基本関数を計算するより簡単な方法を提供し、CORDIC とは異なり、BKM では結果のスケーリング係数は必要ありません。BKM の収束率は、CORDIC と同様に反復ごとに約 1 ビットですが、BKM ではテーブルに複素オペランドの対数が格納されるため、同じ精度でより多くの事前計算テーブル要素が必要になります。

シフトアンド加算クラスの他のアルゴリズムと同様に、BKM はハードウェア実装に特に適しています。多項式近似や有理近似などの他の方法と比較したソフトウェア BKM 実装の相対的なパフォーマンスは、高速マルチビット シフト (バレル シフタなど) またはハードウェア浮動小数点演算の可用性に依存します。

この方程式を解くには

${\displaystyle \ln(x)=y}$

BKMアルゴリズムは対数の基本的な性質を利用している

${\displaystyle \ln(ab)=\ln(a)+\ln(b)}$

円周率記法を用いると、この等式は次のように一般化される。

${\displaystyle \ln \left(\prod _{k=0}^{n}a_{k}\right)=\sum _{k=0}^{n}\ln(a_{k})}$

任意の数値は積で表すことができるため、任意の値のセットを選択して、その積を掛け合わせると元の値が得られます。コンピュータ システムでは、2 の倍数で乗算して除算する方がはるかに高速ですが、すべての数値が 2 の倍数であるとは限らないため、 を使用する方が、より単純な を選択するよりも優れたオプションです。最初は大きな変化から始めて、 が増加するにつれて精度を上げたいので、より具体的に を使用すると、最終積で使用する のサブセットに応じて、積が 1 から ~4.768 までの任意の値に近づくようになります。この時点で、上記の式は次のようになります。 ${\displaystyle a_{k}}$${\displaystyle a_{k}=1+2^{m}}$${\displaystyle a_{k}=2^{m}}$${\displaystyle k}$${\displaystyle a_{k}=1+2^{-k}}$${\displaystyle a_{k}}$

${\displaystyle \ln \left(\prod _{k\in K\subset \mathbb {Z} _{0}^{+}}1+2^{-k}\right)=\sum _{k\in K\subset \mathbb {Z} _{0}^{+}}\ln(1+2^{-k})}$

この選択により、積の計算の複雑さが、実装に応じて、繰り返しの乗算から単純な加算とビットシフトに軽減されます。最後に、値をテーブルに格納することで、解の計算も単純な加算になります。反復すると、2 つの別々のシーケンスが得られます。1 つのシーケンスは入力値に近づき、もう 1 つは出力値に近づきます。 ${\displaystyle a_{k}}$${\displaystyle \ln(1+2^{-k})}$${\displaystyle x}$${\displaystyle \ln(x)=y}$

$${\displaystyle x_{k}={\begin{cases}1&{\text{if }}k=0\\x_{k-1}\cdot (1+2^{-k})&{\text{if }}x_{k}{\text{ would be}}\leq x\\x_{k-1}&{\text{otherwise}}\end{cases}}}$$

この再帰的定義と、が厳密に増加していることから、帰納法と収束法によって次のことが示される。 ${\displaystyle x_{k}}$

${\displaystyle \lim _{k\to \infty }x_{k}=x}$

出力を計算するために、まず参照テーブルを作成します。 ${\displaystyle 1\leq x\lesssim 4.768}$

${\displaystyle A_{k}=\ln(1+2^{-k})}$

そして、出力は定義に従って反復的に計算されます 。この反復における条件は入力の条件と同じです。入力と同様に、このシーケンスも厳密に増加するため、次のように示されます。 $${\displaystyle y_{k}={\begin{cases}0&{\text{if }}k=0\\y_{k-1}+A_{k}&{\text{if }}x_{k}{\text{ would be}}\leq x\\y_{k-1}&{\text{otherwise}}\end{cases}}}$$

${\displaystyle \lim _{k\to \infty }y_{k}=y}$

いずれの場合も。 ${\displaystyle 0\leq y\lesssim 1.562}$

上記のアルゴリズムは入力と出力の両方を同時に計算するため、 が既知の値でが計算したい値になるように少し変更して、対数ではなく指数を計算することができます。この場合、xは未知数となるため、条件は次のように変わります。 ${\displaystyle y}$${\displaystyle x}$

${\displaystyle \dots {\text{if }}x_{k}{\text{ would be}}\leq x}$

に

${\displaystyle \dots {\text{if }}y_{k}{\text{ would be}}\leq y}$

対数関数 (L モード) を計算するために、アルゴリズムは各反復で かどうかをテストします。 そうである場合は、および を計算します。反復後、関数の値は の誤差でわかります。 ${\displaystyle x_{n}\cdot (1+2^{-n})\leq x}$${\displaystyle x_{n+1}}$${\displaystyle y_{n+1}}$${\displaystyle N}$${\displaystyle \Delta \ln(x)\leq 2^{-N}}$

C++ での自然対数のサンプル プログラム (A_e表を参照):

 double log_e ( const double Argument , const int Bits = 53 ) // 1 <= Argument <= 4.768462058 { double x = 1.0 , y = 0.0 , s = 1.0 ;          
 
              

    for ( int k = 0 ; k < Bits ; k ++ ) { double const z = x + x * s ; if ( z <= Argument ) { x = z ; y += A_e [ k ]; } s *= 0.5 ; } return y ; }         
             
          
             
            
      
        
    
     
 

e以外の底の対数も同様の手順で計算できます。

C++ での 2 進対数計算のサンプル プログラム (A_2表を参照):

 double log_2 ( const double Argument , const int Bits = 53 ) // 1 <= Argument <= 4.768462058 { double x = 1.0 , y = 0.0 , s = 1.0 ;          
 
              

    for ( int k = 0 ; k < Bits ; k ++ ) { double const z = x + x * s ; if ( z <= Argument ) { x = z ; y += A_2 [ k ]; } s *= 0.5 ; } return y ; }         
             
          
             
            
      
        
    
     
 

どちらの例でも、許容される引数の範囲は同じです (1 ≤  Argument ≤ 4.768462058…)。底が 2 の対数の場合、指数を事前に分割して (整数部分を取得するため)、アルゴリズムを剰余 (1 と 2 の間) に適用できます。引数は 2.384231… より小さいため、kの反復は 1 から開始できます。どちらの底でも、s による乗算は、浮動小数点指数を直接変更して、反復ごとに 1 を減算することで置き換えることができます。これにより、アルゴリズムは乗算をせずに加算のみを使用します。

指数関数 (E モード) を計算するために、アルゴリズムは各反復で かどうかをテストします。 そうである場合は、および を計算します。反復後、関数の値は の誤差でわかります。 ${\displaystyle y_{n}+\ln(1+2^{-n})\leq y}$${\displaystyle x_{n+1}}$${\displaystyle y_{n+1}}$${\displaystyle N}$${\displaystyle \Delta \exp(x)\leq 2^{-N}}$

C++ のサンプルプログラム (A_e表を参照):

 double exp ( const double Argument , const int Bits = 54 ) // 0 <= Argument <= 1.5620238332 { double x = 1.0 , y = 0.0 , s = 1.0 ;         	
 
             

   for ( int k = 0 ; k < Bits ; k ++ ) { double const z = y + A_e [ k ]; if ( z <= Argument ) { y = z ; x = x + x * s ; } s *= 0.5 ; } return x ; }         
             
          
           
             
      
        
   
    
 

• Bajard, Jean - Claude; Kla, Sylvanus; Muller, Jean-Michel (1994 年 8 月)。「BKM: 複雑な基本関数の新しいハードウェア アルゴリズム」 ( PDF)。IEEE Transactions on Computers。43 ( 8): 955–963。doi : 10.1109 /12.295857。ISSN 0018-9340。Zbl 1073.68501。2018年 11 月 3 日にオリジナルから アーカイブ(PDF) 。2017年 12 月 21 日に取得。
• Skaf, Ali; Muller, Jean-Michel; Guyot, Alain ( 1994 年 9 月 20 ～ 22 日)。複素指数関数と対数関数のオンライン ハードウェア実装。ESSCIRC '94: 第 20 回ヨーロッパ固体回路会議。ドイツ、ウルム。CiteSeerX  10.1.1.47.7521。ISBN 2-86332-160-9. 2021年8月23日閲覧。（5ページ）[1][2]
• Bajard, Jean-Claude; Imbert, Laurent (1999-11-02). 「複素基本関数の評価: BKM の新しいバージョン」( PDF)。Luk, Franklin T. (ed.). Advanced Signal Processing Algorithms, Architectures, and Implementations IX 。Vol . 3807。Society of Photo-Optical Instrumentation Engineers (SPIE)。pp. 2–9。Bibcode :1999SPIE.3807....2B。doi :10.1117/12.367631。S2CID 121001818。2020-06-09にオリジナルから アーカイブ(PDF) 。2020-06-09に取得。 {{cite book}}:|journal=無視 (ヘルプ) (8ページ) [3]
• アンベール、ローラン。ミュラー、ジャン＝ミシェル。リコ、ファビアン (2006-05-24) [2000-06-01、1999 年 9 月]。 「ポケット コンピューターで超越計算を行うための Radix-10 BKM アルゴリズム」。VLSI 信号処理ジャーナル(研究レポート)。25 (2)。Kluwer Academic Publishers / Institut National de recherche en informatique et en automatique (INRIA): 179–186。土井:10.1023/A:1008127208220。ISSN  0922-5773。S2CID  392036。RR-3754。 INRIA-00072908。テーマ 2 ISSN  0249-6399。 2018年7月11日時点のオリジナルよりアーカイブ。2018年7月11日閲覧。（1+15ページ）[4][5][6]
• Didier, Laurent-Stéphane; Rico, Fabien (2002-01-21). 「High radix BKM algorithm with Selection by Rounding」(PDF) . S2CID  17750192. lip6.2002.009. hal-02545612. 2021-08-23 にオリジナルからアーカイブ(PDF)されました。 2021-08-23に取得。[7] (1+11ページ)
• Didier, Laurent-Stéphane; Rico, Fabien (2004-12-01). 「高基数 BKM アルゴリズム」.数値アルゴリズム. SCAN'2002 国際会議. 37 (1–4 [4]). Springer Science+Business Media, LLC : 113–125. Bibcode :2004NuAlg..37..113D. doi :10.1023/B:NUMA.0000049459.69390.ff. eISSN  1572-9265. ISSN  1017-1398. S2CID  2761452.[8]
• Muller, Jean-Michel (2006).初等関数: アルゴリズムと実装(第 2 版). ボストン、マサチューセッツ州、米国: Birkhäuser . ISBN 978-0-8176-4372-0LCCN  2005048094 。
• Muller, Jean-Michel (2016-12-12).初等関数: アルゴリズムと実装(第 3 版). ボストン、マサチューセッツ州、米国: Birkhäuser . ISBN 978-1-4899-7981-0. ISBN 1-4899-7981-6 . 

• ヨーク、ギュンター。ランペ、ベルンハルト。ノルベルト・ウェンゲル (1989)。 Arithmetische Algorithmen der Mikrorechentechnik (ドイツ語) (第 1 版)。ベルリン、ドイツ: VEB Verlag Technik。 280–282ページ。ISBN 3-34100515-3. ISBN 978-3-34100515-6 . EAN  9783341005156. MPN 5539165. ライセンス 201.370/4/89 . 2015年12月1日閲覧。 
• Meggitt, John E. (1961-08-29). 「疑似除算および疑似乗算プロセス」。IBM Journal of Research and Development . 6 (2). 米国ニュージャージー州リバートン: IBM Corporation (1962 年 4 月発行): 210–226, 287. doi :10.1147/rd.62.0210 . 2015 年 12 月 1 日閲覧。
• Chi Chen, Tien (1972 年 7 月)。「指数、対数、比率、平方根の自動計算」。IBM Journal of Research and Development。16 ( 4)。米国カリフォルニア州サンノゼ、ニュージャージー州リバートン: IBM サンノゼ研究所、IBM Corporation : 380–388。doi :10.1147/rd.164.0380。2015年 12 月 1 日に閲覧。
• ナタリー・レボル;ヤコブソン、ジャン＝クロード (2000-05-01)。 「高速化されたシフトアンド加算アルゴリズム」(PDF)。信頼性の高いコンピューティング。6 (2)。米国、ボストン:リール科学技術大学の数値解析および最適化研究所 (ANO) 。Kluwer Academic Publishers : 193–205。土井:10.1023/A:1009921407000。eISSN  1573-1340。ISSN  1385-3139。OCLC  67306353. S2CID 10716391. 2021-08-23 のオリジナルから アーカイブ(PDF) 。2021年8月23日閲覧。（14ページ）[9]