数値演算法 (4) 高速フーリエ変換乗算処理を高速化するための手法として、前回は Karatsuba法と Toom-Cook法を紹介しました。どちらの方法も、数値を多項式として表現してその各係数を求めることによって、乗算結果を得ることができるということを利用しています。今回は、多項式を利用した手法としてまずは一般的な解法を考え、最終的には高速フーリエ変換を利用した乗算処理の高速化について説明したいと思います。 ● 「(2)多倍長整数の演算」の加算ルーチンについて 今回紹介するサンプル・プログラムの作成中、「(2)多倍長整数の演算」内の加算ルーチン(operator+=)においてバグが見つかり、修正を行いました。もし利用されている方がいましたら、差し替えをお願いします。バグの内容については、「(2)多倍長整数の演算」ページ下の更新履歴の中で簡単に説明してあります。
