Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!ico!ism780c!news
From: news@ism780c.isc.com (News system)
Newsgroups: comp.arch
Subject: Re: Divide by three?
Message-ID: <28052@ism780c.isc.com>
Date: 2 Jun 89 18:05:20 GMT
References: <8906020201.AA10938@terra.oscs.montana.edu>
Reply-To: marv@ism780.UUCP (Marvin Rubenstein)
Organization: Interactive Systems Corp., Santa Monica CA
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 + ...

How about a 2K table of quotients indexed by the 11 bit number?

   e.g in C:

       int i_over_three = [0,0,0,1,1,1,2,2,2,...];
       int i;
       i_over_three[i]  /* is i/3 */


     Marv Rubinstein