🚀 go-pugleaf

In article <44t2n7$oe1@bug.rahul.net>, Samuel P. Kho <samkho@rahul.net> wrote:
> could you describe how to take modulo-prime-number-1-less-than-2^n by
> few shifts and adds over mod 2^n?

Sure!  It's the same way you find numbers modulo 9 in base 10: add up the
digits.  Or the way you find them modulo 11, by alternating adding and
subtracting.

For example, let's say I want a 32-bit number modulo 31.  That's 2^5-1,
and it takes 7 5-bit fields to fill up a 32-bit number, so we'll reduce
logarithmicly, in three steps:

word32 mod31(word32 x)
{
	/* First, 5*4 = 20 bits, and add 1 to prevent 0 result */
	x = (x & 0xfffff) + (x >> 20) + 1;
	/* Then 10 bits */
	x = (x & 0x3ff) + (x >> 10);
	/* Then 5 bits */
	x = (x & 0x1f) + (x >> 5);	/* 1 <= Result <= 0x3f */
	/* Then fold back in any overflow and subtract the extra 1 */
	x = (x & 0x1f) + (x >> 5);	/* 1 <= Result <= 0x20 */
	x = (x & 0x1f) + (x >> 5) - 1;	/* 0 <= Result <= 0x1e */
}

The idea is based on the fact that 32*x is congruent to x mod 31.
So if I take some bits and shift them 5 (or a multiple of 5) bits down
and add them to the remaining bits, I haven't changed the value,
modulo 31.

The only tricky part is figuring out the number of final fold-back
steps required, or maybe finding a way to structure the computation
so fewer are needed.  The +1/-1 part (where the +1 gets added is not too
critical) is because the fold-and-add reduces numbes to the range 1..31
(except for an input of zero), and we want an output range of 0..30.

The last little bit is kind of tricky to nail down = perhaps someone
who's thought about it more can suggest a more efficient algorithm?

(There are variations on this for 2^n-k, for small k, although
they get more complex.)
-- 
	-Colin