如何获得第N个随机“NextInt”值？

Question

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

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;

Answer 1

您可以在o（log N)时间内完成此操作。从S(0)开始，如果我们暂时忽略模数(2⁴⁸)，我们可以看到（使用M和A作为乘法器和加数的简写）

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(mod2^48)可以通过模幂运算和重复平方，以o(logn)步长轻松地计算出来。

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

(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)
• 计算投资

获得

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