🚀 go-pugleaf

> 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