binary divide by 3

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
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



Re: binary divide by 3
Quoted text here. Click to load it

All arithmetic processes are built on those operations.  However
you may be thinking of an adaptation of double dabble.  See
dubldabl.txt at:

  <http://cbfalconer.home.att.net/download/

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: binary divide by 3
Quoted text here. Click to load it

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

Re: binary divide by 3
Quoted text here. Click to load it

Nice.  This is a keeper.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: binary divide by 3

yazdi: snipped-for-privacy@acm.org...
Quoted text here. Click to load it
performing

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] = ;

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



Site Timeline