級数の集約による多倍長数の計算法とπの計算への応用

URI http://harp.lib.hiroshima-u.ac.jp/hiroshima-cu/metadata/6534
File
Title
級数の集約による多倍長数の計算法とπの計算への応用
Title Alternative
Recursive Reduction of Series for Multiple-precision Evaluation and its Application to Pi Calculation
Author
氏名 右田 剛史
ヨミ ミギタ ツヨシ
別名 MIGITA Tsuyoshi
氏名 天野 晃
ヨミ アマノ アキラ
別名 AMANO Akira
氏名 浅田 尚紀
ヨミ アサダ ナオキ
別名 ASADA Naoki
氏名 藤野 清次
ヨミ フジノ セイジ
別名 FUJINO Seiji
Subject
級数の集約
πの計算
Chudnovskyの公式
Abstract

多数桁の数学定数, 特にπや自然対数の計算法として簡単に導出できる級数展開を用いる方法と, πにおけるGauss-Legendreの公式等の反復計算法が知られている.πに関しては, 従来N桁の値を得る計算量は, 級数によるとO(N^2), 反復計算法によるとO(N(logN)^2)とされ, Nが大きい時には反復計算法の方が格段に有利であると言われていた.本稿ではある種の級数に対して, 隣接する級数の項を集約することにより, O(N(logN)^3)の計算量で級数の和を計算する計算法を示した.この方法によって桁数Nが大きい時にも, 従来計算時間的に反復計算法より不利とされてきた級数による計算が, 同等の時間で行える, 本手法を用いることにより, 3.2万桁から5.3億桁のπの計算に関して, 級数の和を用いたChudnovskyの公式を, 反復計算によるGauss-Legendreの公式よりも高速に計算できることが明らかになった. / Multiple-precision mathematical constants, such as π or e are known to be calculated by sum of series. On the other hand, much faster calculation method that use iteration are known for some constants such as π. For the case of π, N digits calculation time by method of sum of series is said to be O(N^2), and that of iterational method is O(N(logN)^2).Thus, for large N, iterational method is far more efficient than that of sum of series. In this paper, we propose a fast algorithm of calculating sum of series in O(N(logN)^3)time by recursively reducing adjacent terms of series. With this algorithm, calculation time of sum of series become comparable to that of iterational method in case of large N. Experimental results on calculating 32, 000 to 530 million digits of π showed that the Chudnovsky formula which uses sum of series can be calculated faster than the Gauss-Legendre method which uses iterational method.

Journal Title
情報処理学会研究報告. [ハイパフォーマンスコンピューティング]
Volume
98
Issue
115
Spage
31
Epage
36
Published Date
1998-12-11
Publisher
社団法人情報処理学会
ISSN
0919-6072
NCID
AN10463942
NAID
110002932333
Language
jpn
NIIType
Technical Report
Text Version
出版社版
Rights
ここに掲載した著作物の利用に関する注意:本著作物の著作権は(社)情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 / The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. All Rights Reserved, Copyright (C) Information Processing Society of Japan.
本文データは学協会の許諾に基づきCiNiiから複製したものである
Relation
isVersionOf:http://ci.nii.ac.jp/naid/110002932333
Relation URL
Old URI
Set
hiroshima-cu