The fuzzy hash code may make the point moot, but generating
pseudo-random numbers can be done quite quickly (say, < 10 cycles) for
the fairly low quality requirements of a skip list. Precomputing a
bunch into a table and fetching from the table until empty helps a
great deal.
Certainly it is as fast as most good hash functions. (After all, I could
just keep a counter and hash that if I had a good hash function, couldn't I?)
A simple lagged-fibonacci generator like x[i] = x[i-24] + x[i-55] would
do fine. Moving to a twisted generator (TGFSR) improves things even more.
What is arguably the best PRNG currently existing, the Mersenne Twister
(Can you say "perfect score on the spectral test with up to 600 dimensions",
boys and girls?), is quite fast.
Now, if you need cryptographically strong, that's a different issue.
As I wrote before, I think it's the variable node size that makes skip
lists a pain to work with, not the random numbers.
--
-Colin
>
>A simple lagged-fibonacci generator like x[i] = x[i-24] + x[i-55] would
>do fine. Moving to a twisted generator (TGFSR) improves things even more.
>What is arguably the best PRNG currently existing, the Mersenne Twister
>(Can you say "perfect score on the spectral test with up to 600 dimensions",
>boys and girls?), is quite fast.
>
MT19937 has a period of 2^19937 - 1, with a "623-dimensional equidistribution
property". It's available from http://www.math.keio.ac.jp/matumoto/emt.html .
Don't kill their machine though.
Marnix Coppens
---
Reality is that which | Artificial Intelligence
when you stop believing | stands no chance against
in it doesn't go away. (Philip K. Dick) | Natural Stupidity.