🚀 go-pugleaf

In article <d33P02nM30sj01@amdahl.uts.amdahl.com> shs@uts.amdahl.com (Steve Schoettler) writes:

>	What's the fastest way to divide an 11 bit number by three,
>	on a processor that doesn't have any multiply or divide instructions?
>
>	There is not enough room in memory for a table lookup.

Sorry if this is a dense answer, but what's wrong with multiplying
by 1/3?  In binary, that's 0.010101..., so the algorithm looks like

	temp := number>>2;
	quot := temp

	while temp>=4 do temp := temp>>2; quot := quot+temp end

For an 11-bit number, worst case is 5 shifts and 4 adds.  If I expected
a logarithmic distribution of input values, I'd probably unroll the loop
and branch out after iterations 2 and 3.