java – 如何获取第n个随机“nextInt”值？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 如何获取第n个随机“nextInt”值？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1892字，纯文字阅读大概需要3分钟。

内容图文

当使用类java.util.Random时,如何获得从调用nextInt()方法获得的值N次,但是以更有效的方式(具体在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个nextseed”值？我假设在那之后,我可以通过让变量“bits”为32来获取第n个int值(方法nextInt()只调用next(32)并返回结果).

提前致谢

PS：也许这是一个更适合mathexchange的问题？

解决方法:

你可以在O(log N)时间内完成.从s(0)开始,如果我们暂时忽略模数(248),我们可以看到(使用m和a作为乘数和加数的简写)

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

现在,通过重复平方的模幂运算,可以在O(log N)步骤中容易地计算m ^ N(mod 2 ^ 48).

另一部分有点复杂.暂时忽略模数,几何和是

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

是什么让计算这个模2 ^ 48有点不重要的是m – 1不是模数的互质.但是,自从

m = 0x5DEECE66DL

m-1的最大公约数和模数为4,而(m-1)/ 4具有模289的模逆公式.让

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)

内容总结

以上是互联网集市为您收集整理的java – 如何获取第n个随机“nextInt”值？全部内容，希望文章能够帮你解决java – 如何获取第n个随机“nextInt”值？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端