Xref: utzoo comp.arch:10029 sci.math:6868 rec.puzzles:3588
Path: utzoo!attcan!uunet!cs.utexas.edu!sun-barr!ames!amdahl!shs
From: shs@uts.amdahl.com (Steve Schoettler)
Newsgroups: comp.arch,sci.math,rec.puzzles
Subject: Divide by three?
Message-ID: <d33P02nM30sj01@amdahl.uts.amdahl.com>
Date: 1 Jun 89 22:50:18 GMT
Reply-To: shs@uts.amdahl.com (Steve Schoettler)
Organization: Amdahl Corporation, Sunnyvale CA
Lines: 29


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