PDA

View Full Version : How to generate quality random numbers in bulk?




Qaanol
Jul 19, 2013, 03:32 PM
What random number generators are available to fill large arrays (arbitrary size, often more than 100,000 bytes) with statistically high-quality random numbers?

How good is the quality of output from /dev/random?

Is there a fast and efficient way to use arc4random_uniform() to fill a large array?



subsonix
Jul 19, 2013, 03:43 PM
How good is the quality of output from /dev/random?


Read more about it here:

https://developer.apple.com/library/mac/#documentation/Darwin/Reference/ManPages/man4/random.4.html

chown33
Jul 19, 2013, 03:46 PM
What random number generators are available to fill large arrays (arbitrary size, often more than 100,000 bytes) with statistically high-quality random numbers?
Command line:
apropos random



How good is the quality of output from /dev/random?

Command line:
man 4 random



Is there a fast and efficient way to use arc4random_uniform() to fill a large array?
Try a for loop.

How do you know a for loop isn't fast and efficient? If you have evidence, please post it. If you don't have evidence, then do the simplest thing that could possibly work (a for loop), then measure it.

The representation of the value in the array will affect speed. uint_32_t times may differ from uint_8_t, float, double, etc.

gnasher729
Jul 19, 2013, 06:12 PM
What random number generators are available to fill large arrays (arbitrary size, often more than 100,000 bytes) with statistically high-quality random numbers?

How good is the quality of output from /dev/random?

Is there a fast and efficient way to use arc4random_uniform() to fill a large array?

Check out this article.

http://domino.research.ibm.com/tchjr/journalindex.nsf/4ac37cf0bdc4dd6a85256547004d47e1/87a0c1cc3288480485256bfa0067f9a8

These guys managed 40 million pseudo-random numbers per second in 2002.

Qaanol
Jul 19, 2013, 08:12 PM
Thanks everyone, I found arc4random_buf, which fills an array of specified byte length with random values.

Edit: …and apparently it is only available on 10.7 and newer, so I guess I can’t use it on my current machine. Ah well, at least I know it for future reference.

chown33
Jul 19, 2013, 08:57 PM
Thanks everyone, I found arc4random_buf, which fills an array of specified byte length with random values.

Edit: …and apparently it is only available on 10.7 and newer, so I guess I can’t use it on my current machine. Ah well, at least I know it for future reference.

You specifically mentioned arc4random_uniform() in your first post. My conclusion is that you wanted random numbers uniformly distributed below a specific upper limit.

If you just wanted random bytes (i.e. uniformly distributed values in the range [0-255]), then you should have asked for that. The obvious answer would then be /dev/random, whose characteristics are described in the man page:
man 4 random

Or you could google the source for arc4random_buf(), which you could then use without needing to rely on 10.7.

ArtOfWarfare
Jul 19, 2013, 10:11 PM
If you have control over the platform and the CPU is new enough, use C's asm function to access Intel's built in random number generator. They've been in Macs for the past 2-3 years but I don't think the compilers utilize the features of the chips yet.

Based on the usage of the phrase "pseudo random" from that link, I suspect my suggestion is superior when it comes to how random the results are (you can look up Intel's papers on how the chips guarantee their own randomness) - but of course, if you're looking to support older devices it may not be feasible.

Qaanol
Jul 21, 2013, 01:46 PM
If you just wanted random bytes (i.e. uniformly distributed values in the range [0-255]), then you should have asked for that. The obvious answer would then be /dev/random, whose characteristics are described in the man page:
man 4 random

Thanks. The Yarrow algorithm seems strong.

What I really need is a fast way to generate large arrays of floats drawn from a normal distribution.

My plan is to make an array of floats drawn from a uniform distribution between 0 and 1, then use the Box-Muller transform (or the equivalent Marsaglia polar method) to transform the result into a normal distribution. I intend to use vecLib functions to operate on the entire array quickly for that purpose.

In order to get the uniformly distributed floats, I had the idea in mind to create an array of random unsigned integers, then cast each element to a float and multiply by the reciprocal of the maximum random number.

I would prefer to do the type-cast in place, meaning I need an integer format of the same size as a float. On my machine, uint and float are each 32 bits long (sizeof() says 4 for both), so that seems like it will work, though I do not know how future-proof that is. I need the float type because that is what works with single-precision vector functions in vecLib, so perhaps uint32_t is more reliable as the destination type for the random bytes from /dev/random.