多数桁分割乗算の高速計算法(数値計算)

概要

論文の詳細を見る
多数桁乗算をm分割して計算するアルゴリズムを提案する.本分割乗算は, 拡張FMT(高速剰余変換)の適用によりFMTをm分割しても分割しないときと同じ計算量にする方法と, ダイレクトI/Oにより必要なデータを非連続に入出力して, 総I/O量を分割数に依存させなくする方法で構成される.分割乗算の具体的例として2段階FMTのアルゴリズムと数値実験結果を示す.ファイルI/Oを使用した多数桁の分割乗算は, 使用計算機のメモリ容量を超えた桁数の乗算をする場合に必要となる.n桁の多数桁の乗算はFFT(高速フーリエ変換)を使用して, O(n log n(log log n))の計算量で計算できることが知られている.一方, FFT使用した多数桁乗算をm分割すると, 計算量は分割しないときのm倍になるといわれている.また, ファイルI/Oを利用しFFTによる多数桁乗算をm分割すると, ファイルI/Oの総量も分割しないときのm倍になるといわれている.これに対して, FMTによるm分割乗算のアルゴリズムを使用すると, n桁計算の計算量はO(n log n(log log n))でファイルI/Oの総量はO(n)となり, ともに分割しないときと同じで, n桁計算に必要なメモリ量は分割しないときの約1/mに減少する.
一般社団法人情報処理学会の論文
2005-05-15