Problem 193 (途中経過)

今アップされている一番番号のデカい問題にふと挑戦してみた。

問題はこちら
http://projecteuler.net/index.php?section=problems&id=193

ガチの力ずく探索だとアホほど時間がかかるのでエラトステネスのふるい的なものを一定のセグメントごとに作るような実装をした。

一定のセグメントごと、というのは全ての数に対してふるいの表を構築するのは記憶領域の関係で不可能なためです。

アイディアを分かりやすく書くと

1,2,3,4,5,6,7,8,9であれば(non-square free numberをTとすると)4と8だけT,F,F,T,F,F,F,T,Tのような感じ
true,falseを格納するだけなのでサイズ数百のセグメントでもそんなにメモリは食わないはず...

Cなどのプリミティブな言語であればbit fieldを使えばさらに使用メモリをコンパクトにすることができそうですね。

もちろん、この表は不完全なのでTのものは飛ばして、Fのものだけ本当にsquare free numberかどうかを確かめます。

ざっくりつくって、10万までのsquare free numberを探索するのにかかった時間が22分。遅いかな〜もっと最適化できそうです。
2の50乗まで求めるにはいつまでかかるやら...
ちなみに2の50乗までのビットフィールドを構築しようとすると128テラバイト必要なようです。

追記:
改良したら10万までのsquare free numberの探索を8.9秒で終わらせられるところまでいきました。
といっても本当にsquare-freeかどうかを検証をする関数でさぼってn/2までやっていたところを平方根までに修正しただけです。
35万までで57秒。50万までで1分37秒。これ実は単なる素数の数え上げより遅かった。ショック...
ふるいを作るセグメントの大きさを調整することでふるいを作るオーバーヘッドを減らしたり調整してみてもあまり変わらず...
なにかアルゴリズムが間違っているのか。
やはり数が大きくなるにつれsqfree?関数の処理が重くなりますね〜...
macbook proがデュアルコアなのでマルチスレッドの処理を入れてみるか?
しかしrubyのスレッドはネイティブスレッドではないのでオーバーヘッドが大きいのではという懸念もありますね。
呼び出しのオーバーヘッドはあまり問題にならないかもだけどコンテキストスイッチのオーバーヘッドがどれくらいかによりますな〜

追記2:
今試してみたら残念なことにふるいの表を使わない力づくの方法の方が早かった(1〜25万, 1〜50万とも)
4の倍数, 9の倍数, 16の倍数, 25の倍数と穴が多いためふるいで候補をそこまで減らすことができないのが原因ではないかと思われる。
これはおそらく何らかの数学的性質を使ったアルゴリズムのブレイクスルーがない限り分散コンピューティングでもしないと人間が起きて寝るまでの時間では解くことはできないのではないかと思う。