Range of Random.nextGaussian, continued

In the first part I described a theoretical range of values returned by nextGaussian; in this part I will describe the way used to find out the actual minimum and maximum values.

The simplest way would require using brute force to check all 2⁴⁸ possible seed values. This would take a few years on my computer, so I had to do better than that.

As explained in the first part, in order to maximize the values of nextGaussian, the values of v1 and v2 need to be as close to zero as possible. For that, the value returned by nextDouble needs to be close to 0.5. So, how do we make the random number generator return the values we want?

NextDouble calls next two times, first to get top 26 significant bits of the result, then again to get next 27 bits. If we can get the top bits to be 1 << 25, the resulting double will be very close to 0.5.

A call to next first updates the seed value used by Random, then returns top N bits of the new seed. So, we know the desired seed value after the call to next. In order to find out the value for seed before the call, we can use the simple reversing algorithm found here:

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;

private static long reverseSeed (long seed) {
    // reverse the addend from the seed
    seed -= addend;
    long result = 0;
    // iterate through the seeds bits
    for (int i = 0; i < 48; i++) {
        long mask = 1L << i;
        // find the next bit
        long bit = seed & mask;
        // add it to the result
        result |= bit;
        if (bit == mask) {
            // if the bit was 1, subtract its effects from the seed
            seed -= multiplier << i;
        }
    }
    return result;
} 

Then, we also need to counter the initial scrambling that happens in setSeed operation:

private static long unscramble(long seed) {
    return seed ^ multiplier;
}

 And we're ready to start hacking:

long seedRange = 0x2000000L;
Random rand = new Random();
double minSoFar = 0, maxSoFar = 0;
for(long seed = -seedRange;seed<seedRange;seed++) {
    rand.setSeed(unscramble(reverseSeed(0x800000000000L + seed)));
    double d = rand.nextGaussian();
    if(minSoFar > d) {
        minSoFar = d;
        System.out.println("Seed: "+seed+ " min: "+d);
    }
    if(maxSoFar < d) {
        maxSoFar = d;
        System.out.println("Seed: "+seed+ " max: "+d);
    }

    d = rand.nextGaussian();
    if(minSoFar > d) {
        minSoFar = d;
        System.out.println("Seed: "+seed+ " second min: "+d);
    }
    if(maxSoFar < d) {
        maxSoFar = d;
        System.out.println("Seed: "+seed+ " second max: "+d);
    }
}

The lowest value found was: -7.844680087923773 (on second call to nextGaussian with seed = 994892)
The highest value found was: 7.995084298635286 (on first call to nextGaussian with seed = 14005843)
These are the real maximum & minimum values returned by Oracle Java 8 implementation of nextGaussian.