http://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/
10^13 までの素数をファイルに格納する問題。
5Tバイトか！すごいね。なんとかもっと最適化できないか考えたけど、元記事もかなり頑張ってる模様。
10^13あたりの素数分布を見てみると、だいたい300間隔くらいになってる。なので値自体じゃなくて前の素数との差を記録するようにすれば１つあたり２バイトあればいい。これで計算すると5Tバイトになる。 600Gバイト
もっと頑張るとすれば、素数は奇数なので間隔は常に偶数。したがって間隔/2を記録すればいい。こうするとほとんどが256以下になって1バイトで記録できる。
という訳で以下のようなフォーマットで、ある数以上ある数以下の素数を保存するファイルを考える。まず素数256個くらいをひと塊にしてブロックに分割する。8bit でOKなブロックは8bit で、そうじゃないブロックだけ16bitで記録すればほぼ1byte/1素数になる。10^13までだと合計2.5Tバイトくらい。追記：まちがえた。300Gバイトくらいのようだ。だいぶ減る
素数の数 Np ブロックのサイズ 256 ブロックの数 Nb=Np/256 +1 各ブロックの先頭素数の値 8bytes * Nb 各ブロック差分が8bit/16 bitフラグ 1byte *Nb 各ブロック先頭fseek位置 4 bytes*Nb 差分の値 1 or 2 bytes * 255 * Nb
例えば N より大きい最小の素数が欲しいとする。Nに応じてファイルを選びヘッダだけロード。ブロック先頭の素数の値のテーブルを二分法サーチで探して欲しいテーブル番号を求め、ファイルをシークしてそのブロックをロード、あとは加算していって計算する。
追記：素数間隔の分布はexp(-間隔/25.0)のような分布になっている。実際の10^13付近の分布を使ってエントロピーP Log Pを計算すると約 5.2 bit。したがってハフマン符号化を使って差分を記憶すれば平均1byte以下、~200Gb になる。しかしこの程度の圧縮のためにコード複雑にしてバグる確率増やすよりはハードを1.5倍使って単純にやったほうがいいだろな。
コード http://d.hatena.ne.jp/ita/00010418/p1
