Xref: utzoo comp.arch:10043 sci.math:6879 rec.puzzles:3592
Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!lll-winken!ssyx.ucsc.edu!filbo
From: filbo@ssyx.ucsc.edu (Bela Lubkin)
Newsgroups: comp.arch,sci.math,rec.puzzles
Subject: Re: Divide by three?
Summary: Multiply by 1/3
Message-ID: <26279@lll-winken.LLNL.GOV>
Date: 2 Jun 89 12:58:59 GMT
References: <d33P02nM30sj01@amdahl.uts.amdahl.com>
Sender: usenet@lll-winken.LLNL.GOV
Reply-To: filbo@ssyx.ucsc.edu (Bela Lubkin)
Followup-To: comp.arch
Organization: R Pentomino
Lines: 35

1/3 in binary is .01010101...

To divide an 11-bit number by 3, multiply it by .01010101... binary.

To do this without using a multiply instruction:
  Store 0 in Result.
  Repeat 5 times:
    Shift Dividend right by 2 and add it to Result. 
-- this amounts to 16 simple instructions, if no looping constructs are used.

However, the results will be more accurate if you:
  Store Divident in Result.
  Repeat 5 times:
    Shift Dividend right by 2 and add it to Result.
  Increment Result.
  Shift Result right by 2.

Neither routine is exact.  To be exact to 11 bits' accuracy with this method,
you must first shift the dividend left 11 times to make it a 22-bit value,
then shift-right-by-2-and-add 11 times.  And yes, the code can be optimized a
bit by cascading the shift-and-adds, eliminating some of the intermediate adds.

Alternatively, use any approximate method, then correct the result by re-
multiplying it by 3 (shift left and add), then repeatedly adding 3 to that
value until it exceeds the dividend, while also incrementing the approximate
result.  i.e. if algorithm X says that 100/3 is 30:
  30*3=90
  (30+1)*3=93
  (30+2)*3=96
  (30+3)*3=99
  (30+4)*3=102
  retreat to 30+3, 33.

You could even recursively apply the approximate algorithm to the difference
between the dividend and 3*(dividend approximately/3).  >Bela<