java - How to obtain all possible values returnable by Random.nextLong?

Question

The Random#nextLong() documentation states that this method will not return all possible long values:

Returns the next pseudorandom, uniformly distributed long value from this random number generator's sequence. The general contract of nextLong is that one long value is pseudorandomly generated and returned. The method nextLong is implemented by class Random as if by:

public long nextLong() {
    return ((long) next(32) << 32) + next(32);
}

Because class Random uses a seed with only 48 bits, this algorithm will not return all possible long values.

For example, the number 8090327796378429294 is generatable, but the number 8090327796378429295 is not, even though their only difference is one least significant bit, and the value itself is 63 bits long.

There's a way to know whether or not a value can be returned by nextLong() using the following algorithm:

public class JavaRandom {
    private static final long ADD = 0xBL;
    private static final long MULT = 0x5DEECE66DL;
    private static final long TWO16 = 1L << 16;
    private static final long MASK_31 = (1L << 31) - 1;
    private static final long MASK_32 = (1L << 32) - 1;
    private static final long MASK_48 = (1L << 48) - 1;

    public static boolean canBeGeneratedByJavaRandom(long randomValue) {
        long i1 = (randomValue >> 32) & MASK_32;
        long i2 = (randomValue & MASK_32);
        if (i2 > MASK_31) {
            i1 = i1 + 1;
        }

        long front = i1 << 16;
        for (long i = 0; i < TWO16; i++) {
            long seed = front | i;
            long i22 = (((seed * MULT) + ADD) & MASK_48) >> 16;
            if (i22 == i2) {
                return true;
            }
        }

        return false;
    }
}

How can I get all values that can be generated by nextLong() without running this check for every possible 64-bit number? Calling nextLong() until all values are collected doesn't feel reasonable as well as there can be collisions.

question from:https://stackoverflow.com/questions/65910868/how-to-obtain-all-possible-values-returnable-by-random-nextlong

Answer 1

Given that the setSeed function fully uses the lower 48 bits of the value passed in to set the seed, you can simply iterate over all seed value from 0 to (1L << 48) - 1, setSeed to each of them, then call nextLong() once for each seed.

More info:

• This answer points out that it's possible to determine the seed from 2 consecutive nextInt() values, therefore there are no two different seeds that generates the same 2 consecutive nextInt() values.
• The documentation states that nextInt() calls next(32), and nextLong() gets the value of 2 consecutive next(32) values.

From the two points above, different seed values will generate different nextLong() values.