Messages in this thread | | | Date | Sat, 23 Jan 1999 01:33:38 +0000 | From | Alan Mimms <> | Subject | Re: Random number generator for skiplists |
| |
Charles Cazabon wrote:
> 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. > ----------------------------------------------------
Thanks Charles. However your algorithm does at least one very expensive division (or two, depending on the relationship of modulus and divide on the architecture you're running on) and two multiplies. Everything in the code I pointed to was simple addition and subtraction with a single modulus operation. I claim the running time of your function is substantially longer than the running time of the one at http://wannabe.guru.org/alg/node136.html on most processors.
I have no basis to argue one way or the other about quality of randomness comparisons of these algorithms. Quite possibly better randomness is WORTH a couple of extra divisions and multiplies per skiplist insertion, especially if searches and deletions are much more common than insertions.
a
- 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/
| |