`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 expensivedivision (or two, depending on the relationship of modulus and divide on thearchitecture you're running on) and two multiplies.  Everything in the codeI pointed to was simple addition and subtraction with a single modulusoperation.  I claim the running time of your function is substantially longerthan the running time of the one at  http://wannabe.guru.org/alg/node136.htmlon most processors.I have no basis to argue one way or the other about quality of randomnesscomparisons of these algorithms.  Quite possibly better randomness is WORTH acouple of extra divisions and multiplies per skiplist insertion, especially ifsearches and deletions are much more common than insertions.a-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/`