> Suppose you want to pick an integer at random in a set of N elements.
Furthermore, suppose the distribution has to be even. Then, you do not want the modulo N in any shape or form, unless the modulus is a factor of the range of the random number source.
What you do is find the smallest power of P, such that N < P. Then you reduce the input numbers using mod P; which is a fast bitwise AND operation against (P - 1).
Then, you reject values which are >= N; you get another random number R and try again, until R & (P - 1) lands in the [0, N) range.
> Suppose you have a hash table with a capacity N. Again, you need to transform your hash values (typically 32-bit or 64-bit integers) down to an index no larger than N.
I wouldn't have such a thing where N isn't a power of two.
Non-power-of-two moduli in hash tables are only useful in the open addressing technique, where all entries are stored in the table itself, rather than in chains emanating from the table. Open addressing resolves collisions by probing for alternate locations in the hash table. If the modulus is a prime number under open addressing, then if quadratic probing is used:
it will have the property of visiting all the table locations. That is to say, the quadratic probes modulo a prime N generate a sequence of unique table entries before repeating. This guarantees that a place will be found for any new key even if the table has just one slot left.
Furthermore, suppose the distribution has to be even. Then, you do not want the modulo N in any shape or form, unless the modulus is a factor of the range of the random number source.
What you do is find the smallest power of P, such that N < P. Then you reduce the input numbers using mod P; which is a fast bitwise AND operation against (P - 1).
Then, you reject values which are >= N; you get another random number R and try again, until R & (P - 1) lands in the [0, N) range.
> Suppose you have a hash table with a capacity N. Again, you need to transform your hash values (typically 32-bit or 64-bit integers) down to an index no larger than N.
I wouldn't have such a thing where N isn't a power of two.
Non-power-of-two moduli in hash tables are only useful in the open addressing technique, where all entries are stored in the table itself, rather than in chains emanating from the table. Open addressing resolves collisions by probing for alternate locations in the hash table. If the modulus is a prime number under open addressing, then if quadratic probing is used:
https://en.wikipedia.org/wiki/Quadratic_probing
it will have the property of visiting all the table locations. That is to say, the quadratic probes modulo a prime N generate a sequence of unique table entries before repeating. This guarantees that a place will be found for any new key even if the table has just one slot left.