# Re: integer mod with constant modulus.

## mernst@theory.lcs.mit.edu (Michael Ernst)Thu, 29 Jun 1995 20:58:34 GMT

From comp.compilers

Related articles
integer mod with constant modulus. rocky@panix.com (R. Bernstein) (1995-06-24)
Re: integer mod with constant modulus. mernst@theory.lcs.mit.edu (1995-06-29)
Re: integer mod with constant modulus. markt@harlequin.co.uk (1995-07-04)
HAKMEM #169 chase@centerline.com (1995-07-06)
| List of all articles for this month |

 Newsgroups: comp.compilers From: mernst@theory.lcs.mit.edu (Michael Ernst) Keywords: arithmetic Organization: MIT Lab for Computer Science References: 95-06-047 Date: Thu, 29 Jun 1995 20:58:34 GMT

"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

-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;
}
--

Post a followup to this message