I did a lot of research on pseudo random number generation about a year ago
for a project involving gambling devices -- where patterns in the output
would be a Very Bad Thing (tm). I had a look at the code referenced above
and it doesn't look particularly quick.
A consulting statistician in the field of gaming pointed me to a pseudo-
random number generation algorithm that held up very well under George
Marsaglia's DieHard suite of randomness evaluation tests. The algorithm
is known as Lewis-Goodman-Miller after the mathematicians who invented it.
In its simplest form, it is just the following few lines of code:
long rand (long seed)
{
/* m = 2^31 -1 = 2147483647, a = 16807
* m / a = 127773, m mod a = 2836
*/
long hi = seed / 127773L;
long lo = seed % 127773L;
seed = 16807L * lo - 2836L * hi;
if (seed <= 0) seed += 2147483647L;
return seed;
}
This gives pretty good randomness, but not lottery-quality. To achieve
that, you just generate a table (say 64 entries) from this function.
To get your higher-quality random number, you generate one above, mask
off everything but bits 31-26, shift that, and use it as an index into
the table to get your number. You then replace it with another number
from this function.
Very fast, and very high-quality pseudo-random numbers. I have an analysis
done on a stream of ten million numbers generated this way if anyone is
interested. It worked very well for the project I used it on.
Charles Cazabon
-- ---------------------------------------------------- Charles Cazabon <charlesc-linux@qcc.sk.ca> Any opinions expressed are just that -- my opinions. ----------------------------------------------------
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/