Thu, 29 Jun 1995 20:58:34 GMT

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

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

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;

}

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.