🚀 go-pugleaf

colin@nyx10.cs.du.edu "Colin Plumb" writes:
>>word32 mod31(word32 x) ...

fred@genesis.demon.co.uk writes:
>This replaces 1 division operation with, at a rough count, 17 'fast'
>operations. While this may be faster on many systems it would be unwise
>to assume it.

While Colin's example can be improved, division does take upwards of 30
cycles on many architectures.  And there are faster cases:

(assume 32-bit int)

unsigned mod65537(unsigned x) {
	unsigned x1 = (x>>16);
	unsigned x2 = x&0xffff;
	/* note x = x1*65536 + x2 = x1*65537 + x2 - x1 */
	/* so x mod 65537 = (x2-x1) mod 65537 */
	unsigned res = x2 - x1;
	if ((int)res < 0) res += 65537;
}

unsigned mod32767(unsigned x) {
	unsigned x1 = (x>>15);
	unsigned x2 = x&0x7fff;
	/* note x = x1*32768 + x2 = x1*32767 + x2 + x1 */
	/* so x mod 32767 = (x2+x1) mod 32767 */
	unsigned res = x2 + x1;
	/* but res could be as much as 2^17+2^15-2, so repeat */
	x1 = (res>>15); /* at most 4 */
	x2 = res&0xffff;
	res = x1 + x2;
	/* now res is at most 32767+4 */
	return (res < 32767) ? res : res - 32767;
}



-- 
-- Joe Buck 	<jbuck@synopsys.com>	(not speaking for Synopsys, Inc)
Anagrams for "information superhighway":	Enormous hairy pig with fan
						A rough whimper of insanity