d.y.d.

23:09 09/05/28

BOOK OFF

ここのところ、BOOK OFF のタメシ買いセットというのを大量に試し買いしてみてました。各セット2つずつ計90冊。「どう見てもただの在庫整理だろ」というような意見もあるかと思うのですが、個人的には、これ、すごい面白そうだなーと思ったので。

何かの拍子に「自分が読んだことない作品を読んでみよう！」と思っても、自分で探してみて買うのだと、どうしても、どこか自分が好きそうな方向に偏ってセンサーが反応してしまうんですよね、結局。逆にこういう完全に強制他人のチョイスの下でやってくる本なら、そういうこともなく意外な作品に出会えるのではないか、とか。あと、アマゾン完全ランダム買いとかと違って、蔵出しに回されるくらい世の中に出回っている程度には売れているのが来るはずで、本気の大外れが大集合ということにもならないだろう、と。というわけで、具体的に来たシリーズ一覧↓↓

「DEATH NOTE」「冒険王ビィト」「エア・ギア」「DEAR BOYS ACT2」「School Rumble」「ななか6/17」「MAR」「あいこら」「新撰組異聞ピースメーカー」「PAPUWA」「ライフ」「神風怪盗ジャンヌ」「禁断の恋でいこう」「マリア様がみてる」「ガッチャガチャ」「カードの王様」「V・B・ローズ」「グッドモーニング・コール」「コスメの魔法」「ホットギミック」「GIRLSブラボー」「最終兵器彼女」「キャプテン翼 ROAD TO 2002」「天上天下」「GUNSLINGER GIRL」「天才柳沢教授の生活」「無限の住人」「バガボンド」「tactics」「リヴァイアサン」

色変えたのが自分が読んだことがあったもの。悪くない回避率だったと思う。中身も全体的に面白いのが多かったので満足です。

23:59 09/05/26

前回の

前回の Random の話について succeed さん、shiro さんからコメントいただいたのでまとめ追記あります。みんな読むべし。

論文

読んだ論文という話題を見て、そういえば、ここ一年半くらいに読んだPDFは JabRef に突っ込んであるので一覧が出せるなーと思ってやってみました → jabref20090526.html。

読んだけどあまりにもどうでもよかったのは登録してなかったり、逆に [あとで読む] 状態で放置してあるもの（Discrepancy Method の本とか力尽きてます）が混ざってたり、あとは、読んだのは昔だけれど再読したり辞書的に引くために入れてある論文も何本かあったりしてますが、多分だいたいこんな感じです。

…ただ、"研究者として"は論文を読んでいない気がするなあ。自分に近い分野の動向をチェックだとか、今対象としている問題領域に今までどういうアプローチがあってどこまで明らかになっているかのサーベイだとか、そういうのはよくわからない…いや、やることはやりますけど…。 Landreaall (14) が自分の研究にはきっと未来永劫影響せず純粋に読み物として読んで「おもしれー！」と終わるというのと全く同じレベルで、八割方の論文は、小説や漫画を読むのと完全に同じ感覚の趣味です。お気に入りの著者の新作が出たから読む！みたいな雰囲気で選んでる気がする。学会の Proceedings って年１回刊行されるアンソロジーでしょう？

22:06 09/05/23

歩いた

溝の口まで。適当に南西方向に軽めにと言うことで電通大あたりゴールにしようと思って、何も考えず渋谷に向かって歩いたあと渋谷で地図チェックしたら向かうべきは新宿だったことが判明。めんどくさいのでそのまままっすぐ歩いてとりあえず神奈川に入ってみた。

最初の乱数

java.util.Random の nextDouble が返す最初の乱数が偏ってる [1] [2] っていう話、どういう理由でこういう現象が起きるんだろう、というのが気になってだいぶ前に一瞬調べてみたのをなんとなくまとめておきます。いや、別に大したことはないんですが。

java.util.Random の中身の、関係ある部分を抜粋すると、こう。

class Random {
    private final long seed; // 実際は、スレッドセーフにするために AtomicLong を使って実装されている

    // java.util.Random の乱数は48ビットの線形合同法
    private final static long multiplier = 0x5DEECE66DL;
    private final static long addend = 0xBL;
    private final static long mask = (1L << 48) - 1;

    public void setSeed(long seed) {
        this.seed = (seed ^ multiplier) & mask;
    }

    // bitsビットのランダムな整数を一つ取り出す
    // 実装は「seed を1ステップ進めて、上位bitsビットを返す」
    protected int next(int bits) {
        this.seed = (this.seed * multiplier + addend) & mask;
        return (int)(this.seed >>> (48 - bits));
    }

    // 53ビットの整数を作って 1<53 で割ることで0以上1未満の乱数を作る
    // 53ビット整数の作り方は、「next(26)を上位26ビット、next(27)を下位27ビットにする」
    public double nextDouble() {
        return (((long)(next(26)) << 27) + next(27))
             / (double)(1L << 53);
    }
}

next(26) が上位ビットなので、nextDouble の返す値のだいたいの大きさはこちらで決まります。 next(27) の影響は1億分の1くらい。つまり「最初の nextDouble が偏る == 最初の next (の上位ビット)が偏る」。

では、なぜ最初の next (の上位ビット)が偏るのか。リンクさせていただいた２つの記事ではいずれも、シードを 0 ～ 1024 辺りの、 10ビットの範囲で変化させて実験していました。このシードの偏りが、そのまま最初の乱数の偏りに結びついてしまっています。最初に setSeed(S) したとすると、最初の next は

((S ^ multiplier) * multiplier + addend) & mask

の上位ビットを切り出してきます。大雑把に考えて、 multiplier は 32 ビットの値なので、たとえば S が 0 ～ 1024 の10ビットの値だと、掛け算しても下42ビットしか変化しない。つまり上6ビットは固定→偏る、という。（繰り上がり等考えるとそこまで単純でもないですが、まあ、だいたい。）現象としては「与えるシードの上位ビットが同じだと返ってくる最初の乱数の上位ビットもだいたい同じ」なので、シードを大きくしても、範囲がせまいと、たとえば 65536～66536 や 16777216～16778216 の範囲で変化させると特定のゾーンに固まります。ふーむ。

※ 追記 ※

では、こういった問題にどう対処するべきか、と、id:succeed さんからのお便りです。なるほどー。自分で考えてても実際じゃあどうあるべきだったのか（Random の実装側が setSeedでもう一歩進める実装 / nextDoubleの上と下の取り方を逆転する実装か何かで散らばらせる / 「seedとはそういうもの」なので使う側が考えるべき）なのかさっぱりわからなかったので助かります。（実装詳細を隠蔽したいという前提で）ライブラリとして提供する側として考えると、かぶらないと保証できる乱数系列を複数生成するようなAPIを用意することになるのかな。

※ 追々記 ※

shiro さんからもコメントいただきました。Scheme の SRFI 27 にはそういうAPIが定められているとのこと。Pre-Finalization Discussion Archive の "streams and substreams" から "changes to the design" あたりのスレッドにこの関数についての議論があって、確かに、独立な乱数列を複数生成するシードを適切に選ぶにはいろいときちんと考えないといけなくて云々、といった経緯が語られていました。なるほどどどー。

21:57 09/05/05

PPIM

Pure Prolog Implementation Marathon に参加してました。その場での成果物→ kelog2.zip。

・ 42.195KBコード書くを目標にものすごい勢いで適当なコードの量産を試みる → 4分の1くらい経った時点で5KBしかないこれは無理だなー。・普通の実装戦略ではなく変なことをやろうと思って、何か無理矢理グラウンド化してSATソルバに持ち込んで解かせてみようと2時間くらい考える → ボトムアップ戦略のできそこないみたいな使い方しか思いつかないこれは無理だなー。 SMTとかそっち系のものの実装を事前に調べとけばよかった。・なにも完成させないではつまらないので普通のトップダウン戦略で書いてみる方向にヒヨる → いちおうできた・ m0h1canさんによるWAMの解説が面白かったので似非WAMっぽくなんかマシンっぽくしてみよう → どんな巨大なルールも5命令で書けてしまう大変大味な命令セットが完成。・ここから段階的に改善してってもっと低レベルっぽくしよう… → と思ったけど時間切れ。

…という感じでした。5命令というのは「1: ホーン節をメモリにロードする命令」「2: バックトラック用に現在の状態覚える命令」「3: ロードしたホーン節のheadを現在のゴールスタックの先頭と単一化する命令」「4: ロードしたホーン節のtailを現在のゴールスタックに全部積む命令」「5: ゴールスタックの先頭にあるサブゴールを実行」で、1, 3, 4, 5 をちゃんとマジメに細かく分けてコードに落としつつ 2 をちゃんと樹状スタック管理すればWAMっぽくなると期待したい。面白かったのでちょこちょこ続きの実装してみようかな。

Derive Your Dreams