Java Random(seed) get random at index?

Question

Explanation below, here is my current code.

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);
    }

That outputs the following

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
{}

My goal is exactly what is above. I want to make a class that extends Random, that includes a getSeededIntAtIndex function. For example, I would want to implement the class as follows.

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

Currently, to do this, I have the following code.

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

    return temp.nextInt();
}

I am simply cycling through the random X number of times until it hits the desired number. However, if I select a large index, like 3,000,000 I would prefer this method be optimized. Is there any way this can be optimized? This method only takes ~0.34 seconds to run on seemingly any device, PC or cell phone. I had only asked this question because it seems like a waste of 2,999,999 calculations, even if it is not really hard on the system. Why not optimize if it is possible?

Answer 1

java.util.Random is specified to use the following recurrence to advance the seed:

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

This is a linear congruential generator, and as such, we can advance it N steps in only O(log(N)) time.

Let a = 0x5DEECE66DL, b = 0xBL, and m = 1L << 48. The value of the seed after N steps has the following closed form (not actual Java):

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

There are two reasons I didn't try to write this as a valid Java statement. The first is that we need modular exponentiation to evaluate this efficiently, and the second is that we need 80-bit arithmetic to compute (a^N - 1) mod (a-1)m. Both of these problems can be solved using Java's BigInteger class, which provides modular exponentiation and arbitrary-precision integers. Alternatively, we can use a variation on the modular exponentiation algorithm to calculate ((a^N - 1) mod (a-1)m)/(a-1) as (a^(N-1) + a^(N-2) + ... + a + 1) mod m within the bounds of 64-bit arithmetic, saving us from having to go through the overhead of BigInteger.

Nayuki, one of the guys I linked to earlier, has a working demo of an LCG with the ability to skip forward and backward, based on BigInteger. You could use that with the parameters specified for java.util.Random to implement a java.util.Random equivalent with skipahead capabilities, or you could write it yourself.