generic add with carry

This is a discussion on generic add with carry within the C++ Programming forums, part of the General Programming Boards category; I am in the process of rewriting a big integer class. the older version is fast but makes some non-portable ...

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Question 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?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by anon View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> 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&#37; probability that they are equal).
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    anon's right. beside that, comparing against a single operand wouldn't be sufficient.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  8. #8
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    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;
    }
    ?
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,047
    [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)()
    Last edited by dwks; 11-09-2007 at 06:26 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by dwks View Post
    [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.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  11. #11
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,047
    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 ++;
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  12. #12
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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.
    Last edited by Sebastiani; 11-09-2007 at 07:24 PM.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  13. #13
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,047
    >> 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();
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  14. #14
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by dwks View Post
    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 View Post
    btw, you won't mind if I use you're solution, then?
    I wouldn't mind at all.

    Quote Originally Posted by Sebastiani View Post
    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?
    Last edited by Dave_Sinkula; 11-09-2007 at 07:35 PM. Reason: Combining consecutive posts.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Sebastiani View Post
    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.
    Last edited by iMalc; 11-09-2007 at 09:41 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 05:55 PM
  2. Vector vs. array.
    By matsp in forum C++ Programming
    Replies: 37
    Last Post: 06-23-2008, 12:41 PM
  3. Help needed Please
    By jereland in forum C Programming
    Replies: 9
    Last Post: 03-18-2004, 04:30 AM
  4. Can somebody test this code please
    By andy bee in forum C Programming
    Replies: 6
    Last Post: 10-09-2001, 03:08 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21