Messages in this thread | | | Date | Fri, 22 Jan 1999 23:49:58 -0600 | From | Charles Cazabon <> | Subject | Re: Random number generator for skiplists |
| |
I wrote: [code snipped] > > /* 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; Alan Mimms <alan@packetengines.com> wrote: > > 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.
I would have assumed that the compiler would perform the division only once, as both the division result and the modulo remainder should be available simultaneously after the division -- although admittedly my assembly experience is limited to x86 only. Do other architectures require separate operations for integer division and modulo division?
I do admit the division is expensive; 486 tables show 43-44 clocks. The multiplies show as 13 clocks (best case); I can't seem to find my Pentium references. I would assume it is somewhat faster, but am not sure.
> 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 bow to you on this; I'm not even sufficiently sure of my understanding of the kernel internals to call myself a novice.
> 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.
If this is the case, the algorithm I presented would definitely fit the bill; Marsaglia's analysis software showed zero high-order correlation in any of the tests on the output of this algorithm.
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/
| |