What is the true maximum (and minimum) value of Random.nextGaussian()?

  • A+
Category:Languages

In theory, the bounds for nextGaussian are meant to be positive and negative infinity. But since Random.nextDouble, which is used to calculate the Gaussian random number, doesn't come infinitely close to 0 and 1, there is a practical limit to nextGaussian. And Random.next is also not a perfectly uniform distribution.

It was theorised that the maximum should be about 2.2042*10^17 and related to the 53 bit shift of nextDouble (reference), but that is likely just an upper bound.

The answer probably depends on the distribution of Random.next and the exact implementation of StrictMath.sqrt and StrictMath.log. I couldn't find much information about either.

And yes, I know that the outer values are extremely unlikely, but it can be relevant, for example in the context of RNG manipulation in games.

 


So everything I will say here is purely theoretical, and I am still working on a GPU program to scan the whole seed base.

The nextGaussian() method is implemented as such.

private double nextNextGaussian; private boolean haveNextNextGaussian = false;   public double nextGaussian() {     if (haveNextNextGaussian) {       haveNextNextGaussian = false;      return nextNextGaussian;     } else {       double v1, v2, s;       do {        v1 = 2 * nextDouble() - 1;   // between -1.0 and 1.0        v2 = 2 * nextDouble() - 1;   // between -1.0 and 1.0        s = v1 * v1 + v2 * v2;      } while (s >= 1 || s == 0);       double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);      nextNextGaussian = v2 * multiplier;      haveNextNextGaussian = true;      return v1 * multiplier;     }   } 

The most interesting part has to be at the end, [return v1 * multiplier]. Because v1 cannot be larger than 1.0D, we need to find a way to increase the size of the multiplier, which is implemented as follows.

double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s); 

The only variable being "s", it is safe to establish that the lower "s" is, the bigger the multiplier will get. All good? Let's keep going.

 do {    v1 = 2 * nextDouble() - 1;   // between -1.0 and 1.0    v2 = 2 * nextDouble() - 1;   // between -1.0 and 1.0    s = v1 * v1 + v2 * v2;  } while (s >= 1 || s == 0); 

This tells us that "s" has to belong to the ]0,1[ number set and that the lowest value we're looking for is just a little bigger than zero. "S" is declared with the sum of squares of "v1" and "v2". To get the smallest theoretical value, v2 needs to be zero and v1 needs to be as small as it can possibly get. Why "theoretical"? Because they are generated from nextDouble() calls. There is no guarantee that the seed base contains those 2 consecutive numbers.

Let's have fun now!

Lowest value "v1" can hold is the double's epsilon, which is 2^(-1022). Making our way back, to get such a number, nextDouble would need to generate (2^(-1022) + 1) / 2.

That is...very very very disturbing. I'm not an expert, but I am pretty sure many bits are gonna get lost, and floating-point errors are to be expected.

It is probably(most definitely) impossible for a nextDouble to generate such a value, but the goal is to find a value as close as possible to that number.

Just for the fun of it, let's do the full math to find the answer. StrictMath.log() is implemented as the natural log. I haven't looked into it's precision, but let's assume there was no limitations on that level. The highest nextGaussian would be calculated as...

= (-2 * ln(v1 * v1) / (v1 * v1)) * v1  = (-2 * ln(EPSILON^2) / (EPSILON^2)) * EPSILON  where EPSILON is equal to 2^(-1022). 

Believe it or not, I could barely find any calculator that accepted such small numbers, but I finally opted for this high precision calculator.

By plugging in this equation,

(-2 * ln((2^(-1022))^2) / ((2^(-1022))^2)) * (2^(-1022))

I got,

1.273479378356503041913108844696651886724617446559145569961266215283953862086306158E+311

Pretty big huh? Well...it's definitely not going to be that big...but it's nice to take into account. Hope my reasoning makes sense and don't be shy to point out any mistake I made.

As I said at the start, I am working on a program to bruteforce all seeds and find the actual lowest value. I'll keep you updated.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: