たつをの ChangeLog : 2010-05-28

本屋さんでみかけたこんな本。

■竹内政明 / 名文どろぼう

人の心を打つ名文を書くには、名文を盗むことから始めよう。当代随一の名文家が、小林秀雄からスティーヴン・キング、落語、六法全書まで、秘密のネタ帳から古今東西の「名文」を絶妙に引用して綴る人生の四季。名文の芳香に浸る至福のひととき。

店頭でざっと目を通してみたんだけど、一言二言引用してそれについてコメントするという形式がなんだかブログっぽかったです。
というか、引用多めのブログってのがこういう随筆っぽいんだろうけど。

帯には「名文を引用して名文を書く技術」と。

下記の記事を読んで、10兆までの素数を現実的な時間で実際に生成する戦略を練ってみた。

- 10兆までの素数のリストを作ってみませんか？ (記者の眼：ITpro)
http://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/

とりあえず、ざくっと作った Perl スクリプト。
ものすごく時間はかかるけど（何ヵ月とか何年とか？）、とりあえず10兆までの素数が生成できる（はず）。

コード(gen-prime.pl):

#!/usr/bin/perl
use strict;
use warnings;
my $target = 10000000000000;
my $max_pn = sqrt($target);
my @pn;
for (my $n = 2; $n < $target; $n++) {
    for (my $i = 0; $i < @pn; $i++) {
        goto NOTPN if $n % $pn[$i] == 0;
        last if $n/$pn[$i] <= 2;
    }
    if ($n < $max_pn) {
        push @pn, $n;
    }
    print "$n\n";
  NOTPN:
}

プログラムに必要なメモリ容量についての考察。
10兆は10の13乗(10^13)。
ルートを取ると3162277.66...。
つまりプログラムは最大3162277までの素数を持てば良い。
実際の素数の数は約23万個。
23万個の素数をリストとして保持すれば良い。

実時間で終了させるには並列化が必要。
ということで、異なるマシン(CPU)で動かす前提のプログラム。

コード(gen-prime-p.pl):

#!/usr/bin/perl
use strict;
use warnings;
my $new_from = shift;
my $new_to = shift;
my $target = 10000000000000;
my $max_pn = sqrt($target);
my $flag;
my @pn;
for (my $n = 2; $n < $target; $n++) {
    for (my $i = 0; $i < @pn; $i++) {
        goto NOTPN if $n % $pn[$i] == 0;
        last if $n/$pn[$i] <= 2;
    }
    if ($n < $max_pn) {
        push @pn, $n;
    } elsif (not $flag) {
        $n = $new_from;
        $target = $new_to;
        $flag = 1;
    }
    print "$n\n";
  NOTPN:
}

ロジックは以下の通り：
(1) 3162277までの素数を得て数字リストとして保持する。
(2) その後はあらかじめ指定された3162277以降10兆までの分割領域に対して素数判明処理を行う。
(3) 素数と判明したらメモリに保持せずすぐに出力する。

実行例（例えば、それぞれ別マシンで動かす）:

./gen-prime-p.pl 3162277 1000000000
./gen-prime-p.pl 1000000001 2000000000
./gen-prime-p.pl 2000000001 3000000000
...

3162277（23万）の代わりに、分かりやすく 10^7 の値にしちゃってもいいかと。ざっくりと。
- Prime Counting Function -- from Wolfram MathWorld
http://mathworld.wolfram.com/PrimeCountingFunction.html

n (10^n)	素数の数
6	78498
7	664579

10兆までの全素数を単純にファイルに出力すると5Tバイトほどになるみたいなんだけど、素数そのものではなく差分を出力するようにすればだいぶ減らせる気がする。
どうせシーケンシャルにしかアクセスしないだろうから、ビット詰め詰めで良いしな。

素数判定アルゴリズムって、いろいろあるなあ→Wikipedia:素数判定。
前述のプログラム、確率的素数判定法でフィルタリングするともっと速くなりそう。深入りしすぎっぽいのでやらないけど。
（追記100530: 「Miller-Rabinは該当範囲について正確な判定が保証されてるアルゴリズムがある」ことを教えて頂きました。ありがとうございます。後日やってみます。 http://www.prefield.com/algorithm/math/isprime.html ）

ref.
- [を] Perlで素数判定と近隣素数の探索[2006-08-15-2]

今週の平日のランチ。
自分用メモ。

■5/24（月） パスタ

A971 でパスタランチ。


■5/25（火） お弁当

しんぷなお弁当でした。
冷凍御飯は容器のまま会社に持ってきてレンジであっためました。
夏はこの作戦がベストっぽいな。


■5/26（水） お弁当

妻が職場の近くまでやってきたので庭でいっしょにお弁当を食べました。
わいわい♪


■5/27（木） お弁当

ロールパンのサンドイッチのお弁当でした。


■5/28（金） 寿司

「梅の木」でお寿司でした。

今宵も夜の散歩。
今夜は満月だったそうな。
でも天気はあいにくの曇り。



空を見上げると一部明るい部分がありました。
雲の向こうにきっと満月があるはず。

ちなみに夜の散歩では恵比寿ガーデンプレイスのマクドナルドで100円コーヒーを頂くことが多いです。小さな贅沢！

今朝はばたばたしてたので、朝食は恵比寿にある「えびすむすび」でおにぎりを買いました。



ゑびすむすび 恵比寿本店
http://gourmet.livedoor.com/restaurant/404439/
http://tracks.seesaa.net/article/129050509.html
場所：東京都渋谷区恵比寿南1-2-8 雨宮ビル1F

この店、いろんな種類のおむすびがあります。
その場でにぎってもらえたりします。
数席あるので店内でささっと食べることも可能。