級数の再帰的集約による多倍長数の計算法とπの計算への応用
スポンサーリンク
概要
- 論文の詳細を見る
数学定数である円周率πの多数桁の計算法として,級数展開を用いる方法と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.
- 社団法人情報処理学会の論文
- 1999-12-15
社団法人情報処理学会 | 論文
- 5 テーブルトップインタフェース(実世界インタフェースの新たな展開)
- 内部ネットワーク監視を目的とした時間・論理・地理情報の統合的視覚化システム(コンピュータグラフィックス)
- 個人認証システム「あわせ絵」の安全性と利便性に関する評価実験(信頼性,ユビキタス社会を支えるコンピュータセキュリティ技術)
- おはじきインタフェース : ハイスピードカメラを用いた指を弾くジェスチャの認識(入力と表現(1),表現のためのインタフェース,および一般)
- 壁型ディスプレイとの非接触対話手法に関する研究(コミュニケーションと表現,表現のためのインタフェース,および一般)