円周率10億桁を計算する #2


と、いうわけで、検証。
macroxue / const-piLink のzipファイルを入手する。
件の Hanhong Xue 氏の円周率計算プログラム、新しめのバージョンである。
nitobe@debian64:~$ wget https://github.com/macroxue/const-pi/archive/master.zipLink 
     :
     :
nitobe@debian64:~$ unzip master.zip
Archive:  master.zip
8232a2005009a1d3f33c68c2e7e1054d12e8ae6d
   creating: const-pi-master/
  inflating: const-pi-master/Args.h  
  inflating: const-pi-master/README.md  
  inflating: const-pi-master/const.cpp  
  inflating: const-pi-master/fac.c   
  inflating: const-pi-master/fac.h   
  inflating: const-pi-master/makefile  
  inflating: const-pi-master/my.c    
  inflating: const-pi-master/my.h    
nitobe@debian64:~$ 
10億桁の計算はできるのだが、2進10進変換で落ちる。たぶんメモリ不足だ。フォーマットも非常に凝ったものだが、扱いにくいので、gmpのオリジナル出力関数を使用する。my.c の my_out_str関数もコメントアウトして亡き者とする。Xue さんごめんなさい。
nitobe@debian64:~/const-pi-master$ diff const.cpp ../const_new/const-pi-master/const.cpp
90c90,91
<             my_out_str(out_fp, 10, digits+2, result);
---
> //            my_out_str(out_fp, 10, digits+2, result);
>             mpf_out_str(out_fp, 10, digits+2+2, result);
nitobe@debian64:~/const-pi-master$ diff my.c ../const_new/const-pi-master/my.c
367a368
> /*
434a436
> */
ささ、早速計算してみよう。
nitobe@debian64:~/const_new/const-pi-master$ time ./const pi -d1000000000 -o pi1G.txt
Calculation started at Sat Dec 15 12:47:03 2012

1000000000 digits of pi using Chudnovsky formula, 70513670 terms.
        initialization : 17.720 s
      binary splitting : 4126.380 s                
              division : 771.880 s
           square root : 115.470 s
        multiplication : 76.110 s
-----------------------------------
         calculation : 5108.710 s
              output : 2377.740 s

           user time : 7453.158 s
            sys time : 33.330 s
        memory usage : 7567424 KB

Calculation finished at Sat Dec 15 14:51:49 2012

real124m46.183s
user124m13.158s
sys0m33.342s
nitobe@debian64:~/const_new/const-pi-master$ time ./format.sed pi1G.txt >pi1g.txt

real2m36.393s
user2m34.690s
sys0m1.696s
nitobe@debian64:~/const_new/const-pi-master$ time ./const pi-rama -d1000000000 -o pi1G-rama.txt
Calculation started at Sat Dec 15 15:30:39 2012

1000000000 digits of pi using Ramanujan formula, 125273397 terms.
        initialization : 15.850 s
      binary splitting : 6177.520 s                
              division : 790.000 s
           square root : 119.790 s
        multiplication : 78.360 s
-----------------------------------
         calculation : 7182.620 s
              output : 2432.270 s

           user time : 9572.514 s
            sys time : 42.387 s
        memory usage : 9204968 KB

Calculation finished at Sat Dec 15 18:10:53 2012

real160m14.581s
user159m32.518s
sys0m42.423s
nitobe@debian64:~/const_new/const-pi-master$ time ./format.sed pi1G-rama.txt >pi1g-rama.txt

real2m41.404s
user2m39.262s
sys0m2.088s
nitobe@debian64:~/const_new/const-pi-master$ time ./const pi-agm -d1000000000 -o pi1G-agm.txt
Calculation started at Sat Dec 15 18:35:39 2012

1000000000 digits of pi using AGM.
        initialization :  0.000 s
           iteration 1 : 178.290 s
           iteration 2 : 278.120 s
           iteration 3 : 278.280 s
           iteration 4 : 278.630 s
           iteration 5 : 277.700 s
           iteration 6 : 279.700 s
           iteration 7 : 279.920 s
           iteration 8 : 277.230 s
           iteration 9 : 280.430 s
          iteration 10 : 281.650 s
          iteration 11 : 280.880 s
          iteration 12 : 280.740 s
          iteration 13 : 280.720 s
          iteration 14 : 283.320 s
          iteration 15 : 280.400 s
          iteration 16 : 280.400 s
          iteration 17 : 281.510 s
          iteration 18 : 280.970 s
          iteration 19 : 280.330 s
          iteration 20 : 280.230 s
          iteration 21 : 280.000 s
          iteration 22 : 280.570 s
          iteration 23 : 280.520 s
          iteration 24 : 278.800 s
          iteration 25 : 276.900 s
          iteration 26 : 275.450 s
          iteration 27 : 278.470 s
          iteration 28 : 291.890 s
          iteration 29 : 255.460 s
          iteration 30 : 225.770 s
              division : 731.840 s
-----------------------------------
         calculation : 8955.190 s
              output : 2350.680 s

           user time : 11110.358 s
            sys time : 195.520 s
        memory usage : 6256556 KB

Calculation finished at Sat Dec 15 21:44:05 2012

real188m25.535s
user185m10.362s
sys3m15.628s
nitobe@debian64:~/const_new/const-pi-master$ time ./format.sed pi1G-agm.txt >pi1g-agm.txt

real2m36.758s
user2m34.898s
sys0m1.868s
nitobe@debian64:~/const_new/const-pi-master$
ご覧のように、Chudnovskyの式、Ramanujanの式、AGMの三種類のアルゴリズムで10億桁を計算してみた。
さて、いよいよ比較なのだが、巨大な一行野郎を、sedで100桁/行フォーマットにした理由が、ここでわかっていただけると思う。diff が使いたかったんだな
nitobe@debian64:~/const_new/const-pi-master$ time diff pi1g.txt pi1g-rama.txt
1,7c1,8
< Calculation started at Sat Dec 15 12:47:03 2012
< 1000000000 digits of pi using Chudnovsky formula, 70513670 terms.
<         initialization : 17.720 s
<       binary splitting : 4126.380 s
<               division : 771.880 s
<            square root : 115.470 s
<         multiplication : 76.110 s
---
> Calculation started at Sat Dec 15 15:33.
> 9 2012
> 1000000000 digits of pi using Ramanujan formula, 125273397 terms.
>         initialization : 15.850 s
>       binary splitting : 6177.520 s
>               division : 790.000 s
>            square root : 119.790 s
>         multiplication : 78.360 s
9c10
<          calculation : 5108.710 s
---
>          calculation : 7182.620 s
10000013,10000017c10000014,10000018
<               output : 2377.740 s
<            user time : 7453.158 s
<             sys time : 33.330 s
<         memory usage : 7567424 KB
< Calculation finished at Sat Dec 15 14:51:49 2012
---
>               output : 2432.270 s
>            user time : 9572.514 s
>             sys time : 42.387 s
>         memory usage : 9204968 KB
> Calculation finished at Sat Dec 15 18:10:53 2012

real0m34.410s
user0m9.657s
sys0m4.880s
nitobe@debian64:~/const_new/const-pi-master$ time diff pi1g.txt pi1g-agm.txt
1,7c1,35
< Calculation started at Sat Dec 15 12:47:03 2012
< 1000000000 digits of pi using Chudnovsky formula, 70513670 terms.
<         initialization : 17.720 s
<       binary splitting : 4126.380 s
<               division : 771.880 s
<            square root : 115.470 s
<         multiplication : 76.110 s
---
> Calculation started at Sat Dec 15 18:35:39 2012
> 1000000000 digits of pi using AGM.
>         initialization :  0.000 s
>            iteration 1 : 178.290 s
>            iteration 2 : 278.120 s
>            iteration 3 : 278.280 s
>            iteration 4 : 278.630 s
>            iteration 5 : 277.700 s
>            iteration 6 : 279.700 s
>            iteration 7 : 279.920 s
>            iteration 8 : 277.230 s
>            iteration 9 : 280.430 s
>           iteration 10 : 281.650 s
>           iteration 11 : 280.880 s
>           iteration 12 : 280.740 s
>           iteration 13 : 280.720 s
>           iteration 14 : 283.320 s
>           iteration 15 : 280.400 s
>           iteration 16 : 280.400 s
>           iteration 17 : 281.510 s
>           iteration 18 : 280.970 s
>           iteration 19 : 283.
> 30 s
>           iteration 20 : 280.230 s
>           iteration 21 : 280.000 s
>           iteration 22 : 280.570 s
>           iteration 23 : 280.520 s
>           iteration 24 : 278.800 s
>           iteration 25 : 276.900 s
>           iteration 26 : 275.450 s
>           iteration 27 : 278.470 s
>           iteration 28 : 291.890 s
>           iteration 29 : 255.460 s
>           iteration 30 : 225.770 s
>               division : 731.840 s
9c37
<          calculation : 5108.710 s
---
>          calculation : 8955.190 s
10000013,10000017c10000041,10000046
<               output : 2377.740 s
<            user time : 7453.158 s
<             sys time : 33.330 s
<         memory usage : 7567424 KB
< Calculation finished at Sat Dec 15 14:51:49 2012
---
>               output : 2350.680 s
>            user time : 11113.
> 58 s
>             sys time : 195.520 s
>         memory usage : 6256556 KB
> Calculation finished at Sat Dec 15 21:44:05 2012

real0m23.249s
user0m9.133s
sys0m3.004s
nitobe@debian64:~/const_new/const-pi-master$ time diff pi1g.txt ../../pi/pi1g.txt
1,9d0
< Calculation started at Sat Dec 15 12:47:03 2012
< 1000000000 digits of pi using Chudnovsky formula, 70513670 terms.
<         initialization : 17.720 s
<       binary splitting : 4126.380 s
<               division : 771.880 s
<            square root : 115.470 s
<         multiplication : 76.110 s
< -----------------------------------
<          calculation : 5108.710 s
10000011,10000017c10000002
< 644
< 
<               output : 2377.740 s
<            user time : 7453.158 s
<             sys time : 33.330 s
<         memory usage : 7567424 KB
< Calculation finished at Sat Dec 15 14:51:49 2012
---
> 64388312

real0m23.689s
user0m9.213s
sys0m3.012s
nitobe@debian64:~/const_new/const-pi-master$
恐るべしdiff。1GByteのファイルを30秒前後で比較している。

参考までにHanhong Xue 氏のファイルと、すずきひろのぶ氏のファイルの頭とケツをお見せしよう。
Chudnovsky formula by Hanhong Xue
       1 Calculation started at Sat Dec 15 12:47:03 2012
       2 1000000000 digits of pi using Chudnovsky formula, 70513670 terms.
       3         initialization : 17.720 s
       4       binary splitting : 4126.380 s
       5               division : 771.880 s
       6            square root : 115.470 s
       7         multiplication : 76.110 s
       8 -----------------------------------
       9          calculation : 5108.710 s
      10 3.
      11 1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
      12 8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196
      13 4428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273
     :
     :
10000009 4219776753871319682188195635848934815504410194647387557034502943416861599324354199731814355060392734
10000010 6434543524276655356743570219396394581990548327874671398682093196353628204612755715171395115275045519
10000011 644
10000012 
10000013               output : 2377.740 s
10000014            user time : 7453.158 s
10000015             sys time : 33.330 s
10000016         memory usage : 7567424 KB
10000017 Calculation finished at Sat Dec 15 14:51:49 2012

AGM by Hironobu Suzuki
       1 3.
       2 1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
       3 8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196
       4 4428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273
     :
     :
10000000 4219776753871319682188195635848934815504410194647387557034502943416861599324354199731814355060392734
10000001 6434543524276655356743570219396394581990548327874671398682093196353628204612755715171395115275045519
10000002 64388312
xue 氏のファイルは、頭とケツに諸々の情報が入っているので9行ずれている。

4種類の実装で10億2桁目まで同一であることを確認しました。

注:実行時間は全く当てにならない。このPC上では、seti@home Link on BOINCLink 及び、World Community GridLink on BOINC がリソースの75%を占有している。

ぎゃぼ!sed スクリプトが、時間の文字列”0.3”で悪さをしている!正しい挙動だ。ま、数値の比較には影響しないので見なかったことにしておこう。

ご希望の方には円周率10億桁のテキストファイルをメールで送付させていただきます。1.01GByteですけど...何か...問題でも?。

 

— posted by nitobe at 06:42 pm   commentComment [0] 

コメントをどうぞ。 名前(ペンネーム)と画像認証のひらがな4文字は必須で、ウェブサイトURLはオプションです。

ウェブサイト (U):

タグは使えません。http://・・・ は自動的にリンク表示となります

:) :D 8-) ;-) :P :E :o :( (TT) ):T (--) (++!) ?;w) (-o-) (**!) ;v) f(--; :B l_P~ (QQ) ふね do くもり

     

[X] [Top ↑]

T: Y: ALL: Online:
ThemeSwitch
  • Basic
Created in 1.0819 sec.
prev
2024.5
next
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
 
strawberry-linux geigercounter Ver.2
Sibasaki, Cyofu City, Tokyo, JAPAN
blogBar