ホーム ] 実行時間計測ラブラリ ] EXIF情報ライブラリ ] 文字式演算 ] クイックソートライブラリ ] 多倍長演算ライブラリ ] 多倍長演算ライブラリU ] 画像処理ライブラリ ]

上へ
概要
プログラミング仕様
演算速度
技術解説(システム編)
技術解説(四則演算編)
技術解説(FFT編)
技術解説(数学関数編)

多倍長演算ライブラリ(MegaPrecision)

技術解説(FFT編)

最終更新日:2007/04/26 新規

●概要

 従来の手法による乗算と除算では、精度が高くなると急激に遅くなる、これは桁数の自乗に比例するからである。高速化としては、FFTによる乗算と、FFT乗算によるニュートン法の逆数除算が定石である。それらについて紹介する。

FFT乗算

 従来算法の乗算では、やはり遅いので、世の中的なFFT乗算も導入している。

逆数除算

 乗算が高速化されれば、除算の高速化となるが、高速除算は、一般には、逆数法が用いられる。つまり、A / B は、A * (1 / B) とするのである。これは、FFT乗算が可能な環境で、且つ逆数を高速に求められることが前提となる。