mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

Ruby - 円周率計算(Spigotアルゴリズム)!

[ プログラミング, 数学 ] [ Ruby, 円周率 ]

こんばんは。

Ruby で円周率を計算してみました。 通常、コンピュータで円周率を計算するには多倍長整数の概念を使用しますが、今回は上の桁から順々に計算していく “Spigot” というアルゴリズムを利用しました。

Spigot アルゴリズムについての詳しいことは、

に記載されていますが、簡単に言うと、arctan(1) = π/4 であることを利用した計算方法です。 また、こちらのサイトにはC言語によるプログラムが掲載されています。

今回は、このC言語によるプログラムを Ruby に移植しただけです。 そして、C言語と Ruby の実行速度の違いも実感してみたかったのです。

記録

C言語によるプログラムは上記のリンク内を参照してください。

1.Ruby スクリプト作成

実行速度を測定するために benchmark を使用しています。 【PG-1】158Byte で 2400 桁計算できるC言語プログラムを Ruby に移植。

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
require 'benchmark'

base = 10000 # 基底
n    = 8400  # 計算項数

puts Benchmark.measure {

  # 分子初期化
  numerator = Array.new( 8401, base / 5 )

  out = 0 # 出力値
  8400.step( 1, -14 ) { |n|
    temp = 0            # 一時変数/繰り上がり
    ( n - 1 ).step( 1, -1 ) { |i|
      denom = 2  i - 1 # 分母
      temp = temp  i + numerator[i] * base
      numerator[i] = temp % denom
      temp /= denom
    }
    printf( "%04d", out + temp / base )
    out = temp % base
  }
  puts

}

# ヘッダキャプション
puts Benchmark::CAPTION

【PG-2】133 Byte で 15000 桁計算できるC言語プログラムを Ruby に移植。

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
require 'benchmark'

nume  = Array.new( 52514, 0 )
carry = 0
base  = 10000
first = 0

puts Benchmark.measure {

  52500.step( 1, -14 ) { |n|
    carry %= base
    digit = carry
    ( n - 1 ).step( 1, -1 ) { |i|
      denom = 2  i - 1;
      carry = carry  i + base * ( first != 0 ? nume[i] : ( base / 5 ) )
      nume[i] = carry % denom
      carry /= denom
    }
    first = printf("%04d", digit + carry / base)
  }
  puts

}

# ヘッダキャプション
puts Benchmark::CAPTION

2.実行結果

PG-1、PG-2 のC言語版とRuby版を実行して比較。 当然、C言語版で実行した結果とRuby版で実行した結果が同じなることは確認しております。 当方の非力な環境の場合、各プログラムを10回実行した平均は以下のようになりました。

PG C言語 Ruby
PG-1 0.0422 sec 0.7551 sec
PG-2 1.7332 sec 41.2474 sec
PG-1 に関しては 17.9倍、PG-2 に関しては 23.8倍 Ruby の方が時間がかかりました。

3.参考

参考までに、PG-2 で15,000桁計算した結果の先頭部分と末尾部分を掲載。

1
2
3
4
5
6
7
8
3141592653589793238462643383279502884197
1693993751058209749445923078164062862089
9862803482534211706798214808651328230664
7093844609550582231725359408128481117450
 :
5853131533718386826561786227363716975774
1830239860065914816164049449650117321313
8957470620884748023653710311508984279927


当然ながら、C言語の方が圧倒的に高速です。 Ruby が数値計算には向いていない、ということを実感しました。 やはり、テキスト処理に向いていると。

いつか、多倍長整数の概念を利用して本格的に円周率計算をしてみたいとも(少しだけ)思いました。 (Ruby か C か FORTRAN か その他 かで)

以上。

Comments