Xref: utzoo comp.arch:10059 rec.puzzles:3596 sci.math:6894
Newsgroups: comp.arch,rec.puzzles,sci.math
Path: utzoo!utgpu!jarvis.csri.toronto.edu!ois.db.toronto.edu!jonah
From: jonah@db.toronto.edu (Jeffrey Lee)
Subject: Re: Divide by three?
Message-ID: <89Jun2.223016edt.9331@ois.db.toronto.edu>
Organization: University of Toronto, CSRI
References: <d33P02nM30sj01@amdahl.uts.amdahl.com>
Date: Fri, 2 Jun 89 22:28:22 EDT

> 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.
> 

[A] You didn't specify whether the numbers were unsigned or signed
magnitude.  The following produces exact answers for 11-bit positive
integers and does not produce any partial results greater than 2047:

    int
    d3(n)
        register int n;
    {
        register q;
        q = n>>2;
        q = (n-q)>>1;
        q = (n-q)>>1;
        q = (n-q)>>1;
        q = (n-q)>>1;
        q = (n-q)>>1;
        q = (n-q)>>1;
        q = (n-q)>>1;
        q = (n-q)>>1;
        q = (n-q)>>1;
        q = (n-q)>>1;
    }

There may be faster ways that use larger partial results.
This can be altered to work for negative numbers:  negate,
compute, and negate the result.

---
Jeff Lee              jonah@db.toronto.edu