Thread: generic add with carry

I am in the process of rewriting a big integer class. the older version is fast but makes some non-portable assumptions (inline assembly). the new class takes an additional Traits template parameter that allows customization of the internal adding functionality, etc.

what I'm working on right now is a generic function that will work with any unsigned type to use with the default Traits.

here's what I've come up with:

Code:

template <typename Unsigned>
static
Unsigned
adc(Unsigned * dst, Unsigned src, Unsigned carry = 0)
{
    static
    Unsigned
    one = 1,
    half = (std::numeric_limits<Unsigned>::max)() >> one;
 
    Unsigned
    tmp = *dst;
    *dst += src + carry;
 
    return
    (src >> one) + (tmp >> one) + (((src & one) + (tmp & one) + carry) >> one) > half;
}

my concern is the efficiency of the algorithm. is there a better/faster way to do this?

So this function does an addition and returns the new carry (1 or 0)?

Since these are unsigned types, wouldn't the sum be smaller than either of the operands in case of wrap-over?

A style issue is that having a variable named one storing the value 1 looks a bit stupid. You are not avoiding a magic value by that (it is OK to use literal 1 and 0 if their purpose is clear).

Originally Posted by anon

A style issue is that having a variable named one storing the value 1 looks a bit stupid. You are not avoiding a magic value by that (it is OK to use literal 1 and 0 if their purpose is clear).

Yes, and if you REALLY want a constant of one, it should probably be const int one = 1; rather than static int one = 1;
Whilst both are relatively similar, the latter forms a "global" variable, which the compiler may not realize is a constant.

I'm pretty sure that there's a way to identify if there's a carry by examining the result, but it would require knowing the top bit.

--
Mats

>> I'm pretty sure that there's a way to identify if there's a carry by examining the result, but it would require knowing the top bit.

I'm assuming you meant the top bit of the operands? the answer is 'sometimes'. in the case where both operands have the top bit set, a carry out is guaranteed. consider: 128 + 128 + 0 = 256. conversely, when the top bits are cleared, a carry will never occur. consider: 127 + 127 + 1 = 255. in all other cases we have to resort to some other method. having said that, I could test the top bits as an optimization (considering that there is a 50% probability that they are equal).

To check for overflow when adding unsigned types, simply perform the add and check if the result is less than one of the operands.
i.e.

Code:

unsinged int a, b, c;
cin >> a >> b >> c;
c = a + b;
bool carry = c < a;

You could study the big integer class on my webpage. It's pretty optimal for most things, an uses no asm whatsoever. However I don't go as far as using std::numeric_limits even once, so it's only 99% portable.

But there is also the carry: so MAX + MAX + 1 = MAX.

Also MAX + 1 + 1 = 1 which overflows but is not smaller than the second operand (where the last one is carry).

anon's right. beside that, comparing against a single operand wouldn't be sufficient.

Code:

template <typename T>
bool adc(T * dst, T src, bool carry = 0)
{
   bool result = *dst > std::numeric_limits<T>::max() - carry;
   *dst   += carry;
   result += *dst > std::numeric_limits<T>::max() - src;
   *dst   += src;
   return result;
}

?

[edit] Beaten by Dave_Sinkula. [/edit]
[edit=2] Is is portable to rely on true being 1, rather than some other value like -1?

Code:

result += *dst > std::numeric_limits<T>::max() - src;

[/edit]

The best way I can think of to detect overflow would be to use something like this.

Code:

if(b > MAX - a) {
    // overflow
}

That's assuming that you know the maximum possible value for the given type, of course. Something you can easily determine with

Code:

std::numeric_limits<type>::max()

BTW, why did you have parentheses around your call?

Code:

(std::numeric_limits<Unsigned>::max)()

Originally Posted by dwks

[edit=2] Is is portable to rely on true being 1, rather than some other value like -1?

Code:

result += *dst > std::numeric_limits<T>::max() - src;

[/edit]

In this context I believe so:
http://web.archive.org/web/200502070...aft.html#3.3.8

Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.

Hmm, that's good to know. I've occasionally used code like this just because I wasn't sure if that was the case:

Code:

result += (*dst > std::numeric_limits<T>::max() - src) ? 1 : 0;

Of course, in that case, this makes more sense, but you know what I mean.

Code:

if(*dst > std::numeric_limits<T>::max() - src) result ++;

Dave_Sinkula: considering that your algorithm only requires 2 subtractions and 2 compares to detect the carry, I'd say there probably isn't a more efficient solution than yours. =)

well done.

[edit]
btw, you won't mind if I use you're solution, then?
[/edit]

>> BTW, why did you have parentheses around your call?

some headers define min/max as macros (such as windows.h). the parenthesis simply prevent the compiler from interpreting it as a macro invocation.

>> BTW, why did you have parentheses around your call?

some headers define min/max as macros (such as windows.h). the parenthesis simply prevent the compiler from interpreting it as a macro invocation.

That's interesting indeed. I've never come across that problem before. Yet another reason to avoid macros, I suppose.

Code:

// does not compile
#include <iostream>

class c {
public:
    void test() { std::cout << "function\n"; }
};

#define test() \
    std::cout << "macro\n";

int main() {
    c::test();
}

Originally Posted by dwks

Of course, in that case, this makes more sense, but you know what I mean.

Code:

if(*dst > std::numeric_limits<T>::max() - src) result ++;

I was trying to avoid branching, I've heard that affects pipelines and such (but it's not my usual arena).

Originally Posted by Sebastiani

btw, you won't mind if I use you're solution, then?

I wouldn't mind at all.

Originally Posted by Sebastiani

some headers define min/max as macros (such as windows.h). the parenthesis simply prevent the compiler from interpreting it as a macro invocation.

Can something like std::numeric_limits<T>::max() resolve into a compile-time constant?

Originally Posted by Sebastiani

anon's right. beside that, comparing against a single operand wouldn't be sufficient.

Comparing against a single operand is sufficient, and the test does work in every case. You're dismissing it because it sounds too simple, without trying any example. If you don't believe me then make up a bit of code that runs through every possible test case for adding two bytes. I'll tell you now though that I've already done this test and much more myself, and you'll simply find that it always works.

Of course if you have 2 plus signs, then you need to check for overflow twice, and or the overflow flags together. Or if you get clever you can optimise the carry flag case down to the following, which is straight out of the += operator of my big integer class:

Code:

for (int i = 0; i < BIGINTSIZE; ++i) {
	data[i] += q.data[i] + carry;
	if (!carry) {
		carry = (data[i] <  q.data[i]) ? 1U : 0U;
	} else {
		carry = (data[i] <= q.data[i]) ? 1U : 0U;
	}
}

If q.data[i] + carry overflows then we go into the else case which sees that data[i] <= q.data[i] and hence the carry bit remains set.

In other words: Yes it actually works!

Feel free to download the whole bigint.h from the 'useful classes' section on my site and give it a whirl.