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
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/

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