如何获得第n个随机的“ nextInt”值？

Question

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

例如，如果我构造一个具有特定种子值的Random对象，并且想要快速获得第100,000个“ nextInt（）值”（即，调用方法nextInt（）100,000次后获得的值） ，我可以吗？

为简单起见，假定JDK的版本1.7.06是因为可能需要知道类Random中某些私有字段的确切值。可以这样说，我发现以下字段与随机值的计算有关：

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)