Xref: utzoo comp.arch:10064 sci.math:6896 rec.puzzles:3598
Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!agate!helios.ee.lbl.gov!nosc!humu!uhccux!aloha1!!jimh1
From: jimh1@.UUCP (jimh1 is ACK alter ego)
Newsgroups: comp.arch,sci.math,rec.puzzles
Subject: Re: Divide by three?
Summary: previous work in the field
Message-ID: <162@.UUCP>
Date: 2 Jun 89 19:38:13 GMT
References: <d33P02nM30sj01@amdahl.uts.amdahl.com>
Organization: Verifone Inc., Software tools, Mililani, HI
Lines: 16


in the paper "A Fast Technique for Constant Divisors" CACM V19 nr 2
all such division operations are considered for this class of problems.

let N be the given. 
	M = N * 5; /* 2^2+1 = 5*/
	M = M * 17; /* 2^4 +1 = 17 */
	M = M * 257; /* 2^8 +1 = 257 */
/* at this point our intermediate quantity has overflowed our
   original 11 bit register: for larger register sizes we may have
   to continue with 2^16+1 and 2^32+1 */

	ANS = -M    /* VOILA*/

Note that if the N is not evenly divisible by 3 the result ANS 
appears larger than N. HOWEVER, ANS * 3 results in N (within 11 bits)