Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!mcvax!kth!sunic!sics.se!uplog!lynx!bd
From: bd@zyx.SE (Bjorn Danielsson)
Newsgroups: comp.arch
Subject: Re: Divide by three?
Message-ID: <1110@lynx.zyx.SE>
Date: 13 Jun 89 03:22:06 GMT
References: <d33P02nM30sj01@amdahl.uts.amdahl.com>
Reply-To: bd@lynx.zyx.SE (Bjorn Danielsson)
Organization: ZYX Sweden AB, Stockholm, Sweden
Lines: 81

In article <d33P02nM30sj01@amdahl.uts.amdahl.com> 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.
>
>       2. Reduced Table Lookup.
>          If there's room for 1/2 a table or 1/4 a table or ...,
>          shift right n bits.  Table entries must contain (2^n)x/3
>          instead of x/3.  As n gets larger, table gets smaller, but
>          the error increases (as 2^n).
>       
>Steve

The following algorithm uses 128 bytes of table space, and calculates an
exact answer in six instructions (or less):

        1. Split the number into a 5-bit (x) and a 6-bit (y) part,
           so that n = 64x + y.

        2. Calculate (64x)/3, y/3, remainder(64x,3), and remainder(y,3)
           by table lookups. There is one table for 64x (32 entries) and
           another for y (64 entries). In both tables, the quotient is
           shifted two bits to the left, and the righmost two bits encode
           the remainder as:

                remainder = 0   ->   bits = 00
                remainder = 1   ->   bits = 01
                remainder = 2   ->   bits = 11

           The first table must be at least 12 bits wide, and the second one
           at least 7 bits.

        3. Add the results of the table lookups. Remainders that add up to 3
           or more will result in a carry into the "4" bit, because of the
           special encoding.

        4. Shift the sum two bits to the right. The result is the answer.

Here's a C program fragment for it:

    short table1[32] = {
           0,   85,  171,  256,  341,  427,  512,  597,  683,  768,  853,
         939, 1024, 1109, 1195, 1280, 1365, 1451, 1536, 1621, 1707, 1792,
        1877, 1963, 2048, 2133, 2219, 2304, 2389, 2475, 2560, 2645
    };

    char table2[64] = {
         0,  1,  3,  4,  5,  7,  8,  9, 11, 12, 13, 15, 16, 17, 19, 20,
        21, 23, 24, 25, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40, 41,
        43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 56, 57, 59, 60, 61, 63,
        64, 65, 67, 68, 69, 71, 72, 73, 75, 76, 77, 79, 80, 81, 83, 84
    };

    unsigned int
    divide_by_three(n)
        unsigned int n;
    {
        unsigned int x, y;
        x = n >> 6;
        x = table1[x];
        y = n & 0x3f;
        y = table2[y];
        x = x + y;
        x = x >> 2;
        return x;
    }

-- 
Bjorn Danielsson, ZYX Sweden AB, +46 (18) 69 67 63, bd@zyx.SE