■HOTEL [comic]

SFだな!
しかしなんという特装版。(印刷の版が特別、普通の製版じゃない、という意味)。
だからかお値段高め。
つまり、部数としてはすごいヒットにはなれないけれども、確実にこれだけの部数は売れる、という見込みがあっての判断だろう。

Boichi 作品集 HOTEL (モーニング KC)

• 作者: Boichi
• 出版社/メーカー: 講談社
• 発売: 2008-10-23
• ASIN: 4063727459
• メディア: コミック
• 

そしてここに、某ブログのレビューを見て買ってしまった者が一人。

……ヨハネの黙示録を指す場合は"Apocalypse"じゃなくてなんだっけ? "Revelation"、いや定冠詞を付けて"the Revelation"か。複数形の方は俗称なんだ。へー。

■Javaで指定範囲の乱数生成のlong版が欲しい、という話 [java]

ところで、Javaの乱数ではnextInt(int)というメソッドがあるので、intだと範囲指定して乱数を得ることができます。

けどもnextLong(long)というメソッドはないので、longだと範囲指定して乱数を得ることができません。

なにも考えなければ

nextLong() % n;

などとすると範囲を抑えれるのですけど、乱数としてちゃんとなるためには、もう少し頭を使ったほうがいいような気がします。

2008-11-10 - きしだのはてな

n が 2^m の形になっているならば、[0, Long.MAX_VALUE) を均等に分割するので、剰余を取ればいいです。

それ以外の時は、均等に分割されないので、小さい方が多くでてきます。
簡単のために MAX_VALUE が15 だとしましょう。乱数が 0 から 15 の範囲ででてきます。
これを 0 〜 2 の範囲に絞りたくて 3 で剰余を取ってしまうと

• 0 (0, 3, 6, 9, 12, 15)
• 1 (1, 4, 7, 10, 13)
• 2 (2, 6, 8, 11, 14)

となって、0 が 1つ多く(15の分)出現します。
なので、15が出たらこれを棄てたいです。

ということで話を元に戻すと、「MAX_VALUE 以下で n の倍数のうち最大のもの」未満を採用して、それ以上なら棄てます。

で、実際 java.util.Random#nextInt(int)の実装は、

    public int nextInt(int n) {
        if (n <= 0)
            throw new IllegalArgumentException("n must be positive");

        if ((n & -n) == n)  // i.e., n is a power of 2
            return (int)((n * (long)next(31)) >> 31);

        int bits, val;
        do {
            bits = next(31);
            val = bits % n;
        } while (bits - val + (n-1) < 0);
        return val;
    }

となっています。2のべき乗かどうかの判定や、上に書いた判定がちょっとだけトリッキーですが。

乱数で出てきた数(bits)から剰余(val)を引くと、bit 以下で最大の n の倍数が出ます。これに (n-1) を足して MAX_VALUE を超えて桁あふれ*1を起こすと負数になってしまう。
そうだったら値を棄てる。そうでなければ採用。

という具合になっています。

(追記) 注意! ここから先は大嘘です!! コメント参照のこと!!

……しかし。

しかしですね。

いざlong版をコードにしようとする段になると気がつくはずです。
nextLong(long) なるメソッドが欲しい時は、引数に指定するのは、Integer.MAX_VALUE より大きい値の場合なんですよね。
Javaでは言語仕様で、Integer と Long の MAX_VALUE は決められていて実装依存などないわけですから、

nextLong() して、n 以上の値がでてきたら棄てればいい

ってことになるじゃないですか。(Integer.MAX_VALUE より大きい場合、2倍しただけで Long.MAX_VALUE を超えてしまうのがほとんどだから)

public long nextLong(long n) {
    if (n <= 0)
        throw new IllegalArgumentException("n must be positive");

    if (n <= Integer.MAX_VALUE)
        return (long)nextInt((int)n);

    long val;
    do {
        val = nextLong();
    } while (val >= n);
    return val;
}

これでおしまいだ! (注:コンパイル通してません)

なるほど、nextLong(long)が無いわけだ。と思いました。

これで大丈夫かどうかは、元々の乱数の質に依るのでこれだけでは評価できないです。
特定の乱数生成方法と相性が悪い、とかあるかもしれませんが、それは元々の乱数の質がよくないという意味でもありますし……。

■もう少しだけ [java]

上で書いた nextLong(long) メソッドの中で、nextInt と nextLong の両方を使っている。
乱数生成の質が、nextInt の nextLong の両方で保証されてないといけないなぁ、と思った。

java.util.Random は実は long の大きさ(64bit長)を直接生成することはできない。nextLong() の実装は、int を2つ生成してビット結合するようになっている。
それだけではなく、

Random クラスによる nextLong メソッドの実装は、次と同等です。

 public long nextLong() {
   return ((long)next(32) << 32) + next(32);
 }

Random クラスは 48 ビットのみを含むシードを使用するため、このアルゴリズムは可能なすべての long 値の一部しか返しません

Random (Java Platform SE 6)

という但し書きが付いていたりする。

また、getDouble()なども、

[以前のバージョンの Java では、結果は次のように誤って計算されました。

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);

これでもある程度等しく思われますが、実際には、浮動小数点数の丸めでのバイアスのために大きなばらつきが生じるので、有効数字の下位ビットが 0 になることが 1 になることの 3 倍ありました。この程度のばらつきは実際には問題になりませんが、完全性を求めて修正を試みています。]

Random (Java Platform SE 6)

浮動小数点数の丸めの処理などは、1000speakers in Sendaiのために、資料を読んでいてちょうどでてきた部分(話す内容とは直接関係ないけど)なので、なるほどそういうことも気をつけないといけないのかぁ。

とかもね。