Using integer multiplication to avoid integer division

[sun!attunix.sf.att.com!dfp]

Dave Hough writes:
>But Mike Powell pointed out in another context that integer division
>by a fixed constant can often be replaced by an integer multiplication
>and a shift.   When I understood what he had in mind I decided to apply
>it to see what kind of performance improvement was possible.  I was
>running on validgh, a 4/110 with SunOS 4.0, with a version of the C 1.1
>compiler, compiling -O4 -Bstatic.  Results:
>
>	obvious code in C		6.2 secs
>	assembler call to .udiv		3.7 secs
>	Powell improvement in C		2.2 secs
>
>And here's the code which avoids division entirely:
>
>
>unsigned short
>quorem10000(x, pr)
>	unsigned long   x;
>	unsigned short *pr;
>
>/* quorem gets x/10000 ; *pr gets x%10000              */
>
>{
>	long unsigned   t;
>
>	t = ((x >> 4) * 839) >> 19;
>	switch (t) {
>	case 0:
>		*pr = x;
>		break;
>	case 1:
>		*pr = x - 10000;
>		break;
>	case 2:
>		*pr = x - 20000;
>		break;
>	case 3:
>		*pr = x - 30000;
>		break;
>	case 4:
>		*pr = x - 40000;
>		break;
>	case 5:
>		*pr = x - 50000;
>		break;
>	case 6:
>		*pr = x - 60000;
>		break;
>	}
>	return t;
>}

Maybe I'm missing something obvious, but this seems a pretty
difficult way to determine which of [0,6] is x/10000.  Given
that we're talking about this small of a range, why not:

unsigned short quorem10000(unsigned long x, unsigned short *pr)
{
	if (x < 10000)		{ *pr = x - 00000; return 0; }
	else if (x < 20000)	{ *pr = x - 10000; return 1; }
	else if (x < 30000)	{ *pr = x - 20000; return 2; }
	else if (x < 40000)	{ *pr = x - 30000; return 3; }
	else if (x < 50000)	{ *pr = x - 40000; return 4; }
	else if (x < 60000)	{ *pr = x - 50000; return 5; }
	else if (x < 70000)	{ *pr = x - 60000; return 6; }
	else			{ fatal("bad quorem10000!"); }
}

A binary search through the multiples of 10000 will reduce the
maximum number of tests from 7 to 3.  Seems pretty cheap to me.

Dave