Haskell::OGR-nの探索(その2)

前回、PGR(n,m)の探索過程でm'<mであるm’が見つかった時点で、一旦全計算をキャンセルしてm’で計算をやり直したほうが計算量を削減できる、という仮定を立てたので本当にそうなのか実際にコードを書いてみた。

ogr2.hs

例外処理の類は使わずに、愚直にm(m’)を計算結果と一緒に持ちまわるようにしたので、ぱっと見やはり冗長というかうざったい感じのコードになった。HaskellらしくMaybeモナドなんかで途中の計算をつないでやるようなコードが書ければもっとシンプルになりそうな気はするが、その境地にはまだ程遠い。
ついでに、得られた計算結果の内鏡像解をタプルにまとめて返すようにしたので多少結果が見易くなっていると思う。

で、肝心の計算時間は、

% time ./ogr2 8
([0,1,4,9,15,22,32,34],[0,2,12,19,25,30,33,34])
3.651u 0.001s 0:03.65 100.0%    685+850k 0+0io 0pf+0w
% time ./ogr2 9
([0,1,5,12,25,27,35,41,44],[0,3,9,17,19,32,39,43,44])
56.130u 0.060s 0:56.19 100.0%   686+851k 0+0io 0pf+0w
% time ./ogr2 10
([0,1,6,10,23,26,34,41,53,55],[0,2,14,21,29,32,45,49,54,55])
647.876u 0.789s 10:50.60 99.7%  685+850k 0+0io 0pf+0w

となり、予想通り大幅な計算量の削減に成功している(前回のコードではOGR-9を求めるのにも2時間以上かかっていたし)。
とは言っても、OGR-11以降の計算はまだまだ相当な時間がかかりそう。distribute.netでチャレンジするのがOGR-22の探索だから、先は果てしないね。