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

Access this Article

Search this Article

Author(s)

Abstract

多数桁乗算を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.

Journal

  • IPSJ journal

    IPSJ journal 46(5), 1266-1273, 2005-05-15

    Information Processing Society of Japan (IPSJ)

References:  8

Codes

  • NII Article ID (NAID)
    110002768632
  • NII NACSIS-CAT ID (NCID)
    AN00116647
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7764
  • NDL Article ID
    7359811
  • NDL Source Classification
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL Call No.
    Z14-741
  • Data Source
    CJP  NDL  NII-ELS  IPSJ 
Page Top