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).

Quote:

---

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)()

---

Quote:

---

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

Quote:

---

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? :D
[/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.

Quote:

---

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

---

Quote:

---

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).

Quote:

---

Originally Posted by Sebastiani

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

---

I wouldn't mind at all.

Quote:

---

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?

Quote:

---

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.

>> You're dismissing it because it sounds too simple, without trying any example.

well, to be fair, your original solution was incomplete. but I can see how the algorithm works, now. quite ingenious. :)

on a side note, I really wasn't sure if I would get many useful or intelligent responses from this thread. luckily, I was wrong!

many thanks to everyone that posted.

Sorry to resurrect the thread, but I just thought this should be said:

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

---

Note that you could use this instead, because of what Dave_Sinkula posted:

Code:

---

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

---

Quote:

---

Originally Posted by Dave_Sinkula

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

---

Not my arena either, but it seems like you might be right:

Quote:

---

The downside of a long pipeline is when a program branches, the entire pipeline must be flushed, a problem that branch predicting helps to alleviate.

---

(From http://en.wikipedia.org/wiki/Instruction_pipeline.)

I'm assuming that flushing a pipeline is a bad thing . . . :)

Quote:

---

Originally Posted by dwks

Sorry to resurrect the thread, but I just thought this should be said:

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

---

Note that you could use this instead, because of what Dave_Sinkula posted:

Code:

---

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

---

Not my arena either, but it seems like you might be right:

(From http://en.wikipedia.org/wiki/Instruction_pipeline.)

I'm assuming that flushing a pipeline is a bad thing . . . :)

---

Flushing the pipeline is indeed bad.

However, I doubt that the compiler will actually generate noticably different code for the two pieces of source given.

--
Mats

Be extremely careful when judging programs for things like cache coherency, branch efficiency, and similar hardware-level performance issues. Your guess which of two given pieces of code is faster will typically be right 50&#37; of the time. It's extremely hard to predict what will happen, given modern compilers and CPUs.

In the course about efficient programming I'm taking right now, the teacher is showing us techniques for refactoring code and tools for measuring efficiency. The goal is to use the tools and figure out where and what the problem is, then make an informed guess at a transformation that would alleviate the problem, measure again, make another guess, and so on, until you've found the best way to do it.
Don't worry, the next generation of CPUs will invalidate all your experiments ;)

Quote:

---

Originally Posted by CornedBee

Be extremely careful when judging programs for things like cache coherency, branch efficiency, and similar hardware-level performance issues. Your guess which of two given pieces of code is faster will typically be right 50% of the time. It's extremely hard to predict what will happen, given modern compilers and CPUs.

---

Yes. My statement about the equivalence of the two last statements was based on experience with both Visual Studio C++ .Net and gcc 3 and 4. Both of those will use "SETcc" to produce truth-values from "a = x < y" or similar, so no branch there.

Quote:

---

In the course about efficient programming I'm taking right now, the teacher is showing us techniques for refactoring code and tools for measuring efficiency. The goal is to use the tools and figure out where and what the problem is, then make an informed guess at a transformation that would alleviate the problem, measure again, make another guess, and so on, until you've found the best way to do it.
Don't worry, the next generation of CPUs will invalidate all your experiments ;)

---

Sounds like an interesting class - I wish I had known about that one some 12-15 years ago when I started working on performance analyzis.

If you have something that is anything but real trivial, it's definitely necessary to "find the bottleneck" with the right type of tools, sampling profiler or some such is a good tool here.

Not only do different CPU variants change the behaviour, but also changing from one compiler to another will change the behaviour - because the next generation compiler will "know" how to do more efficient code for the latest generation processors.


--
Mats

Yeah I always thought that using the ? operator there might have been unnecessary. It's an old habbit since I learnt Pascal before C++. More strongly typed lauanges don't allow implicit conversion from bool to int.

The branch wouldn't be so bad if it was predictable, but it's probably mostly random, depending on what you're using the code for of course.

btw, I found the original code I built my version from, see here:
http://www.google.com/search?hl=en&q...2+bigint&meta=
Beware though as that code is rather buggy. I fixed hopefully all of the bugs in my version, optimised a lot of the functions (especially the bitshifts), and added a lot of missing stuff, like signed big integers.