Xref: utzoo comp.arch:10119 sci.math:6934 rec.puzzles:3606 Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!unmvax!deimos.cis.ksu.edu!atanasoff!hascall From: hascall@atanasoff.cs.iastate.edu (John Hascall) Newsgroups: comp.arch,sci.math,rec.puzzles Subject: Re: Divide by three? Message-ID: <1115@atanasoff.cs.iastate.edu> Date: 6 Jun 89 14:35:58 GMT References: Reply-To: hascall@atanasoff.cs.iastate.edu (John Hascall) Organization: Iowa State Univ. Computation Center Lines: 22 In article shs@uts.amdahl.com (Steve Schoettler) writes: >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? > There is not enough room in memory for a table lookup. > Suppose (A): answer must be exact (to the nearest bit). > (B): answer can be approximate. >Here are a couple of ideas for (B): > 1. Divide by 2 (shift), divide by 4 (shift again), and take the average > (add and shift). This produces 3x/8, which has a 4% error, > but only takes 4 instructions. 1a. If you can do a 2-bit shift in 1 instruction, then try: Divide by 4 [y = (x >> 2)], divide by 16 [z = (y >> 4)] and add [y += z]. This gives: x * (1/4 + 1/16) or x * 0.3125, which is only 2% error in 3 instructions (and adding another shift-by-2 and add gives x * 0.328125 (0.5%) in 5). John Hascall / ISU Comp Center / Ames IA