lkml.org 
[lkml]   [1999]   [Jan]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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/

\
 
 \ /
  Last update: 2005-03-22 13:49    [from the cache]
©2003-2011 Jasper Spaans