Adding and multiplying two unsigned integers

Discussion in 'C++' started by Edith Gross, May 1, 2005.

  1. Edith Gross

    Edith Gross Guest

    I'd like to add to unsigned integers and find out whether a carry occurs.
    Can I do that in a simple and fast way?

    A similar problem is subtracting with borrow and the multiplication of two
    unsigned integers where the result may not fit?

    Can anybody give me a hint of how to wolve these problems?

    TIA,

    EG

    ----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
    http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
    ----= East and West-Coast Server Farms - Total Privacy via Encryption =----
    Edith Gross, May 1, 2005
    #1
    1. Advertising

  2. Edith Gross

    Guest

    Hmm...

    total = first + second;
    if (total < first) { /*then there was a carry*/ }
    , May 1, 2005
    #2
    1. Advertising

  3. "Edith Gross" <> wrote in message
    news:p...
    > I'd like to add to unsigned integers and find out whether a carry occurs.
    > Can I do that in a simple and fast way?

    In a portable way, I think the best you can do is:
    unsigned c = a + b;
    bool carryOccurred = ( c<a || c<b );

    > A similar problem is subtracting with borrow and the multiplication of two
    > unsigned integers where the result may not fit?


    For subtraction, you can pre-test which number is larger:
    bool carryWillOccur = (b>a);
    unsigned c = a-b;

    For multiplication, you need to split each operand in two halfs,
    or rely on the availability of a longer integer number.
    Alternatively, using bit-shifts and additions for each bit
    of one of the operands is often a good approach.

    > Can anybody give me a hint of how to wolve these problems?


    It looks like you might be looking to implement a "big integer"
    library. A number of such libraries exist already, so a web
    search might be worth your time ;)


    > TIA,

    HTH -Ivan

    --
    http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
    Ivan Vecerina, May 1, 2005
    #3
  4. "Ivan Vecerina" <> wrote in message
    news:d51v9v$q0o$...
    > "Edith Gross" <> wrote in message
    > news:p...
    >> I'd like to add to unsigned integers and find out whether a carry occurs.
    >> Can I do that in a simple and fast way?

    > In a portable way, I think the best you can do is:
    > unsigned c = a + b;
    > bool carryOccurred = ( c<a || c<b );

    Of course, it is redundant to perform both tests.
    You could use:
    bool carryOccurred = ( c<b );
    or:
    bool carryOccurred = ( c<a );
    no need for both.
    Ivan Vecerina, May 1, 2005
    #4
  5. Edith Gross

    Edith Gross Guest

    On Sun, 01 May 2005 09:08:43 +0200, Ivan Vecerina wrote:

    > It looks like you might be looking to implement a "big integer"
    > library. A number of such libraries exist already, so a web
    > search might be worth your time ;)


    Thx. It may be funny, but it seems to me, that there is no such library
    (or they are not free). I looked around and googled, but found nothing. Of
    course there are a lot of candidates but at some place they do not work.
    For example CLN does not work, as it is made for Linux. I tried another
    one which was said to have a Windows version but I could not compile it,
    etc.

    Now I use something like this:

    inline unsigned int add(unsigned int a,unsigned int b)
    {
    __asm {
    clc
    cmp overflow,0
    je nulla
    setc
    nulla:
    mov eax,a
    adc eax,b
    mov overflow,0
    jnc nooverflow
    mov overflow,1
    nooverflow:
    }
    }

    but I am not even sure that it works. But this is a specific
    implementation and is OT in this group.
    EG

    ----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
    http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
    ----= East and West-Coast Server Farms - Total Privacy via Encryption =----
    Edith Gross, May 1, 2005
    #5
  6. Edith Gross

    Jerry Coffin Guest

    Edith Gross wrote:

    [ ... arbitrary precision math ]

    > Thx. It may be funny, but it seems to me, that there is no such
    > library (or they are not free).


    There are quite a few that are free in one fashion or another. Some
    that I've used include:

    MIRACL: http://indigo.ie/~mscott/
    Not quite the speed demon they claim it to be, but easy to use.
    Free for non-commercial types of uses.

    NTL: http://www.shoup.net/ntl/
    Big integer capability is more or less a side-item here, but it's
    quite fast and works nicely nonetheless. Distributed under GPL.

    GMP: ftp://ftp.gnu.org/gnu/gmp/ (and many others)
    Quite fast. Builds easily on Linux, with some difficulty with
    MinGW, and AFAIK, not at all with any non-GNU compiler.
    Distributed under GPL.

    apfloat: http://www.apfloat.org/apfloat/
    I've used it only a little, but so far it's been the fastest I've
    tried. Both portable and compiler-specific versions for Borland,
    VC++ and GNU are available. The version specifically for VC++ also
    requires MASM (which you may already have). Freeware.

    Both NTL and apfloat provide high-precision floating point in addition
    to the usual large integers. MIRACL doesn't provide floating point but
    does support rational numbers (i.e. ratios of two large integers) which
    give many of the same capabilities. If you require it to be completely
    free, apfloat is the obvious choice here. If you can live with its
    licensing, I'd probably go for NTL instead -- I find it easier to use
    (though that may be partly because I've used it a lot more).

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, May 1, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David Harmon
    Replies:
    2
    Views:
    2,897
    cplusplus
    Jun 14, 2006
  2. John Cho
    Replies:
    4
    Views:
    673
    cplusplus
    Jun 14, 2006
  3. Tenacious

    Multiplying two doubles

    Tenacious, Jun 2, 2006, in forum: C++
    Replies:
    4
    Views:
    410
    Luke Meyers
    Jun 3, 2006
  4. pozz
    Replies:
    12
    Views:
    719
    Tim Rentsch
    Mar 20, 2011
  5. Haris BogdanoviƦ

    adding, multiplying array

    Haris BogdanoviƦ, Jun 7, 2009, in forum: Ruby
    Replies:
    5
    Views:
    90
    Michael Kohl
    Jun 7, 2009
Loading...

Share This Page