CUBは子供の白熊

Java SE 8 実践プログラミングの練習問題を解く

第8章 その他の Java 8 機能を理解する : 問題 4 : Random はゼロを生成するか?

Java プログラミング 関数型プログラミング

問題?

Math.nextDown(x)メソッドは、何らかのランダムな処理が x に正確に一致した場合に、x よりも次に小さな浮動小数点を返します。
これにより、返された数が x より小さいことが保証されます。

これは本当に保証できるのでしょうか?

ちょっと待った!

上の問題文は、本の文章そのままです。
どうゆう意味なのでしょう?

私は、最初

Math.nextDown(double)メソッドは、ランダムな要素があって引数より小さい値を返さないことがある。

という意味かと思ってました。

ところがMath.nextDown(double d)メソッドの実装は、NaN や { -\infty } でないとき

if (d == 0.0)
    return -Double.MIN_VALUE;
else if (d > 0.0)
    return Double.longBitsToDouble(Double.doubleToRawLongBits(d) - 1);
else /* d < 0.0 */
    return Double.longBitsToDouble(Double.doubleToRawLongBits(d) + 1);

となっています。
Double.doubleToRawLongBitsとDouble.longBitsToDoubleメソッドは、どちらもネイティブコードですが、ランダムな要素はありません。

じゃあ、この問題の意味は何でしょう。
途中は省略しますが、筆者は以下のような乱数クラスを実装していて

public class MyRandom {
    private java.util.Random generator = new Random();

    // 0.0 < 戻り値 < 1.0
    public double nextDouble() {
        double r = 1.0 - generator.nextDouble();
        if (r == 1.0) {
            r = Math.nextDown(r);
        }
        return r;
    }
}

はたと

r が 1 になる（即ちRandom.nextDouble()が 0 を返す）ことはあるんだろうか?

という疑問が湧いたのではないかと推理します（お前は探偵か?）。

本当の問題

java.util.RandomクラスのnextDoubleメソッドの戻り値の範囲は

0.0 ≦ x < 1.0

であり、ゼロを返す可能性はある。
しかし、この範囲には {2^{53} } 個の浮動小数点が存在するので、ゼロが返ってくる確率は極めて低いはずである。

java.util.RandomクラスのnextDoubleメソッドが百万回以内にゼロを返すようなシードの最小値を求めよ。
　← 結局Math.nextDownは関係ないじゃん

Randomの解説

java.util.Randomは、内部的にシード(long 有効桁数は48ビット)の数列を持っている。
シードは、次の漸化式で計算する。

{ s_{n+1} = ( s_n \cdot m + a ) \% N }
　{ m = 25214903917 }
　{ a = 11 }
　{ N = 2^{48} }

nextDoubleメソッドは、この2つのシード { s_n , s_{n+1} } の上位26ビットと上位27ビットを連結して53ビットの long 値を生成し、{ 2^{53} } で割った数を返す。

コンストラクタで与えられたシードを { s_0 } とすると、最初の乱数は { s_1 } の上位26ビットと { s_2 } 上位27ビットを連結した値になる。

解答

{ s_n = 0 } のとき { s_{n+1} = 11 } なので、このとき得られる乱数はゼロになる。

シードの漸化式の逆変換は

{ s_{n-1} = ( s_n - a ) \cdot v \% N }
　{ v = 246154705703781 }

となる。
あと、コンストラクタで与えられた引数がそのままシードになる訳ではなく、次のように変換される。

{ ( s \ \mathrm{XOR} \ m ) \% N }

つまり、ゼロから始めて逆の漸化式を二百万回たどり、上の XOR 演算を適用して最小値を見つければよい。

■ 逆の漸化式

private static final long m = 25214903917L;
private static final long mask = (1L << 48) - 1;

private static long prev(long s) {
    final long a = 11;
    final long v = 246154705703781L;

    return ((s - a) * v) & mask;
}

■ 最小値を見つける

OptionalLong seed =
    LongStream.iterate(prev(0), s -> prev(prev(s)))
    .limit(100_0000)
    .map(s -> (s ^ m) & mask)
    .min();
System.out.println("最小のシードは " + seed.getAsLong());
checkZero(seed.getAsLong());

■ 百万回以内にゼロが現れるかどうかをチェック

private boolean checkZero(long seed) {
    Random generator = new Random(seed);
    for (int tries = 1; tries <= 100_0000; tries++) {
        double r = 1.0 - generator.nextDouble();
        if (r == 1.0) {
            System.out.println(tries + "回目で乱数はゼロになった。");
            return true;
        }
    }
    System.out.println("乱数は一度もゼロにならなかった。");
    return false;
}

■ 答え

最小のシードは 881498
376050回目で乱数はゼロになった。