素数生成とグラボを使った多倍長演算
かなり昔の話ですが、素数を600億まで計算しました。アルゴリズムはエラトステネスの篩です。7以上の素数は30で割って1,7,11,13,17,19,23,29余るという性質を利用して8個にスレッドを分けています。この8個という数字、私のコンピュータのロジックコア数に相当するのでそれなりに効率よく処理を配分できていると思います。
タイムはintel Core i7 4770K 3.5~3.9GHzの8logic coreで、90秒でした。
篩処理は配列の要素を1に書き換えていくという方法を取っているのでgccのコンパイルの最適化オプションの-O3にかなり恩恵を受けています（タイムが半分ぐらいになった）
部活のi5のデスクトップで300億まで計算させてみたところ、こちらは60秒でした。（私のだと45秒だった）シングルロジックコアに割り当てられるキャッシュ量が部活のPCの方が多いのが原因かも知れません。
知っての通りC++のスタンダードライブラリに多倍長演算をサポートするものはありません。私はGMPという素晴らしいライブラリ（とにかく演算がめちゃくちゃ速い。FFTを使ってるんでしょううが8000万bit同士の演算が0.3秒で終わる）を使っていますが、それでももっと早くしたいなと思うことがあります。
掛け算とかの簡単な処理はグラボで処理させたほうが速いと思って調べてみてるところなのですが、積表を用いて演算する方式が取られているものがありました。コンピュータで演算させることを考えたらビット演算でやるのが良さそうなきがしますがどうでしょうね。
