Random number generators discussion

Random number generators | www.agner.org

thread Generate ALL float numbers in RNG? - Hangzai Luo - 2004-06-16
last replythread Generate ALL float numbers in RNG? - Agner - 2004-06-18
last replythread Generate ALL float numbers in RNG? - Hangzai Luo - 2004-06-18
last reply Generate ALL float numbers in RNG? - Agner - 2004-06-19
Generate ALL float numbers in RNG?
Author:  Date: 2004-06-16 14:15
I just saw your program and have a question.

Seems your program can't generate all valid float in [0,1).

Like the smallest float (32 bits) is 2^-126, seems your program can only generate 2^-32?


Generate ALL float numbers in RNG?
Author: Agner Date: 2004-06-18 06:52
The result is double precision. The smallest double is 2^-1022 = 10^-307. The probability of reaching a number between 0 and 10^-307 from a perfect uniform distribution would be so small that it would never happen if all the computers in the world did nothing but generating random numbers until doomsday!!!

You have a choice between the resolutions 2^-32, 2^-52, and 2^-63 = 10^-19. That's more than enough for any application you could ever think of.

I think you are confusing range and resolution. The range of floating point numbers is defined by the minimum/maximum exponent. The resolution is defined by the maximum number of decimals. A double can distinguish between 0 and 10^-307, but not between 1 and 1+10^-307.

Generate ALL float numbers in RNG?
Author:  Date: 2004-06-18 20:43
I know the smallest positive double is 2^-1022.
What I mean is your algorithm can't generate all valid random numbers in [0,1).
Your algorithm is like to generate a binary fixed point number of:


and returns f-1.0. This is equal to random()/2^32 mathematically (with full
scale computation, certainly). The problem is, if random() outputs a small number,
say 127, we can write the output float as this:

1.111111(in binary)x2^-25

The problem here is, the mantissa has only 6 bits. The precision is very bad.
Single precision float format can have 2^22 different numbers in [2^-25,2^-24),
but your program can only gives 2^6 = 64 of them.

You may argue the probability is very low, but with my test,
it hits 2^-27 in less than 30 secons, and hits 0 about 9 times in one hour.
I use your B generator to do the test on a Pentium 4 2GHz CPU.
The smallest positive number your program can give is 2^-32 and I met this
number in the one-hour test. This number will given as the entire mantissa
field equals 0.

Generate ALL float numbers in RNG?
Author: Agner Date: 2004-06-19 09:54
Why don't you use one of the algorithms that give 52 or 63 bits resolution? Make sure your results are stored with double or long double precision so you don't loose information somewhere in your code. (Microsoft compilers don't support long double). With a resolution of 32 bits, you can get any value by chance within a reasonable time. With 52 bits or more you can not.

Even though it is possible to represent extremely small values 2^(-x) in a float or double or long double, it's not possible to store the value 1-2^(-x). A random number generator that can generate 2^(-x) but not 1-2^(-x) will obviously not have a perfect uniform distribution. Therefore, x is limited by the resolution, not the range.