Re: A Fast Alternative to Modulo Reduction

[Alexander Nasonov <alnsn%yandex.ru@localhost>]

Mouse wrote:
> Abhinav Upadhyay wrote:
> >> Both operations are not _equivalent_ but he proves that the latter
> >> is also a fair mapping of x in the range [0, N) for 32 bit integers.
> 
> Only under certain assumptions about x - loosely put, that the entropy
> in x is distributed equally across all of x's bits.  But, for example,
> if you use the common string hash function that works like h=0 then
> loop{h=(h*37)+*cp++}, short strings will have all 0s in the high bits.

I can confirm that for several common hash functions (murmur, xxh,
jenkins), a distribution of bits isn't good enough to generate an
acyclic graph for chm (cdb uses the chm algorithm) for many inputs
while fast_divide32 reduction works fine most of the time.

Code is here: https://github.com:/alnsn/rgph

Alex