Calculation of π to 51.5 Billion Decimal Digits on Distributed Memory Parallel Processors

IR IR (HANDLE) IPSJ Web Site 6 Citations 26 References Open Access

Bibliographic Information

Other Title
  • 分散メモリ型並列計算機による円周率の515億桁計算
  • ブンサン メモリガタ ヘイレツ ケイサンキ ニヨル エンシュウリツ

Search this article

Description

本論文では，分散メモリ型並列計算機により高精度の円周率を高速に計算する方法について述べる．高精度の円周率は，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.

Journal

  • IPSJ Journal

    IPSJ Journal 39 (7), 2074-2083, 1998-07-15

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

Citations (6)*help

See more

References(26)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top