[lkml]   [1999]   [Jan]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: Random number generator for skiplists
    Alan Mimms <> wrote:
    > Here is ( ) 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 <>
    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
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:49    [W:0.019 / U:88.112 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site