Re: binary divide by 3

From: Aslan Kral (aslanski2002_at_yahoo.com)
Date: 03/13/05 

Date: Sun, 13 Mar 2005 14:00:03 +0200

"Thad Smith" <ThadSmith@acm.org>, haber iletisinde sunlari
yazdi:423075C6.7F62ACA@acm.org...
> bruce varley wrote:
> >
> > I vaguely recall seeing a reference to an efficient algorithm for
performing
> > a divide by 3 on processors that only have boolean ops, shifts and
> > add/subtract. Can anyone assist? TIA
>
> You can divide by multiplying by the reciprocal. 1/3 =
> .01010101...(binary).
> This can done with shifts and adds. This illustration assumes that x
> is an unsigned integer variable:
>
> x += x >> 2; /* x * 1.01 */
> x += x >> 4; /* x * 1.010101 */
> x += x >> 8; /* x * 1.01010101010101 */
> etc., to get as many bits as needed for input range
> x >>= 2; /* x * .0101010101010101 */
>
> As a practical issue, you may want to round up to avoid the losses
> from truncation when bits are shifted off to the left:
>
> x += (x+2) >> 2;
> x += (x+8) >> 4;
> x += (x+128) >> 8;
>
> If you have an 8-bit value, only the first two terms are needed,
> 16-bits requires 3 terms, etc.
>
> Notice that the way this is written, you can get an overflow if x*4/3
> exceeds the capacity of the working variable.
>
> Thad

Alternatively:

1/(1+n) = 1/n - 1/n^2 + 1/n^3 - 1/n^4 ...

n=2
1/3 = 1/2 - 1/4 + 1/8 - 1/16 ...

Other cool n's would be n=4,8,16,32,... (1/5,1/9,1/17,1/33,...)

So in C:

#include <stdio.h>

unsigned divideBy3(unsigned n)
{
   unsigned ix = 1;
   unsigned nx = 0;
   unsigned temp;
   while (temp = n >> ix)
   {
      if (ix&1)
         nx += temp;
      else
         nx -= temp;
      ++ ix;
   }
   return nx;
}

unsigned diffs[21] = {0};

int main()
{
   unsigned ix = 0xFFFFFFF;
   int diff = -9;
   unsigned* pdiffs = diffs +10;
   while (ix)
   {
      int diffx = divideBy3(ix) - ix/3;
      if (diffx > -9 && diffx < 10)
         pdiffs[diffx] ++;
      -- ix;
   }
   while (diff < 10)
   {
      printf("%d - %u\n", diff, pdiffs[diff]);
      ++ diff;
   }
   return ix;
}

There can be a difference of -4 to 5 due to truncation of bits when
shifting.

Output: (Distribution of differerences)
-9 - 0
-8 - 0
-7 - 0
-6 - 0
-5 - 0
-4 - 407
-3 - 122031
-2 - 4668885
-1 - 41504190
0 - 107980514
1 - 89338095
2 - 23138115
3 - 1659060
4 - 24129
5 - 29
6 - 0
7 - 0
8 - 0
9 - 0