Xref: utzoo comp.arch:10054 sci.math:6887 rec.puzzles:3593 Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!gatech!udel!rochester!pt.cs.cmu.edu!sei!firth From: firth@sei.cmu.edu (Robert Firth) Newsgroups: comp.arch,sci.math,rec.puzzles Subject: Re: Divide by three? Message-ID: <3440@bd.sei.cmu.edu> Date: 2 Jun 89 18:22:03 GMT References: Reply-To: firth@sei.cmu.edu (Robert Firth) Followup-To: comp.arch Organization: Software Engineering Institute, Pittsburgh, PA Lines: 18 In article shs@uts.amdahl.com (Steve Schoettler) writes: > 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. Sorry if this is a dense answer, but what's wrong with multiplying by 1/3? In binary, that's 0.010101..., so the algorithm looks like temp := number>>2; quot := temp while temp>=4 do temp := temp>>2; quot := quot+temp end For an 11-bit number, worst case is 5 shifts and 4 adds. If I expected a logarithmic distribution of input values, I'd probably unroll the loop and branch out after iterations 2 and 3.