著者

高橋 大介 金田 康正

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.39, no.7, pp.2074-2083, 1998-07-15

参考文献数

26

被引用文献数

6

---

本論文では,分散メモリ型並列計算機により高精度の円周率を高速に計算する方法について述べる.高精度の円周率は,Gauss?Legendreの公式およびBorweinの4次の収束の公式を用いると効率良く計算できることが知られている.これら2つの公式には平方根や4乗根,そして逆数計算が含まれているが,それらの計算はNewton法を適用することで,多倍長数の加減乗算に帰着させることができる.n桁どうしの多倍長乗算は高速Fourier変換(FFT)を用いればO (nlognloglogn)で行えるが,多倍長乗算の主要部分であるFFTの計算および多倍長数の加減乗算における正規化の部分を並列化した.その結果,1024プロセッサから成る分散メモリ型並列計算機HITACHI SR2201で515億桁余りの円周率の計算が検証時間を含めて66時間11分で終了した.This paper discusses the fast multiple-precision calculation of π on distributed memory parallel processors.It is well knowen that the multiple-precision π can be efficiently computed by the Gauss-Legendre algorithm and the Borweins' quartically convergent algorithm.Although two algorithms include the square root,4th root and reciprocal calculation,these calculations can be reduced to the multiple-precision addition,subtracion and multiplication by using Newton method.Multiple-precision multiplication of n digits numbers can be realized with the computational complexity of O(nlognloglogn)by using fast Fourier transform(FFT).Calculation of FFT which is crucial to the multiple-precision multiplication and normalization of the multiple-precision addition,subtraction and multiplication can be parallelized.More than 51.5 billion decimal digits of π were calculated on the distributed memory parallel processor HITACHI SR2201(1024PEs)within computing elapsed time of 66 hours 11 minutes which includes the time for the verification.