🚀 go-pugleaf

In article <12640@pur-ee.UUCP> hankd@pur-ee.UUCP (Hank Dietz) writes:
>simplicity), we managed to get divide to be FASTER than multiply...  but it
>doesn't give you modulus/remainder for free.  Yeah, it surprised me too.  I

A number of you have sent me email asking to see the algorithms...  Ok.
What follows is the C code implementing them for 31-bit unsigned values; of
course, I don't advocate writing such routines in C for actual use....

							-hankd@ecn.purdue.edu
---------- cut here for C code which follows ----------

/*	md.c

	Software multiply & divide routines written in C.

	Using a "typical" distribution of operand values, the approximate
	relative times clock mul() at about 30% longer than div() on average
	(on both a Vax 11/780 and a Gould NP1, as measured by profiling
	*LOTS* of executions).  Note that I make no claim of optimality for
	either routine...  they were simply the ones with the best average
	performance among those that we tried.

	Dec. 1988 by H. Dietz...  compiled for posting Aug. 1989.
*/

mul(a, b)
register int a, b;
{
	register int t = 0;

	if (a > b) {
		a ^= b;
		b ^= a;
		a ^= b;
	}

	{
		register int i =
			((a & 0x3fff0000) ?
			 ((a & 0x3f000000) ? 0x20000000 : 0x00800000) :
			 ((a & 0x0000ff00) ? 0x00008000 : 0x00000080));

		do {
			t += t;
			if (a & i) t += b;
		} while (i >>= 1);
	}

	return(t & 0x3fffffff);
}

div(a, b)
register int a, b;
{
	register int shift = 0;
	register int result = 0;

	if (!b) return(0x3fffffff);

	/* Kill trailing zero */
	while (!(b & 1)) {
		b >>= 1;
		a >>= 1;
	}

	/* If b was a power of two, a is the result */
	if (b == 1) return(a);

	/* Normalize b to a */
	while (b < a) {
		b += b;
		++shift;
	}
	if (b > a) {
		b >>= 1;
		--shift;
	}

	/* Subtract loop */
	while (shift-- >= 0) {
		result += result;
		if (a >= b) {
			a -= b;
			result |= 1;
		}
		b >>= 1;
	}

	return(result);
}