GMP
このサイトでは、プログラム言語としてはC言語を使用し、演算には符号無し64bit整数(unsigned long long)を使用してきました。符号無し64bit整数では約1800京までの値を扱えますので、一般的な用途には十分なのですが、整数論では基本的に無限大までの値を扱いますので1800京では小さすぎます。まあ実際には無限大というのはコンピュータでは普通には取扱えないのですが、それでも整数論における値の範囲は大きなものですので64bitでは不足します。これまでは、それは仕方がないかと諦めていたのですが、やはりより大きな値も取扱って計算を行ってみたいと思い、GMPを使用することにしました。
GMPというのはGNUの開発してる多倍長演算ライブラリです。多倍長演算とは、配列を一つの数値と見立てることによって、固定長ではなく大きな数値を取扱える演算のことを言います。当然、メモリを多用するわけですが、昨今のメモリ事情ではそれはさして問題にはならないでしょう。
ということで、いくつかのプログラムをGMPを使用するように書き換えました。逆に、32bit整数(int)で十分なものについてはintに書き換えています。
GMPの限界
(2012/2/21追記)
GMPによる多倍長演算によって、これまでの固定長演算でのオーバーフローを回避できるようになりました。GMPではメモリが許す限りの巨大な数を扱えます。幸い、昨今メモリは急激に大容量化・低価格化していますので、容量が不足する心配はありません。ではどんどん大きな数を扱うようにできるかというと、今度はCPUの処理速度の問題に直面します。メモリはどんどん大容量化しているのですが、CPUは残念ながらどんどん高速化しているという状況ではありません。庶民に手が出るパソコン用のCPUは、単体コアとしての性能はほぼ頭打ちになってしまっていて、現在はコアを増やす方向で性能の向上を図っています。しかし、GMP自体はマルチコアを使用するようには出来ていませんから、いくらコアが増えてもそのままでは利用できないことになります。プログラム自体のマルチコア対応をする必要があります。
整数論の問題は計算が互いに独立しているものが多いですから、単純に探索区間を区切って複数プログラムを実行するだけでマルチコアに対応することが出来ます。とはいえ、それで得られる性能向上はせいぜい数倍から十数倍程度。整数論の本来扱う巨大な数に対しては、まだまだ無力としか言えません。
可能性の一つとしては、GPU(Graphics Processing Unit)があります。昨今の最新鋭のGPUではSP(シェーダプロセッサ)が千以上も搭載されています。汎用CPUコアとSPを直接比較することはナンセンスですが、桁違いのプロセッサ数は魅力ではあります。実際、GPUを用いたスーパーコンピュータもいくつか開発されていたりもします。庶民が手を出せるコンピュータパワーとしては、当面はGPUがその最速の座にあることは間違いないでしょう。
ではプログラムをGPUで処理するように書き直せばいいかというと、そう簡単には話は進みません。GPUプログラミングは並列処理ですから、従来の逐次処理型のプログラムとは全く違ったプログラムになります。全てプログラムを書き直すのは当然として、速度を出すためのチューニングもノウハウの塊だったりします。そのハードルは決して低いものではないでしょう。
長々と書いてきましたが、最後の解決策は結局アルゴリズムに行き当たるのでしょう。素数を求めるのにしても、単純な方法ではいくら時間があっても足りませんが、エラトステネスのふるいを使えばかなり高速化できます。そしてアルゴリズムの改良が行き着いた先には、おそらく紙と鉛筆の世界が待っているのだと思います。コンピュータによる計算を行っておいてなんですが、結局コンピュータでは有限の数しか扱えません。無限大に大きな値に対しては何も出来ないのです。いくら巨大な素数を求めたところで、それは数学的には大した意味はありません。それが可能かどうかはわかりませんが、全ての素数を導き出す公式が発見されるとするならば、それはコンピュータによってではなく、紙と鉛筆によるものだろうと予想されます。ではコンピュータによる計算は全くの無意味かというと、そういうわけでもないと思います。紙と鉛筆による証明に至るまでに、その道筋として、ヒントとして、コンピュータによる計算結果は利用されるのだと思います。
なんだかとりとめのない話になってしまいましたが、GMPによって精度の制限を外されることで、ようやく無限の大きなところに考えが及ぶようになって、ひとまず書き留めておきたいと思った次第であります。