Re: A Fast Alternative to Modulo Reduction

[Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>]

   Date: Fri, 16 Dec 2016 14:39:05 +0530
   From: Abhinav Upadhyay <er.abhinav.upadhyay%gmail.com@localhost>

   I came across an interesting article [1] which talks about a faster
   alternative to the mod operation (x % N) for mapping a number to a
   fixed range, such as [0, N), which is common when we want to generate
   random numbers within a given range, or map a hash value to a range of
   indices in an array.

   It says divisions are more expensive as compared to multiplications,
   so instead of doing x % N, we can use (x * N) >> 32. 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.

   Is this result useful? For example I saw that rand(3) uses the %
   operation to map the value in the range of RAND_MAX.

It is useful -- so useful someone implemented it in NetBSD a few years
ago!  See the fast_divide32(3) routines.  We use it in cdb, the
constant databases, and in ld.elf_so hash table lookups.  I'm sure
there are other places it could be used too.