シフト最適化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/28 23:15 UTC 版)
「ショーンハーゲ・ストラッセン法」の記事における「シフト最適化」の解説
アルゴリズムの途中で、2の累乗（1の冪根を含む）との乗算・除算は多くの場合少数のシフト演算・加算によって置き換えられる。これは次の性質を利用している (2n)k ≡ (−1)k mod (2n + 1) ここで 2n を基数とする位取り記数法において k 桁の数は ( d k − 1 , … , d 1 , d 0 ) {\displaystyle \scriptstyle (d_{k-1},\dots ,d_{1},d_{0})} と表され、 ∑ i = 0 k − 1 d i ⋅ ( 2 n ) i {\displaystyle \scriptstyle \sum _{i=0}^{k-1}d_{i}\cdot (2^{n})^{i}} の数を示し、それぞれは d i {\displaystyle \scriptstyle d_{i}} 0 ≤ d i < 2 n {\displaystyle \scriptstyle 0\leq d_{i}<2^{n}} である。 この表現により、数を mod 2N + 1 において簡単に削減可能である。最下位である右端から n ビットを取り上げ、次の n ビットを引き、さらに次の n ビットを足す…と全てのビットに対して行う。その結果が 0 から 2n の範囲にない場合は、2N + 1 の倍数を足すことで正規化する。例えば、 n = 3 であり法が23+1 = 9 である場合に 656 は以下のように減らされる。 656 = 1 010 010 0002 ≡ 0002 − 0102 + 0102 − 12 = 0 − 2 + 2 − 1 = −1 ≡ 8 (mod 23 + 1). さらに、シフト演算の結果を構築することなく、非常に大きなシフトを行える。0 から 2n の範囲のAを考え、それに 2kを乗じたい場合には、k を n で割って k = qn + r ( r < n )を得る。このとき A(2k) = A(2qn + r) = A[(2n)q(2r)] ≡ (−1)q · shl(A, r) (mod 2n + 1). が成り立つ。ここで、shl(A, r)は A を r ビット左シフトしたものである。A は 2n 以下で、 r < n であるため、r ビット左シフトされた A は高々 2n−1 ビットであり、1回のシフト演算と正規化のための減算のみが必要である。 最後に、 2k で割る場合には、2nが原始根であることを用いれば 22n ≡ 1 (mod 2n + 1) である。したがって A/2k = A(2−k) ≡ A(22n − k) = shl(A, (2n − k) (mod 2n + 1))である。
※この「シフト最適化」の解説は、「ショーンハーゲ・ストラッセン法」の解説の一部です。
「シフト最適化」を含む「ショーンハーゲ・ストラッセン法」の記事については、「ショーンハーゲ・ストラッセン法」の概要を参照ください。
- シフト最適化のページへのリンク
