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

URI http://harp.lib.hiroshima-u.ac.jp/hiroshima-cu/metadata/6533
ファイル
タイトル
級数の再帰的集約による多倍長数の計算法とπの計算への応用
別タイトル
Recursive Reduction of Series for Multiple-precision Evaluation and Its Application to Pi Calculation
著者
氏名 右田 剛史
ヨミ ミギタ ツヨシ
別名 MIGITA Tsuyoshi
氏名 天野 晃
ヨミ アマノ アキラ
別名 AMANO Akira
氏名 浅田 尚紀
ヨミ アサダ ナオキ
別名 ASADA Naoki
氏名 藤野 清次
ヨミ フジノ セイジ
別名 FUJINO Seiji
抄録

数学定数である円周率πの多数桁の計算法として,級数展開を用いる方法とGauss-Legendreの公式などを用いる反復計算法が知られている.従来,N桁のπの値を得る計算量は,級数を用いるとO(N^2),反復計算法を用いるとO(N(log N)^2)とされ,Nが大きいときには反復計算法の方が有利であると考えられていた.本稿では,まず級数計算が2×2行列の積として表現できることを示し,次に隣接する2つの行列の積を再帰的に計算することによって級数を集約し,多倍長乗算を利用して級数の和をO(N(log N)^3)の計算量で求める方法について述べる.本手法を用いることによって,桁数Nが大きくなっても,級数による計算が反復計算法と同等の時間で行えることを確認した.また,3.2万桁から5.3億桁のπの計算時間の変化を調べた結果,級数の和を求めるChudnovskysの公式は,反復計算によるGauss-Legendreの公式よりも高速に計算できることが分かった. / A multiple-precision constant π of N digits is so far calculated by sum of series in O(N^2) computation time as well as by using iterational algorithm in O(N(log N)^2) time. In this paper, we first prove that the series for π calculation can be represented as a product of 2×2 matrices, and then propose a fast algorithm for calculating sum of series in O(N(log N)^3) time by recursively reducing the adjacent matrices. Using this algorithm, computation time of sum of series becomes comparable to that of iterational algorithm, and experimental results on calculating 32,000 to 530 million digits of π have shown that the sum of series using Chudnovskys formula is computed faster than the iterational algorithm using Gauss-Legendre algorithm.

査読の有無
掲載雑誌名
情報処理学会論文誌
40
12
開始ページ
4193
終了ページ
4200
出版年月日
1999-12-15
出版者
社団法人情報処理学会
ISSN
0387-5806
NCID
AN00116647
NAID
110002725167
本文言語
日本語
資料タイプ
学術雑誌論文
著者版フラグ
出版社版
権利情報
ここに掲載した著作物の利用に関する注意:本著作物の著作権は(社)情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 / 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から複製したものである
関連情報
isVersionOf:http://ci.nii.ac.jp/naid/110002725167
関連URL
旧URI
区分
hiroshima-cu