ショーンハーゲ・ストラッセン法
アルゴリズムの途中で、2の累乗(1の冪根を含む)との乗算・除算は多くの場合少数のシフト演算・加算によって置き換えられる。これは次の性質を利用している
(2) ≡ (−1) mod (2 + 1)
ここで 2 を基数とする位取り記数法において 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 2 + 1 において簡単に削減可能である。最下位である右端から n ビットを取り上げ、次の n ビットを引き、さらに次の n ビットを足す...と全てのビットに対して行う。
実際のシステムでショーンハーゲ・ストラッセン法を実装する際に用いられた実用的な最適化について述べる。主に2007年のゴードリー、Kruppa、ジマーマンのGNU Multi-Precision Libraryの機能拡張によるものである。
特定のカットオフポイント以下ではToom-3などの他のアルゴリズムを使用して再帰的に乗算を実行するほうが効率的である。結果を mod 2 + 1 を用いて削減する必要があるが、シフト最適化で説明した通り効率的に計算可能である。
逆離散フーリエ変換には各要素を 2 で割る計算が含まれる。この演算は同様に2の累乗で割る操作を含む A との乗算と組み合わせることが多い。
大きな数を 2 ビットのワードで表すシステムでは、ベクトルのサイズ 2 が1ワードあたりのビット数の倍数とすると便利である。(例えば32ビットのコンピュータでは k ≥ 5 、64ビットのコンピュータでは k ≥ 6 )。これにより、ビットシフト無しで入力を分割可能であり、高位のワードが0か1の場合に mod 2 + 1 で一様な表現ができる。
の結果の逆離散フーリエ変換を計算し、ベクトルCを得る。ここでも全ての積はシフト演算で行われる。これは補間に対応する。 シフト演算を用いて、ベクトルCに重みベクトルの逆行列 A を乗ずる。 符号を調整する:幾つかの要素は負になる。Cのj番目の最大のありえる要素 (j + 1)2 を計算し 2 + 1 を超えていればそれで引く。
最後に、mod 2 + 1 において繰り上がりを実行する。
分割数の最適な数は入力する数の桁数 N に対して N {\displaystyle {\sqrt {N}}} であり、O(N log N log log N) である。k は入力サイズとアーキテクチャに基づいて経験的に設定され、典型的には 4 から 16の値が用いられる。
ステップ2において、次の条件を満たしているかを確認する。
入力ベクトルの各要素は n/2 ビット以下か
入力ベクトルの要素の積は 2n/2 以下か
畳み込みの各要素は 2 個以下の総和であるため 2n/2 + k ビット未満か。
n は 2 を割り切れるか