如何获得第n个随机的"nextInt".价值? [英] How to obtain the nth random "nextInt" value?
问题描述
在使用类java.util.Random时,如何才能获得通过N次调用nextInt()方法获得的值,但是以一种更为有效的方式(特别是在O(1)中)?
When using class java.util.Random, how can one get the value obtained from calling the method nextInt() N times, but in a much more efficient way (in O(1) specifically)?
例如,如果我构造一个具有特定种子值的Random对象,并且想要获得第100,000个"nextInt()值"(即,在调用方法nextInt()100,000次后获得的值),一种快速的方法,我可以吗?
For example, if I construct a Random object with a particular seed value, and I want to get the 100,000th "nextInt() value" (that is, the value obtained after calling the method nextInt() 100,000 times) in a fast way, could I do it?
为简单起见,假设JDK版本1.7.06,因为可能需要知道类Random中某些私有字段的确切值.可以这样说,我发现以下字段与随机值的计算有关:
Assume, for simplicity, version 1.7.06 of the JDK, since it may be required to know the exact values of some private fields in class Random. And speaking of, I found the following fields to be relevant in the calculation of a random value:
private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
在研究了一些随机性之后,我发现使用线性同余生成器获得了随机值.执行该算法的实际方法是方法next(int):
After exploring a bit about randomness, I found that random values are obtained using a Linear congruential generator. The actual method that executes the algorithm is method 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));
}
该算法的相关行是获得下一个种子值的行:
The relevant line for the algorithm is the one that obtains the next seed value:
nextseed = (oldseed * multiplier + addend) & mask;
因此,更具体地说,是否有一种方法可以使该公式通用化以获得第n个nextseed"值?我在这里假设,有了这个之后,我可以通过使变量"bits"为32来简单地获取第n个int值(方法nextInt()只需调用next(32)并返回结果).
So, to be more specific, is there a way that I can generalize this formula to obtain the "nth nextseed" value? I'm assuming here that after having that, I can then simply obtain the nth int value by letting the variable "bits" be 32 (the method nextInt() simply calls next(32) and returns the result).
预先感谢
PS:也许这是一个更适合 mathexchange 的问题?
PS: Perhaps this is a question more suitable for mathexchange?
推荐答案
您可以在 O(log N)
时间内完成此操作.从 s(0)
开始,如果我们暂时忽略模数(2 48 ),我们可以看到(使用 m
和 a
作为乘数
和加数
的简写)
You can do it in O(log N)
time. Starting with s(0)
, if we ignore the modulus (248) for the moment, we can see (using m
and a
as shorthand for multiplier
and addend
) that
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
现在,通过重复平方,通过模幂运算可以轻松地以 O(log N)
步骤计算 m ^ N(mod 2 ^ 48)
.
Now, m^N (mod 2^48)
can easily be computed in O(log N)
steps by modular exponentiation by repeated squaring.
另一部分要复杂一些.现在暂时忽略模数,其几何和为
The other part is a bit more complicated. Ignoring the modulus again for the moment, the geometric sum is
(m^N - 1) / (m - 1)
计算此模 2 ^ 48
有点不平凡的原因是 m-1
并非模的互质.但是,由于
What makes computing this modulo 2^48
a bit nontrivial is that m - 1
is not coprime to the modulus. However, since
m = 0x5DEECE66DL
m-1
的最大公约数,模数为4,(m-1)/4
具有模数反函数 inv
以 2 ^ 48
为模.让
the greatest common divisor of m-1
and the modulus is 4, and (m-1)/4
has a modular inverse inv
modulo 2^48
. Let
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)
这篇关于如何获得第n个随机的"nextInt".价值?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!