For example, prime number 3 an array size 8 will scan the array in the following order N = (N + PRIME) & (ARRAY_SIZE_MASK). N = (N + 3) & 7:
0 3 6 1 4 7 2 5 ... 0
As you can see, all the array entries are covered before the sequence repeats. .... Only certain prime number / power-of-2-array size combinations have this effect, ....
Ummmm.... Actually, Matt, the property you've stated is much more common than you seem to believe. If you generate a sequence N = ( N + Stride ) % ArraySize then you will visit every element of (0 ... ArraySize-1) as long as the Stride and ArraySize are relatively prime (have no prime factors in common).
In particular, if the ArraySize is a power of 2, then it suffices for the stride to be odd. Like 1, for example. ;-)
The real motivation for a prime stride is avoiding hash table collisions. Many hash functions have cyclic properties; for example, using a memory address as a hash code tends to give multiples of 4, 8, and 16. You want your stride to be relatively prime to any cycles in the hash function. Since hash functions tend to be hard to analyze, you generally just pick a number that's likely to be relatively prime to any cycles in the hash function; a large prime is a good candidate. For that reason, many hash table algorithms simply select the largest prime less than the array size as the stride.
Tim Kientzle
_______________________________________________ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "[EMAIL PROTECTED]"
