プログラミング/多倍長整数/ショーンハーゲ・ストラッセン法

ショーンハーゲ・ストラッセン法は、非常に大きな数同士の掛け算を効率的に計算するためのアルゴリズムです。[[../カラツバ法|カラツバ法]]や[[../Toom-Cook乗算|Toom-Cook法]]をさらに発展させたもので、より大きな数の掛け算に対して効果的です。 このアルゴリズムは、数を多項式として表現し、フーリエ変換を利用することで、掛け算の計算量を大幅に減らすことができます。

通常の掛け算との違い

通常の掛け算では、$n$桁の数同士を掛けると、$O(n^2)$の計算量が必要です。 一方、ショーンハーゲ・ストラッセン法では、理論的に$O(n\log n\log \log n)$の計算量で掛け算を行うことができます。

ショーンハーゲ・ストラッセン法の基本的な考え方

ショーンハーゲ・ストラッセン法の基本的な手順は以下の通りです：

1. 掛け算する大きな数を多項式として表現する
2. その多項式を評価点（複素数の根）で評価する
3. 評価点での値同士を掛け合わせる
4. 逆フーリエ変換を用いて、結果の多項式を復元する
5. 復元した多項式から、最終的な掛け算の結果を求める

多項式表現と評価点

例えば、大きな数 $A$ を次のように多項式として表現します：

$A=a_0+a_{1}x+a_2{x}^2+\cdots +a_{n-1}{x}^{n-1}$

ここで、$x=2^m$ （$m$ は適当な整数）とします。 評価点として、$2n$ 乗根の複素数を使用します：

$\omega =e^{2\pi i/(2n)}$

フーリエ変換の利用

ショーンハーゲ・ストラッセン法の核心は、高速フーリエ変換（FFT）を利用することです。FFTを使うことで、多項式の評価と補間を高速に行うことができます。

1. 多項式 $A(x)$ と $B(x)$ をFFTで変換する
2. 変換された値同士を掛け合わせる
3. 逆FFTで結果を元の多項式の形に戻す

なぜ効率的か

ショーンハーゲ・ストラッセン法が効率的な理由は以下の通りです：

1. FFTにより、多項式の評価と補間を高速に行える
2. 評価点での掛け算は単純な複素数の掛け算になる
3. 逆FFTも高速に行える

これらの要因により、全体の計算量を大幅に削減できます。

実用上の注意点

ショーンハーゲ・ストラッセン法は理論的には非常に効率的ですが、実装が複雑で、小さな数の掛け算ではオーバーヘッドが大きくなります。そのため、実際には非常に大きな数（数千桁以上）の掛け算で使用されることが多いです。

まとめ

ショーンハーゲ・ストラッセン法は、フーリエ変換を利用して大きな数の掛け算を高速に行うアルゴリズムです。理論的には非常に効率的ですが、実装が複雑なため、主に非常に大きな数の掛け算に使用されます。この方法は、現代の暗号技術や精度の高い数値計算など、様々な分野で重要な役割を果たしています。