🚀 go-pugleaf

Here's a puzzle:
	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.

	Suppose (A): answer must be exact (to the nearest bit).
	        (B): answer can be approximate.

Here are a couple of ideas for (B):

	1. Divide by 2 (shift), divide by 4 (shift again), and take the average
	    (add and shift).  This produces 3x/8, which has a 4% error,
	   but only takes 4 instructions.

	2. Reduced Table Lookup.
	   If there's room for 1/2 a table or 1/4 a table or ...,
	   shift right n bits.  Table entries must contain (2^n)x/3
	   instead of x/3.  As n gets larger, table gets smaller, but
	   the error increases (as 2^n).
	
Steve
-- 

        Steve Schoettler
        shs@uts.amdahl.com
        {sun,decwrl,pyramid,ames,uunet}!amdahl!shs
        Amdahl Corp., M/S 213, 1250 E. Arques Ave, Sunnyvale, CA 94088