hello all
i developed a fast boolean algorithm for calculating the addition.
because i haven't studied computer science, i don't know if this
algorithm is already in use in practice and where to read about it under
what name, etc. this is also why i write to here because i don't know
where else to ask. the algorithms i found on internet follow quite
different approaches and don't seem to be so compact and easily
implementable. please, if you know about this algorithm, send me a note
about where to read about it. if it's new, i put it under the
original BSD license.
the idea is to separate the basic addition from the carry. the basic
addition can be done with XOR, while the carry can be received via AND.
to put together the basic addition and the carry in turn, the carry must
be pushed one bit to the left. there are two problems left:
1. the carry may leave the bitfield (the number is too big or overflow
error). this can be easily detected by checking the highest bit of the
carry bitfield for 1 (I).
2. when the carry is mapped (with XOR) to the result of the basic
addition, there may result further (rippling) carries. i found out that
one just has to repeat the above procedure until the AND results in
zero (falsum, or no rippling carries left). this means that, in the best
case, the algorithm works O(1) and, in the worst case, O(n).
the advantage of the algorithm is that it bases on just two single
loops (the XOR loop and the AND loop), which can be processed in
parallel. the circuits can be integrated to one big loop where the
bitshift is hardwired. that's why i think that one can say that there
is only one loop to be implemented with some hardwired parts for
checking for the overflow and pushing the AND result.
below is a schema of the algorithm:
because there's only one big loop, the results of the XOR loop and the
AND loop are treated the same as the first input. this is why i use the
same variable names for input and results.
there are two input values (x, y). the result of x XOR y is written
back to x. the result of x AND y is shifted <<1 and written back to y:
the example calculation:
x = 00010111 (23)
y = 00001111 (15)
x + y = 00100110 (38)
the loop:
BEGIN:
1. x = (x XOR y) ==> (00011000,00010110,00000110,00100110 (38))
y = (x AND y) ==> (00000111,00001000,00010000,00000000 (done))
2. IF (y == 0): BREAK
3. IF (y AND 10000000): OVERFLOW ERROR
4. y = (y << 1) ==> (00001110,00010000,00100000)
GOTO BEGIN
IF (x == 38): PRINT "test passed!"
here's an implementation in c:
int main ()
{
unsigned int x = 23; // the first value
unsigned int y = 15; // the second value
unsigned int c = 1; // the carry bitfield (ignore the value)
while (c != 0)
{
c = x & y; // first extracting the (rippling) carry bits
x = x ^ y; // before x gets overwritten with the result of
// the basic addition and, from then on, the
// result of merging x with the carry
y = c << 1; // shifting the carry to merge it with x
} // already beginning from above again
if (x == 38)
printf("test passed!\n");
return 0;
}
what do you think?
dennis heuer
lehrte/hannover
germany
_______________________________________________
Open-graphics mailing list
[email protected]
http://lists.duskglow.com/mailman/listinfo/open-graphics
List service provided by Duskglow Consulting, LLC (www.duskglow.com)
