Re: A Fast Alternative to Modulo Reduction

[Mouse <mouse%Rodents-Montreal.ORG@localhost>]

>> I came across an interesting article [...which...] says divisions
>> are more expensive as compared to multiplications,

This is true on some machines, less true on others.  (I don't know of
any where division is faster than multiplication.  But, since we're
talking about 32x32->64 multiplies and 32/32->32 divides, such a
machine might actually exist.)

>> so instead of doing x % N, we can use (x * N) >> 32.

Only if X has the full 32-bit range.  rand() goes only to RAND_MAX,
which is 0x7fffffff on the handiest machine I have to check, and
random() is specifically documented as having only 31 bits of range.
For those, you'd want to do (x*N)>>31.

>> 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.

However, as I read the manpage, fast_divide32 doesn't do the (x*N)>>32
thing.  x/N can, I think, always be converted into (x*M1)>>M2 for
suitably chosen M1 and M2, where x/N/M1/M2 are 32-bit unsigned, the
multiply is 32x32->64, and the result is identical to x/N.  (For
example, for N=10, M1=0xcccccccd and M2=35.)  The fast_divide32
interface looks to me as though it's designed to support such things.
(It is, however, a good example, of hardwiring hardware assumptions
into an API - in this case, that exactly-32-bits is a useful data size.
Using fast_divide32 for _anything_ (supposedly-)machine-independent is
accumulating technical debt which will need to be paid back down the
road upon encountering a machine where 32 bits is not a convenient data
size.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		mouse%rodents-montreal.org@localhost
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B