# binary divide by 3

#### Do you have a question? Post it now! No Registration Necessary Translate This Thread From English to

• Subject
• Author
• Posted on
• binary divide by 3
• bruce varley
• 03-09-2005 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 All arithmetic processes are built on those operations.  However
you may be thinking of an adaptation of double dabble.  See
dubldabl.txt at:

--
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 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. Re: binary divide by 3 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... 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 = ;

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 