3 ms·
If you want a quick, easy and good quality random number generator, you might want to look at xorshifts. There are a lot of variations, but I particularly like
by GuB-42 6y ago
If you want a quick, easy and good quality random number generator, you might want to look at xorshifts.
There are a lot of variations, but I particularly like the 128 bit version from the original paper [1].
Here is the entire code
unsigned long xor128() {
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
unsigned long t;
t=(xˆ(x<<11));x=y;y=z;z=w;
return( w=(wˆ(w>>19))ˆ(tˆ(t>>8)) );
}
Note: Do not use for security applications! It is not cryptographically secure. But if you need that, or if you are running Monte Carlo simulations and want nothing but the best, you probably should use specialized libraries anyways.
[1] https://www.jstatsoft.org/index.php/jss/article/view/v008i14/xorshift.pdf https://www.jstatsoft.org/index.php/jss/article/view/v008i14...
Edit: And since we are in the subject of picking random numbers for Sattolo's algorithm. Using a simple modulo operator for get a range from a single random number going from 0 to 2^n-1 (like most RNGs produce) can introduce a bias. If the list is short and the numbers are large, it doesn't make that big a difference, but it is something to consider.
- KMag 6y agoIn case anyone is wondering how to do an unbiased choice of the numbers 0 to N given an RNG that generates numbers 0 to 2^Y-1, where 2^Y-1 >= N, there are two ways, both rejecting some samples: 1. Find the smallest Z s.t. 2^Z-1 <= N, generate a random number, bitwise-and with 2^Z-1, accept the result if the result <= N, otherwise repeat. The expected number of times through the loop depends on Y and N, but is strictly less than 2. 2. Let W = floor((2^Z-1) / N), generate a random number, if the number < N*W, return the number mod N, otherwise repeat. The expected number of times through the loop depends on N and Y, but is no more than the first algorithm. The downside is that division and modular division are much slower than bitwise-and on most processors. If division or modular division (on many processors, the same instruction) is much slower than bitwise-and, and your PRNG is pretty fast (such as xorshift / xorishiro), you're better off with the first algorithm. Note that finding the mask from the first algorithm on a 64-bit machine is as simple as: mask = N; for( i = 1; i < 64; i *= 2) { mask |= mask >> i; } // Check if your compiler unrolls this loop