unsigned __int64 overflow problem

Discussion in 'C++' started by Vivi, Aug 25, 2003.

  1. Vivi

    Vivi Guest

    I am trying to find an elegant solution for the "unsigned __int64
    overflow problem" or in general an "unsigned int overflow detection
    problem". In particular, I just have written a little program that
    calculates "aliquot sequences" using unsigned __int64. That gives me
    integers up to 19 digits and that's all I need for now, but the
    sequences often grow fast beyond the _UI64_MAX (maximum value of
    __int64) and in that case, the __int64 variables assume incorrect
    values (pretty much, garbage).

    I was wondering if there is an elegant way, not crucially affecting
    the calculation speed, of detecting if an unsigned __int64 (or any
    other unsigned int) variable "got over the limit".

    Thanks, Vivi
    Vivi, Aug 25, 2003
    #1
    1. Advertising

  2. Vivi

    Jack Klein Guest

    On 24 Aug 2003 22:46:30 -0700, (Vivi) wrote in
    comp.lang.c++:

    > I am trying to find an elegant solution for the "unsigned __int64
    > overflow problem" or in general an "unsigned int overflow detection
    > problem". In particular, I just have written a little program that
    > calculates "aliquot sequences" using unsigned __int64. That gives me
    > integers up to 19 digits and that's all I need for now, but the
    > sequences often grow fast beyond the _UI64_MAX (maximum value of
    > __int64) and in that case, the __int64 variables assume incorrect
    > values (pretty much, garbage).
    >
    > I was wondering if there is an elegant way, not crucially affecting
    > the calculation speed, of detecting if an unsigned __int64 (or any
    > other unsigned int) variable "got over the limit".
    >
    > Thanks, Vivi


    Note that __int64 is not a standard C++ data type. It is an
    acceptable representation for the C "long long" type which will
    probably be added to the next version of the C++ standard, but for now
    it is not a part of the language.

    If/when "long long" is added to the C++ language, the unsigned version
    will have exactly the same behavior as all of the other C and C++
    unsigned types. Specifically, they can't overflow. If a calculation
    or conversion produces a value outside the range of the unsigned type,
    it is modified by repeatedly adding or subtracting one mare than the
    type's maximum value until it is within range. This required behavior
    is well-defined and guaranteed.

    Essentially, that means you get the low 64 bits of the result, any
    carry to higher bits is merely discarded.

    As to whether or not you can detect this after the fact, you can do
    this fairly easily for addition and subtraction for the unsigned
    types:

    Given any unsigned integer type UIT:

    UIT u1, u2;

    /* some values assigned to u1 and u2 */

    /* want to add u2 to u1 unless it will overflow */
    if (u1 + u2 < u1)
    {
    /* will overflow, do something */
    }
    else
    {
    /* won't overflow, OK to continue */
    u1 += u2;
    }

    Likewise for subtraction:

    if (u1 - u2 > u1)
    {
    /* would underflow */
    }
    else
    {
    u1 -= u2;
    }

    Off the top of my head, I think you must pre-test for division, using
    UIT_MAX from <climits>:

    if (UIT_MAX / u2 < u1)
    {
    /* u1 * u2 will wrap */
    }
    else
    {
    u1 *= u2;
    }

    As to how long that takes, and whether or not it crucially affects the
    calculation speed, only you can determine that.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c /faq
    Jack Klein, Aug 25, 2003
    #2
    1. Advertising

  3. Vivi

    ES Kim Guest

    "Vivi" <> wrote in message
    news:...
    > I am trying to find an elegant solution for the "unsigned __int64
    > overflow problem" or in general an "unsigned int overflow detection
    > problem". In particular, I just have written a little program that
    > calculates "aliquot sequences" using unsigned __int64. That gives me
    > integers up to 19 digits and that's all I need for now, but the
    > sequences often grow fast beyond the _UI64_MAX (maximum value of
    > __int64) and in that case, the __int64 variables assume incorrect
    > values (pretty much, garbage).
    >
    > I was wondering if there is an elegant way, not crucially affecting
    > the calculation speed, of detecting if an unsigned __int64 (or any
    > other unsigned int) variable "got over the limit".
    >
    > Thanks, Vivi


    A natural way would be to check if it overfloww before
    you actually carry out the operation.
    If you are concerned about only in unsigned integers,

    1. addition
    Check if a + b > _UI64_MAX, ie, a > _UI64_MAX - b
    If so, it's overflow.

    2. subtraction
    Check if the second operand is greater than the first.

    3. multiplication
    Check if a * b > _UI64_MAX, ie, a > _UI64_MAX / b
    If so, it's overflow. Oh, you must check if b is 0 first.

    4. division
    Nothing to worry about if the second operand is not 0.

    Is this elegant and effecient? Well... it's upon you.

    --
    ES Kim
    ES Kim, Aug 25, 2003
    #3
    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. John Tsiombikas (Nuclear / the Lab)

    Re: Different results if compared as double or __int64?

    John Tsiombikas (Nuclear / the Lab), Jun 30, 2003, in forum: C++
    Replies:
    1
    Views:
    424
    Victor Bazarov
    Jun 30, 2003
  2. Tim Clacy

    __int64 vs. long long

    Tim Clacy, Nov 10, 2003, in forum: C++
    Replies:
    8
    Views:
    821
    Rolf Magnus
    Nov 10, 2003
  3. JR
    Replies:
    3
    Views:
    376
    Xenos
    Feb 5, 2004
  4. Matt Whelan

    SWIG and __int64

    Matt Whelan, Aug 14, 2003, in forum: Python
    Replies:
    2
    Views:
    550
    Matt Whelan
    Aug 15, 2003
  5. pozz
    Replies:
    12
    Views:
    731
    Tim Rentsch
    Mar 20, 2011
Loading...

Share This Page