How to get the nth random value of "nextInt"?

Question

When using the java.util.Random class, how can I get the value obtained by calling the nextInt () method N times, but in a much more efficient way (in O (1))?

For example, if I create a Random object with a specific initial value, and I want to get the 100,000th value of nextInt () (that is, the value obtained after calling the nextInt () method 100,000 times) in a quick way, can I do this?

For simplicity's sake, suppose JDK version 1.7.06, as you may need to know the exact values ​​of some private fields in the Random class. And speaking of this, I found that the following fields matter when calculating a random value:

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

After a bit of randomness research, I found that random values ​​were obtained using a linear congruent generator. The actual method that executes the algorithm is the next (int) method:

 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 corresponding line for the algorithm is the one that receives the following initial value:

 nextseed = (oldseed * multiplier + addend) & mask; 

So, to be more specific, is there a way I can generalize this formula to get the nth nextseed value? I assume that after that I can simply get the nth int value by setting the "bits" variable to 32 (the nextInt () method just calls the next (32) and returns the result).

Thank you in advance

PS: Perhaps this is a question more suitable for mathexchange ?

Answer 1

You can do this in O(log N) time. Starting with s(0) , if we ignore module (2 ⁴⁸ ) at 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 

Now m^N (mod 2^48) can be easily calculated in steps O(log N) by modular exponentiation by re-squaring.

The other part is a bit more complicated. Ignoring the module again for now, the geometric sum

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

What makes computing this modulo 2^48 little nontrivial is that m - 1 incompatible with the module. However, since

 m = 0x5DEECE66DL 

the greatest common factor is m-1 , and the module is 4, and (m-1)/4 has a modular inverse inv modulo 2^48 . Let be

 c = (m^N - 1) (mod 4*2^48) 

Then

 (c / 4) * inv ≡ (m^N - 1) / (m - 1) (mod 2^48) 

So,

• calculate M ≡ m^N (mod 2^50)
• compute inv

To obtain

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

Answer 2

I accepted the answer from Daniel Fisher, as far as he is right, and gives a general solution. Using Daniel's answer, here is a concrete example with java code that shows the basic implementation of the formula (I used the BigInteger class extensively, so it may not be optimal, but I confirmed significant acceleration by the rudimentary method of actually calling the nextInt () method N times):

 import java.math.BigInteger; import java.util.Random; public class RandomNthNextInt { // copied from java.util.Random ========================= private static final long multiplier = 0x5DEECE66DL; private static final long addend = 0xBL; private static final long mask = (1L << 48) - 1; private static long initialScramble(long seed) { return (seed ^ multiplier) & mask; } private static int getNextInt(long nextSeed) { return (int)(nextSeed >>> (48 - 32)); } // ====================================================== private static final BigInteger mod = BigInteger.valueOf(mask + 1L); private static final BigInteger inv = BigInteger.valueOf((multiplier - 1L) / 4L).modInverse(mod); /** * Returns the value obtained after calling the method {@link Random#nextInt()} {@code n} times from a * {@link Random} object initialized with the {@code seed} value. * <p> * This method does not actually create any {@code Random} instance, instead it applies a direct formula which * calculates the expected value in a more efficient way (close to O(log N)). * * @param seed * The initial seed value of the supposed {@code Random} object * @param n * The index (starting at 1) of the "nextInt() value" * @return the nth "nextInt() value" of a {@code Random} object initialized with the given seed value * @throws IllegalArgumentException * If {@code n} is not positive */ public static long getNthNextInt(long seed, long n) { if (n < 1L) { throw new IllegalArgumentException("n must be positive"); } final BigInteger seedZero = BigInteger.valueOf(initialScramble(seed)); final BigInteger nthSeed = calculateNthSeed(seedZero, n); return getNextInt(nthSeed.longValue()); } private static BigInteger calculateNthSeed(BigInteger seed0, long n) { final BigInteger largeM = calculateLargeM(n); final BigInteger largeMmin1div4 = largeM.subtract(BigInteger.ONE).divide(BigInteger.valueOf(4L)); return seed0.multiply(largeM).add(largeMmin1div4.multiply(inv).multiply(BigInteger.valueOf(addend))).mod(mod); } private static BigInteger calculateLargeM(long n) { return BigInteger.valueOf(multiplier).modPow(BigInteger.valueOf(n), BigInteger.valueOf(1L << 50)); } // =========================== Testing stuff ====================================== public static void main(String[] args) { final long n = 100000L; // change this to test other values final long seed = 1L; // change this to test other values System.out.println(n + "th nextInt (formula) = " + getNthNextInt(seed, n)); System.out.println(n + "th nextInt (slow) = " + getNthNextIntSlow(seed, n)); } private static int getNthNextIntSlow(long seed, long n) { if (n < 1L) { throw new IllegalArgumentException("n must be positive"); } final Random rand = new Random(seed); for (long eL = 0; eL < (n - 1); eL++) { rand.nextInt(); } return rand.nextInt(); } } 

NOTE. Note the initialScramble (long) method, which is used to get the first initial value. This is the behavior of the Random class when initializing an instance with a specific seed.