Messages in this thread | | | Date | Fri, 22 Jan 1999 19:12:05 -0600 | From | Charles Cazabon <> | Subject | Re: Random number generator for skiplists |
| |
Alan Mimms <alan@packetengines.com> wrote: > > Here is (http://wannabe.guru.org/alg/node134.html ) a reference to what > looks like a pretty fast and pretty good random number generator that > would be useful for skiplists.
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/
| |