Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!mcvax!hp4nl!dutrun!rcdsdgx
From: rcdsdgx@dutrun.UUCP (Dik Groot)
Newsgroups: comp.arch
Subject: Re: Divide by three?
Summary: 4 shift-and-adds
Message-ID: <736@dutrun.UUCP>
Date: 2 Jun 89 11:46:28 GMT
References: <8906020201.AA10938@terra.oscs.montana.edu>
Reply-To: rcdsdgx@dutrun.UUCP (Dik Groot)
Organization: Delft University of Technology, The Netherlands
Lines: 22

In article <8906020201.AA10938@terra.oscs.montana.edu> iphwk@terra.oscs.montana.edu (Bill Kinnersley) writes:
>[In "Divide by three?" shs@uts.amdahl.com (Steve Schoettler) said:]
>: 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?
>How about using the identity
>
>   1/3 = 1/4 + (1/4)^2 + (1/4)^3 + ...
>
which can also be written as 

1/3 = 1/4 * ( 1 + 1/4 ) * ( 1 + (1/4)^2 ) * ( 1 + (1/4)^4 ) * ... ^8 ...

So divide by 4, and add to the original. Divide the result by 16, and
add. Divide by 256, and add. Do this in 16 bits arithmetic or you might
loose some bits. Divide the last result by 4.
                                                       DikGroot!
-- 
{ - - - - - - - - - - - - - - - - - - - disclaimer : I usually lie. }
Dik Groot,   Delft University of Technology,   Rekencentrum,   DUneT.
Postbox 354, 2600 AJ Delft.  ptt: (31)-15-781938  fax: (31)-15-786522
BITNET/EARN: RCDSDGX AT HDETUD1          usenet/eunet: rcdsdgx@dutrun