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/