080907.jpg

16進数100万桁表示の円周率計算プログラムについて考える。実行速度は2秒以内としたい。効率のよい計算式と、FFTによる乗算で高速化にチャンレンジしたい。

ここのブログでも紹介している多倍長整数を利用するが、16進数に合わせて、1語の大きさを2進32ビット、つまり、16進8桁に直す。10進数と違って、除算ではビットシフト、剰余計算ではビットマスクだけでできるので、さらなる高速化が期待できそう。

整数一つの配列はこんなものになるだろう。オーバーフローが起きて、64ビット整数にしないといけない可能性もあるが。

  unsigned num[125000];

Chudnovsky)の公式は計算が速いようだが、確かめないとなんともいえない。

p11302.jpg

ネット上を調べたら、全ての桁をいっぺんに計算するのではなく、特定の桁だけを算出する方法もあるらしい。今回の用途に合致するかもしれない。

英文 Algorithm for Calculating Individual Hexadecimal Digits of Pi

なお、16進円周率の値一部はここにて確認できる。

Comments are closed.

Post Navigation