Do you have a question? Post it now! No Registration Necessary
- Subject
- Posted on
- binary divide by 3
- 03-09-2005
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:
<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.
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.
Thad
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[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
- » Reverse current into a lithium battery
- — Next thread in » Embedded Programming
- » [Q] Old PC-ISA Data Bus Hold Time Requirement??
- — Previous thread in » Embedded Programming
- » Getting i2c touchscreen to work on TS4900
- — Newest thread in » Embedded Programming
- » Embedded Ethernet
- — Last Updated thread in » Embedded Programming
- » Switch Types
- — The site's Newest Thread. Posted in » Electronics Design