Project Euler - Problem 229 を強引に素早く解こう

問題文はこちら。

• http://projecteuler.net/problem=229
• http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20229

内容は、2*10^9 までの整数のうち、以下の 4 つの式を成立させられる n はいくつあるかというもの。

• n = a₁² +   b₁²
• n = a₂² + 2 b₂²
• n = a₃² + 3 b₃²
• n = a₇² + 7 b₇²

この問題はとても簡単に力任せで解く事が可能で、2*10^9 個の要素を持つフラグテーブルを作って、a と b を網羅し対応する n のフラグを立て、全てのフラグが立っているものをカウントするだけで済んでしまう。

$ g++ -std=c++11 -O4 229.cpp; time ./a.out
********

real    1m0.754s
user    1m0.140s
sys     0m0.516s

ちなみに上記の計測に使った CPU は Core i7-4930K で、以前 Core2Duo E8500 で計測した時でも 4 分で処理出来ていた。

高速化してみた

先程のプログラムは、2*10^9 バイトのおよそ 2GB という広い領域を持つフラグテーブルを、a と b によって塗り潰すものとなっており、参照の局所性というものを全く考えていない。そこでそのテーブルを、キャッシュメモリに乗るだけの区間に分けて処理し、ついでに OpenMP を使いマルチスレッドで動作するように書き直した。

すると OpenMP を使わずシングルスレッドで動かした場合でも

$ g++ -std=c++11 -Wall -O4 229-segmented.cpp; time ./a.out 
229-segmented.cpp:44:0: 警告: #pragma omp parallel を無視します [-Wunknown-pragmas]
********

real    0m13.339s
user    0m13.328s
sys     0m0.000s

と、如何に DRAM が遅くキャッシュメモリが速いのかが分かる結果となった。 そして更に OpenMP を用いてマルチスレッドで処理させると

$ g++ -std=c++11 -Wall -O4 -fopenmp 229-segmented.cpp; time ./a.out
********

real    0m1.648s
user    0m19.632s
sys     0m0.004s

このようになる。というわけで

• 参照の局所性を考えるのおすすめ
• OpenMP を使ったお手軽な並列処理おすすめ

でした。