[Open-graphics] peer review of a fast boolean addition algorithm, please...

[Mark]

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;
}