Re: integer mod with constant modulus.

"R. Bernstein" <rocky@panix.com> writes:
> [Do fast integer mod (2^x +/- 1) computations by casting out nines (or
> other appropriate factor and then summing blocks of bits in a word in
> parallel, making sure there is no carry between blocks.]


This is a really neat technique which was described in HAKMEM and is used
in the X11 sources to count the number of bits in a word (which is actually
a modulus operation). It doesn't require any branches. On some
architectures the final modulus may be expensive; it can be replaced by a
few more shifts, masks, and adds in the obvious way.


-Michael Ernst
mernst@theory.lcs.mit.edu


  /*
    * This function counts the number of bits in a long.
    * It is limited to 63 bit longs, but a minor mod can cope with 511 bits.
    *
    * It is so magic, an explanation is required:
    * Consider a 3 bit number as being
    * 4a+2b+c
    * if we shift it right 1 bit, we have
    * 2a+b
    * subtracting this from the original gives
    * 2a+b+c
    * if we shift the original 2 bits right we get
    * a
    * and so with another subtraction we have
    * a+b+c
    * which is the number of bits in the original number.
    * Suitable masking allows the sums of the octal digits in a
    * 32 bit number to appear in each octal digit. This isn't much help
    * unless we can get all of them summed together.
    * This can be done by modulo arithmetic (sum the digits in a number by molulo
    * the base of the number minus one) the old "casting out nines" trick they
    * taught in school before calculators were invented.
    * Now, using mod 7 wont help us, because our number will very likely have
    * more than 7 bits set. So add the octal digits together to get base64
    * digits, and use modulo 63.
    * (Those of you with 64 bit machines need to add 3 octal digits together to
    * get base512 digits, and use mod 511.)
    *
    * This is HAKMEM 169, as used in X11 sources.
    */
  static int
  t0_hackmemmod(register unsigned long n)
  {
register unsigned long tmp;


tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
  }
--

Return to the comp.compilers page.
Search the comp.compilers archives again.