Dennis Heuer wrote:
many thanks for your replies. naturally, i'm a bit disappointed with
the reviews :) can you point me at good internet literature about the
alternatives? however, for completeness, i also put the following
subtraction under the original BSD license:
Many thanks to you for the proposal -- I certainly enjoyed thinking it
through.
I found this page linked to by the Wikipedia article on adders, and it
seems to be pretty good:
http://www.aoki.ecei.tohoku.ac.jp/arith/mg/algorithm.html
the problem with the subtraction is that detecting the carry isn't that
easy. boolean XOR catches both 1->0 and 0->1, though only the first case
is to be considered. for a luck, filtering the first case out can be
done with a combination of XOR and AND. this is just how the other
algorithm worked except that using the XOR for both the basic addition
and the first step of the calculation of the carry needs some change in
the order of re-using the values. also, the bitshift must be done before
the carry is used in the next XOR because the shifted value is also the
correct input for the next AND. confused? just look at the following
code in c:
int main ()
{
// boolean subtraction with bit shifting
unsigned int x = 23; // the first value
unsigned int y = 15; // the second value, which is also the
// carry bitfield
while (y != 0)
{
x = x ^ y; // first calculating the addition or, from then,
// the merging with the current carry bitfield
y = y & x; // before the result becomes the second input of
// the calculation of the next carry
y = y << 1; // shifting the carry to merge it with x
} // already beginning from above again
if (x == 8)
printf("test passed!\n");
return 0;
}
in the end, this algorithm is even easier than the other. one can skip
the third variable for the carry (at least in code this makes a
difference.)
The downside from a logic implementation perspective is that you now
have a data dependency between two operations where you didn't before,
meaning that each stage is two gate-delays instead of one. If you want
to keep the basic adder block the same for the adder & subtractor, you
can add a layer of XORs at the minuend input and the output to invert
both in the case of subtraction. Of course, if it's a pure subtractor,
use inverters instead of XORs. This is what I meant by "negate one
input", which was really a sloppy way of phrasing it on my part --
sorry. What do you think?
#include <iostream>
unsigned int doit(unsigned int a, unsigned int b, unsigned int sub) {
unsigned int x=a^sub;
unsigned int y=b;
for(int j=0; j<sizeof(a)<<3; j++) {
int z=x;
x=y^z;
y=(y&z)<<1;
}
return x^sub;
}
int main(void) {
unsigned int numadd = 0;
unsigned int numsub = 0;
for (int i=0; i<10000; i++) {
unsigned int sub = (rand()&1?~0:0);
unsigned int a = rand();
unsigned int b = rand();
unsigned int x = doit(a,b,sub);
unsigned int y = (sub?a-b:a+b);
if (x!=y) {
std::cout << "Error: tried " << a << (sub?" - ":" + ") << b;
std::cout << ", expected " << y << " but got " << x << ".";
std::cout << std::endl;
return -1;
} else if (sub)
numsub++;
else
numadd++;
}
std::cout << "Success: " << numadd << " additions, ";
std::cout << numsub << " subtractions." << std::endl;
return 0;
}
_______________________________________________
Open-graphics mailing list
[email protected]
http://lists.duskglow.com/mailman/listinfo/open-graphics
List service provided by Duskglow Consulting, LLC (www.duskglow.com)
