多数桁分割乗算の高速計算法 Fast Computation Method for High-precision Divide Multiplication

この論文にアクセスする

この論文をさがす

著者

抄録

多数桁乗算をm分割して計算するアルゴリズムを提案する.本分割乗算は,拡張FMT(高速剰余変換)3) の適用によりFMTをm分割しても分割しないときと同じ計算量にする方法と,ダイレクトI/Oにより必要なデータを非連続に入出力して,総I/O量を分割数に依存させなくする方法で構成される.分割乗算の具体的例として2段階FMTのアルゴリズムと数値実験結果を示す.ファイルI/Oを使用した多数桁の分割乗算は,使用計算機のメモリ容量を超えた桁数の乗算をする場合に必要となる.n桁の多数桁の乗算はFFT(高速フーリエ変換)を使用して,O(n log n(log log n)) 1) の計算量で計算できることが知られている.一方,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に減少する.In this paper, I would like to present a new algorithm for high-precision multiplication method with m-division. This algorithm consists of the two methods. The first is a method of keeping to constancy even if many divide the computational complexity of the high-precision multiplication with the FMT (Fast Modula Transformation) 3). The second is a method of keeping the amount of total I/O constant with direct I/O. In this paper, the algorithm of the division multiplication that uses the two stage FMT, and the numeric experiment results are shown. The divide multiplication is necessary at the number of digits that exceeds the memory capacity of the using computer. It is known to be able calculate with O(n log n(log log n)) 1) for n-digit precision multiplication by the Fast Fourier Transformation (FFT). On the other hand, when the FFT is applied by m-division, the computational complexity becomes m time. Moreover, if m-division multiplication is done by using file I/O, the amount of I/O becomes O(mn). Then, Ipropose the use of the FMT to the divide multiplication. The FMT can enable m-division multiplication of n-digit precision with O(n log n(log log n)), and make the amount of I/O O(n). Using this method for high-precision multiplication, the memory usage is reduced to 1/m with m-division, and the computational complexity and the amount of I/O that don't depend on number of divison m.

In this paper, I would like to present a new algorithm for high-precision multiplication method with m-division. This algorithm consists of the two methods. The first is a method of keeping to constancy even if many divide the computational complexity of the high-precision multiplication with the FMT (Fast Modula Transformation). The second is a method of keeping the amount of total I/O constant with direct I/O. In this paper, the algorithm of the division multiplication that uses the two stage FMT, and the numeric experiment results are shown. The divide multiplication is necessary at the number of digits that exceeds the memory capacity of the using computer. It is known to be able calculate with O(n log n (log log n)) for n-digit precision multiplication by the Fast Fourier Transformation(FFT). On the other hand, when the FFT is applied by m-division, the computational complexity becomes m time. Moreover, if m-division multiplication is done by using file I/O, the amount of I/O becomes O(mn). Then, I propose the use of the FMT to the divide multiplication. The FMT can enable m-division multiplication of n-digit precision with O (n log n(log log n)), and make the amount of I/O O(n). Using this method for high-precision multiplication, the memory usage is reduced to 1/m with m-division, and the computational complexity and the amount of I/O that don't depend on number of divison m.

収録刊行物

  • 情報処理学会論文誌

    情報処理学会論文誌 46(5), 1266-1273, 2005-05-15

    一般社団法人情報処理学会

参考文献:  8件中 1-8件 を表示

各種コード

  • NII論文ID(NAID)
    110002768632
  • NII書誌ID(NCID)
    AN00116647
  • 本文言語コード
    JPN
  • 資料種別
    Journal Article
  • ISSN
    1882-7764
  • NDL 記事登録ID
    7359811
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-741
  • データ提供元
    CJP書誌  NDL  NII-ELS  IPSJ 
ページトップへ