`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 agofor a project involving gambling devices -- where patterns in the outputwould be a Very Bad Thing (tm).  I had a look at the code referenced aboveand 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 GeorgeMarsaglia's DieHard suite of randomness evaluation tests.  The algorithmis 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 achievethat, you just generate a table (say 64 entries) from this function.To get your higher-quality random number, you generate one above, maskoff everything but bits 31-26, shift that, and use it as an index intothe table to get your number.  You then replace it with another numberfrom this function.Very fast, and very high-quality pseudo-random numbers.  I have an analysisdone on a stream of ten million numbers generated this way if anyone isinterested.  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" inthe body of a message to majordomo@vger.rutgers.eduPlease read the FAQ at http://www.tux.org/lkml/`