id:Nabetani:20041014:p1 から始まる、id:Nabetani:20050226:p4 の続き。
だいぶ高速化したので、n=6 の場合も計算できるようになった。
折角なので秒数とともに書いておくと：
- n=1 : 1個 / 0秒
- n=2 : 5個 / 0秒
- n=3 : 47個 / 0.016秒
- n=4 : 733個 / 0.44秒
- n=5 : 15907個 / 24秒
- n=6 : 443825個 / 2700秒 = 45分
となった。
n=2〜5 は、個数が全て素数という意外な展開だったんだが、n=6 では一見してわかるとおり、合成数となった。何となく残念。
素因数分解の結果は
443825 = 5*5*41*433
である。
n=7 は、個数は1500万程度、計算に要する時間は一週間前後か。無理。
とはいえ、まだまだ高速化の余地はある。
ところで。
http://blog.livedoor.jp/mind_extream/archives/15356274.html
に、
この問題はデータ構造をどうするかが鍵を握ると思う。
とあったので、実装時の話をちょっと書いておく。
書いていて面倒だったのは、同じ式を同じ式だと見抜く部分である。
a-b/c+d と a+(d-b/c) が同じかどうか。
そこで、弱い分数式計算クラスを作った。弱いというのは、約分ができなかったりする（変数が一回ずつしか登場しないので、約分できる必要がない）ことを指す。
分数式は、多項式のペア。多項式は項から係数へのhash。項は、変数の集合。
というような実装を選んだので、
分数式として持つ以上、a/(b/c+d) のような式も多項式のペアに展開して ac/(b+cd) のようにする必要がある。これが面倒だった。
で。できあがった分数式は、正規化（分母の最初の項がマイナスなら、分母と分子に -1 をかけるとか、いろいろ）してから文字列にシリアライズする。
もちろん、その正規化をちゃんとやるのもちょっと面倒。
シリアライズした結果を「発見済み分数式集合」にどんどん入れていき、列挙が終了したらその集合の要素数を調べればよい。
それと。
知人でも何でもない方がここを発見しておもしろがっている記事を読むのは、いつもうれしい。
