方式によるπ計算量の比較

   2010/07/17 早大 & 東京工芸大学 & 海洋研究開発機構 後 保範 ( Ushiro Yasunori )
   2010/08/04 改訂(公式等にリンク追加)

1. 比較の前提

 (1) ラマヌジャン公式 及びArctan(1/x)公式DRM(分割有理数化法)を使用
   DRMはバイナリースピリット法他別の呼び方もある。

 (2) 通分処理における共通因数削減 はDRMに適用可能(x等のベキ項はDRMに含む)
   そのため、AGMには本処理は適用できない。

 (3) 全桁一致の検証は異なる2種類の公式で計算し、最終桁は16進特定桁計算で検証
   最終桁(通常16進32桁)検証でも、計算自体の検証は可能。ただ、最終段でDiskI/O
   に誤りがあった場合に、得られた結果の一部だけ誤る可能性は否定できない。
   このような誤り(最終数百万桁は一致、途中数百万桁不一致)の経験あり。

 (4) 検証を含む処理量の計算は下記を使用
  (a) 全桁(2公式計算)検証
    ラマヌジャン:正計算(ラマヌジャンNO.1)、検証計算(ラマヌジャンNO.2)
    Arctan(1/x) :正計算(Arctan公式)、検証計算(別のArctan公式)
           検証計算は正計算と一部Acctan(1/x)が一致し係数だけ異なるものを利用
           これにより、検証計算は正計算の約半分で計算可能
    AGM(2,4次公式):正計算(AGM公式)、検証計算(別のAGM公式)
            通常、検証計算が多少余分にかかるが、同等とした
  (b) 最終桁検証
    16進数(2進数)に限り可能で最終桁(16進32桁)を特定桁計算結果と検証
    16進特定桁計算時間は正計算時間に比較し無視できるほど少ないため含まず。
  (c) メモリ内とI/O付きの処理量
    メモリ内: 処理量 = 計算量+0.1*(通信量&I/O量)
    I/O付き : 処理量 = 計算量+1.0*(通信量&I/O量)

 (5) 表1.の基準数値
   計算量、通信量&I/O量、検証を含む処理量共に、最小なものを1.0として正規化した指標

2. π計算量の比較

表1. 1〜10兆桁計算での比較
計算公式 適用アルゴリズム π計算処理量 検証を含む処理量
2段階FMT 分割乗算 共通因数
削減
計算量 通信量
&I/O量
全桁(2公式計算) 最終桁
メモリ内 I/O付き I/O付き
ラマヌジャンNO.1
(チュドノフスキー)
1.0 1.0 1.5 2.7 1.0注1)
× 2.5 6.0 4.2 12 4.3
× × 2.8 15 5.8 24 8.9
× × × 3.3 45 11 65 24
ラマヌジャンNO.2
(検証用)
1.7 1.7 --- --- ---
× 4.3 10 --- --- ---
× × 4.7 26 --- --- ---
× × × 5.7 77 --- --- ---
Arctan(1/x) 3.0 3.0 2.5 4.5注4) 3.0
× 7.5 18 7.0 19 13
× × 8.3 54 10 47
25注3)
31
× × × 10 135 18 109 73
AGM(2,4次公式) --- 7.5 18 9.3 26 13
× --- 8.3 54 14 62 31
× × --- 10 135 23注2) 145 73

  注1): 2009年12月(2.7兆桁、ファブリス・ベラール(フランス))
  注2): 2009年8月(2.58兆桁、高橋(筑波大))
      1999年(2061億桁、金田、高橋(共に東大))
  注3): 2002年11月(1.2兆桁、金田(東大)、後(日立)他)
       1TBメモリで、I/Oとメモリ内の中間の処理量=25
  注4): 今回の計画