C++で円周率(PI)を1億桁計算してみた Part1
修士課程でプログラムの最適化or高速化という題でプレゼンしてくれということで・・・
なんとなく円周率を計算するプログラムを作成&高速化(※学生レベルの範囲で)してみました!
そもそも1億の円周率の計算になにが必要かを簡単にまとめると、
・多倍長整数
・高速な円周率の計算式
・それなりに大きいメモリ
といったかんじですね。
なぜ円周率(3.141592…)の計算に浮動小数点型ではなく整数型なのかというと…
主な理由は「計算の高速化」ですね。浮動小数点演算は整数演算よりコストが大きい傾向があるからです。
それじゃあ多倍長整数をつかおう!
任意桁数あつかえる多倍長整数を1から作ってもいいのですが…高速な四則演算扱える形にするには骨が折れますので、 今回はライブラリを使用していきたいと思います。
有名な物には、
・GMP
・Boost.Multiprecision
・LibTomMath
などがありますね。
それぞれメモリ効率や演算アルゴリズム等が違い、一長一短があります。 次回Part2でどの多倍長整数をつかうか決めていきたいとおもいます。