java - 如何获取第n个随机的 "nextInt"值？

Question

当使用类 java.util.Random 时，如何才能以更有效的方式(特别是在 O(1) 中)获得通过调用方法 nextInt() N 次获得的值？

例如，如果我构造一个具有特定种子值的随机对象，并且我想获得第 100,000 个“nextInt() 值”(即调用方法 nextInt() 100,000 次后获得的值)一个快速的方法，我能做到吗？

为简单起见，假设 JDK 版本为 1.7.06，因为可能需要知道类 Random 中某些私有(private)字段的确切值。说到这里，我发现以下字段与随机值的计算相关:

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

在探索了一些随机性之后，我发现随机值是使用线性同余生成器获得的。执行算法的实际方法是 next(int) 方法:

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

算法的相关行是获取下一个种子值的行:

nextseed = (oldseed * multiplier + addend) & mask;

那么，更具体地说，有没有一种方法可以概括这个公式以获得“第 n 个下一个种子”值？我在这里假设，在拥有它之后，我可以通过让变量“bits”为 32 来简单地获取第 n 个 int 值(方法 nextInt() 简单地调用 next(32) 并返回结果)。

提前致谢

PS:或许这个问题更适合mathexchange ？

Answer 1

您可以在 O(log N) 时间内完成。从 s(0) 开始，如果我们暂时忽略模数 (2⁴⁸)，我们可以看到(使用 m 和 a 作为 multiplier 和 addend 的简写)

s(1) = s(0) * m + a
s(2) = s(1) * m + a = s(0) * m² + (m + 1) * a
s(3) = s(2) * m + a = s(0) * m³ + (m² + m + 1) * a
...
s(N) = s(0) * m^N + (m^(N-1) + ... + m + 1) * a

现在，m^N (mod 2^48) 可以通过重复平方的模幂轻松地在 O(log N) 步中计算出来。

另一部分有点复杂。暂时再次忽略模数，几何和为

(m^N - 1) / (m - 1)

使计算此模 2^48 有点不平凡的是 m - 1 不是模数的互质。然而，由于

m = 0x5DEECE66DL

m-1 的最大公约数，模数为 4，(m-1)/4 有模逆 inv 模 2^48。让

c = (m^N - 1) (mod 4*2^48)

然后

(c / 4) * inv ≡ (m^N - 1) / (m - 1) (mod 2^48)

所以

• 计算 M ≡ m^N (mod 2^50)
• 计算inv

获得

s(N) ≡ s(0)*M + ((M - 1)/4)*inv*a (mod 2^48)