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 (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
     USE worldnet address!

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

Nice. This is a keeper.

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
     USE worldnet address!

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

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