Java Random（种子）在索引处随机获取？

Question

下面的解释，这是我当前的代码。

Random seeded = new Random(seed);

    for(int j = 0; j < 3; j++)
    {
        for (int i = 0; i < 10; i++)
            System.out.println(i + " : " + seeded.nextInt(100));
        System.out.println("{}");
        seeded= new Random(seed);
    }

输出以下内容

0 : 91
1 : 76
2 : 3
3 : 56
4 : 92
5 : 98
6 : 92
7 : 46
8 : 74
9 : 60
{}
0 : 91
1 : 76
2 : 3
3 : 56
4 : 92
5 : 98
6 : 92
7 : 46
8 : 74
9 : 60
{}
0 : 91
1 : 76
2 : 3
3 : 56
4 : 92
5 : 98
6 : 92
7 : 46
8 : 74
9 : 60
{}

我的目标正是上面所说的。我想创建一个扩展 Random 的类，其中包括一个 getSeedIntAtIndex 函数。例如，我想按如下方式实现该类。

IndexedRandom random = new IndexedRandom(seed);
int iAt30 = random.getIntAtIndex(30);

目前，要做到这一点，我有以下代码。

public int getIntAtIndex (int index)
{
    Random temp = new Random(seed);
    for(int i = 0; i < index - 1; i++)
        temp.nextInt();

    return temp.nextInt();
}

我只是循环随机 X 次，直到达到所需的次数。但是，如果我选择一个较大的索引，例如 3,000,000，我希望优化此方法。有什么办法可以优化吗？这种方法只需要大约 0.34 秒即可在任何设备、PC 或手机上运行。我问这个问题只是因为它似乎浪费了 2,999,999 次计算，即使它对系统来说并不难。如果可能，为什么不优化？

Answer 1

java.util.Random被指定到使用下面的复发推进种子：

(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

这是一个线性同余生成器，因此，我们可以在 O(log(N)) 时间内将它推进 N 步。

让a = 0x5DEECE66DL、b = 0xBL、 和m = 1L << 48。N 步后种子的值具有以下封闭形式（不是实际的 Java）：

new_seed = (a^N * seed mod m) + (b * ((a^N - 1) mod (a-1)m)/(a-1) mod m)

我没有尝试将其编写为有效的 Java 语句有两个原因。第一个是我们需要模幂来有效地评估它，第二个是我们需要 80 位算术来计算(a^N - 1) mod (a-1)m。这两个问题都可以使用 Java 的BigIntegerclass来解决，它提供了模幂运算和任意精度的整数。或者，我们可以使用模幂算法的变化来计算((a^N - 1) mod (a-1)m)/(a-1)的(a^(N-1) + a^(N-2) + ... + a + 1) mod m64位运算的范围内，不必经历的开销节省了我们BigInteger。

Nayuki 是我之前联系过的人之一，他有一个LCG的工作演示，能够基于 BigInteger 向前和向后跳过。您可以将它与指定的参数一起使用，java.util.Random以实现java.util.Random具有跳过功能的等效项，或者您可以自己编写。