夢みるアドセンス

情報系の雑記 :インターン行きたいので連絡ください hohoku55_at_yahoo.co.jp

速い円周率の計算方法

前提

プロコンの問題を解いていたら円周率の問題に当たった。素直にモンテカルロ法で解いたがタイムオーバー。

以下の方法がいいみたいのでメモ。

 

本題

ガウス=ルジャンドルのアルゴリズム - Wikipedia

4つの変数を反復して計算することにより円周率を算出する。

なんと、3往復するだけで19桁の円周率を計算できるっぽい。(モンテカルロ法だと3.14を出すだけでも100万粒必要)

 

補足

floatでは有効数字17桁しか表せないので、せっかく19桁出せても桁落ちしてしまう。

そこで、Decimal クラスを使って有効数字を拡張する必要がある。

参照:

decimal – 固定小数点数と浮動小数点数 - Python Module of the Week