🚀 go-pugleaf

In article <d33P02nM30sj01@amdahl.uts.amdahl.com> shs@uts.amdahl.com (Steve Schoettler) writes:
 
>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.
 
        1a. If you can do a 2-bit shift in 1 instruction, then try:
	    Divide by 4 [y = (x >> 2)], divide by 16 [z = (y >> 4)] and
	    add [y += z].  This gives:  x * (1/4 + 1/16) or x * 0.3125,
	    which is only 2% error in 3 instructions (and adding another
	    shift-by-2 and add gives x * 0.328125 (0.5%) in 5).

John Hascall / ISU Comp Center / Ames IA