integer overflow

Discussion in 'C Programming' started by Ashutosh Iddya, Apr 16, 2004.

  1. Hi ,

    I am performing an integer count of a particular operation in my program.
    After a sufficiently large value an overflow occurs. At the moment I have
    gone around the problem by declaring it as a double, even that has its
    limits. Is there a method of preventing this overflow or some method of
    recovering from it. Any help in this regard would be greatly appreciated.

    Thanking you.

    Ashutosh
    Ashutosh Iddya, Apr 16, 2004
    #1
    1. Advertising

  2. Ashutosh Iddya

    CBFalconer Guest

    Ashutosh Iddya wrote:
    >
    > I am performing an integer count of a particular operation in my
    > program. After a sufficiently large value an overflow occurs. At
    > the moment I have gone around the problem by declaring it as a
    > double, even that has its limits. Is there a method of preventing
    > this overflow or some method of recovering from it. Any help in
    > this regard would be greatly appreciated.


    If long won't do, then you can use long long (on C99 or gnu gcc
    systems). Otherwise try:

    if (n < INT_MAX) n++;
    else {
    overflows++;
    n = 0;
    }

    and don't forget to #include <limits.h>

    It would be simpler to use unsigned types, and then:

    if (!(++n)) overflow++;

    --
    A: Because it fouls the order in which people normally read text.
    Q: Why is top-posting such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    CBFalconer, Apr 16, 2004
    #2
    1. Advertising

  3. thanks for that. I will try it out and let you know how it went
    Ashutosh
    "CBFalconer" <> wrote in message
    news:...
    > Ashutosh Iddya wrote:
    > >
    > > I am performing an integer count of a particular operation in my
    > > program. After a sufficiently large value an overflow occurs. At
    > > the moment I have gone around the problem by declaring it as a
    > > double, even that has its limits. Is there a method of preventing
    > > this overflow or some method of recovering from it. Any help in
    > > this regard would be greatly appreciated.

    >
    > If long won't do, then you can use long long (on C99 or gnu gcc
    > systems). Otherwise try:
    >
    > if (n < INT_MAX) n++;
    > else {
    > overflows++;
    > n = 0;
    > }
    >
    > and don't forget to #include <limits.h>
    >
    > It would be simpler to use unsigned types, and then:
    >
    > if (!(++n)) overflow++;
    >
    > --
    > A: Because it fouls the order in which people normally read text.
    > Q: Why is top-posting such a bad thing?
    > A: Top-posting.
    > Q: What is the most annoying thing on usenet and in e-mail?
    >
    Ashutosh Iddya, Apr 16, 2004
    #3
  4. On Fri, 16 Apr 2004, Ashutosh Iddya wrote:

    > Hi ,
    >
    > I am performing an integer count of a particular operation in my program.
    > After a sufficiently large value an overflow occurs. At the moment I have
    > gone around the problem by declaring it as a double, even that has its
    > limits. Is there a method of preventing this overflow or some method of
    > recovering from it. Any help in this regard would be greatly appreciated.


    If overflow is happening with your data type you could detect it but
    preventing it means switching to a different data type. For an integer
    data type (long long) is your best bet. If you are only working with
    unsigned numbers then (unsigned long long) is your best bet.

    You might still get overflow. If this is the case you can try using double
    as your data type. Another option is to search the web for "big number C
    library". There are libraries you can use for numbers bigger than unsigned
    long long.

    If you go with the big number library it will probably be slower than
    using long long. You might me able to create your own limited big number
    library. If you are just counting then you only need addition and some way
    of printing the number.

    --
    Send e-mail to: darrell at cs dot toronto dot edu
    Don't send e-mail to
    Darrell Grainger, Apr 16, 2004
    #4
  5. Ashutosh Iddya

    Dan Pop Guest

    In <407fba3a$0$16582$> "Ashutosh Iddya" <> writes:

    >I am performing an integer count of a particular operation in my program.
    >After a sufficiently large value an overflow occurs. At the moment I have
    >gone around the problem by declaring it as a double, even that has its
    >limits.


    I have a hard time imagining you're going to reach the limits of the
    double solution within a reasonable period of time, even if all you
    do is counting. Try the following program and see how long it takes
    to terminate normally.

    #include <stdio.h>

    int main()
    {
    double d = 0;
    while (d + 1 != d) d++;
    printf("%.16f\n", d);
    return 0;
    }

    Assumming that the loop takes one CPU cycle per iteration and that the CPU
    is running at 4.5 GHz, this proggie should run for about 1e6 seconds, if
    using IEEE-754 doubles.

    BTW, how about "optimising" the while loop like this?

    while (d != ++d) ;

    ;-)

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
    Dan Pop, Apr 16, 2004
    #5
  6. Ashutosh Iddya

    Dan Pop Guest

    In <> (Darrell Grainger) writes:

    >On Fri, 16 Apr 2004, Ashutosh Iddya wrote:
    >
    >> I am performing an integer count of a particular operation in my program.
    >> After a sufficiently large value an overflow occurs. At the moment I have
    >> gone around the problem by declaring it as a double, even that has its
    >> limits. Is there a method of preventing this overflow or some method of
    >> recovering from it. Any help in this regard would be greatly appreciated.

    >
    >If overflow is happening with your data type you could detect it but
    >preventing it means switching to a different data type. For an integer
    >data type (long long) is your best bet. If you are only working with
    >unsigned numbers then (unsigned long long) is your best bet.


    Unless your C compiler, invoked in conforming mode, tells you that
    "long long" is a syntax error ;-)

    Are the latest Microsoft C compilers supporting long long?

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
    Dan Pop, Apr 16, 2004
    #6
  7. Ashutosh Iddya

    Grumble Guest

    Darrell Grainger wrote:

    > On Fri, 16 Apr 2004, Ashutosh Iddya wrote:
    >
    >> I am performing an integer count of a particular operation in my program.
    >> After a sufficiently large value an overflow occurs. At the moment I have
    >> gone around the problem by declaring it as a double, even that has its
    >> limits. Is there a method of preventing this overflow or some method of
    >> recovering from it. Any help in this regard would be greatly appreciated.

    >
    > If overflow is happening with your data type you could detect it but
    > preventing it means switching to a different data type. For an integer
    > data type (long long) is your best bet. If you are only working with
    > unsigned numbers then (unsigned long long) is your best bet.
    >
    > You might still get overflow.


    C99's long long int is /at least/ 64 bits wide.

    If the OP's counter were incremented 100 times every cycle on a 10 GHz
    processor, it would take 213 days for the counter to overflow.

    > If this is the case you can try using double as your data type.


    Bad advice.

    An IEEE 754 double will only provide 53 bits of precision.

    See DBL_MANT_DIG and FLT_RADIX in float.h

    For my information, are there implementations where double is wider
    than 64 bits?
    Grumble, Apr 16, 2004
    #7
  8. Ashutosh Iddya

    Eric Sosman Guest

    Grumble wrote:
    > [...]
    > For my information, are there implementations where double is wider
    > than 64 bits?


    VAX H-format floating point had/has 128 bits; I don't recall
    how they're divided up between exponent and fraction. Also,
    when I was working with VAXen the C implementations were not
    able to use H-format. (For the curious: `float' used the
    32-bit F-format, and `double' used either D-format or G-format,
    both 64 bits, at your option -- and if you accidentally mixed
    G's and D's ... "The horror! The horror!")

    --
    Eric Sosman, Apr 16, 2004
    #8
  9. Ashutosh Iddya

    CBFalconer Guest

    Ashutosh Iddya wrote:
    >
    > thanks for that. I will try it out and let you know how it went


    Kindly DO NOT toppost. See sig.

    --
    A: Because it fouls the order in which people normally read text.
    Q: Why is top-posting such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    CBFalconer, Apr 16, 2004
    #9
  10. On Fri, 16 Apr 2004, Grumble wrote:

    > Darrell Grainger wrote:
    >
    > > On Fri, 16 Apr 2004, Ashutosh Iddya wrote:
    > >
    > >> I am performing an integer count of a particular operation in my program.
    > >> After a sufficiently large value an overflow occurs. At the moment I have
    > >> gone around the problem by declaring it as a double, even that has its
    > >> limits. Is there a method of preventing this overflow or some method of
    > >> recovering from it. Any help in this regard would be greatly appreciated.

    > >
    > > If overflow is happening with your data type you could detect it but
    > > preventing it means switching to a different data type. For an integer
    > > data type (long long) is your best bet. If you are only working with
    > > unsigned numbers then (unsigned long long) is your best bet.
    > >
    > > You might still get overflow.

    >
    > C99's long long int is /at least/ 64 bits wide.


    I'd doubt the OP was using a C99 compiler. It is possible but my first
    assumption would be a C89 compiler.

    > If the OP's counter were incremented 100 times every cycle on a 10 GHz
    > processor, it would take 213 days for the counter to overflow.


    Man, slow day and my brain shuts down. Just a month ago I proved that
    overflow on a cycle count profiler for a 1 GHz processor would take over
    500 years to occur. I should have realized this.

    > > If this is the case you can try using double as your data type.

    >
    > Bad advice.
    >
    > An IEEE 754 double will only provide 53 bits of precision.
    >
    > See DBL_MANT_DIG and FLT_RADIX in float.h


    I was thinking more of situations when (long long) would be 32 bit. On
    older compilers I remember seeing support for (long long) such that
    sizeof(long) == sizeof(long long). Essentially they made it so source with
    (long long) would not be considered a syntax error but still only
    supported 32 bit integers.

    > For my information, are there implementations where double is wider
    > than 64 bits?


    Not that I have seen.

    --
    Send e-mail to: darrell at cs dot toronto dot edu
    Don't send e-mail to
    Darrell Grainger, Apr 16, 2004
    #10
  11. "Ashutosh Iddya" <> writes:
    > I am performing an integer count of a particular operation in my program.
    > After a sufficiently large value an overflow occurs. At the moment I have
    > gone around the problem by declaring it as a double, even that has its
    > limits. Is there a method of preventing this overflow or some method of
    > recovering from it. Any help in this regard would be greatly appreciated.


    Using double is probably the wrong solution. If you repeatedly add 1
    to a double variable, you'll never get an overflow, just a loss of
    precision; eventually, (d + 1.0 == d).

    The type "long long" is guaranteed to be at least 64 bits, which
    should be more than enough for whatever it is you're counting. This
    type is new in C99, but many C90 compilers support it as an extension.
    (Since the C90 standard doesn't specify "long long", it's
    theoretically possible that a C90 compiler could provide a "long long"
    type that's smaller than 64 bits, but I don't think anyone has ever
    done that.)

    If 32 bits is enough, use long (or unsigned long).

    If 32 bits isn't enough, and you don't care about portability to
    systems that don't support long long, use long long (or
    unsigned long long).

    Be aware that a C90 implementation that supports long long as an
    extension may not necessarily support everything that goes with it,
    particularly the printf formats.

    If you can't use long long, you might try using a pair of unsigned
    longs (untested code follows):

    unsigned long count_hi = 0;
    unsigned long count_lo = 0;
    ...
    for (...) {
    count_lo ++;
    if (count_lo == 0) count_hi ++;
    }

    Note the use of unsigned types. Overflow is well-defined for unsigned
    types; it wraps around. Overflow for signed types causes undefined
    behavior; wraparound is common, but not guaranteed.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
    Keith Thompson, Apr 16, 2004
    #11
  12. Ashutosh Iddya

    jacob navia Guest

    "Grumble" <> a écrit dans le message de
    news:c5otk9$3aq$...
    > Darrell Grainger wrote:
    >
    > For my information, are there implementations where double is wider
    > than 64 bits?
    >


    There is the standard long double for that.
    In lcc-win32 long double is 80 bits.

    Then, you have the qfloat with 350 bits if you
    really want big precision.

    After that, the bignums is the only way, or
    (much better) to look at the algorithm and
    see why it is overflowing :)

    http://www.cs.virginia.edu/~lcc-win32
    jacob navia, Apr 16, 2004
    #12
  13. Grumble <> writes:
    [...]
    > For my information, are there implementations where double is wider
    > than 64 bits?


    The standard allows it, but I doubt that any implementations actually
    do so. If you have a floating-point type wider than 64 bits, you're
    more likely to call it "long double" (which has been valid at least
    since the C89/C90 standard).

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
    Keith Thompson, Apr 16, 2004
    #13
  14. (Darrell Grainger) writes:
    [...]
    > I was thinking more of situations when (long long) would be 32 bit. On
    > older compilers I remember seeing support for (long long) such that
    > sizeof(long) == sizeof(long long). Essentially they made it so source with
    > (long long) would not be considered a syntax error but still only
    > supported 32 bit integers.


    Ick!

    Can you remember which compiler did this? Did it really implement
    "long long" as a distinct type, or did it just allow the "long"
    keyword to be repeated with no further effect (so "long", "long long",
    and "long long long" would all be equivalent)?

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
    Keith Thompson, Apr 16, 2004
    #14
  15. "Ashutosh Iddya" <> wrote in message
    news:407fba3a$0$16582$...
    > Hi ,
    >
    > I am performing an integer count of a particular operation in my program.
    > After a sufficiently large value an overflow occurs. At the moment I have
    > gone around the problem by declaring it as a double, even that has its
    > limits. Is there a method of preventing this overflow or some method of
    > recovering from it. Any help in this regard would be greatly appreciated.


    unsigned long counter[2] = { 0 };

    for (;;)
    {
    if (++counter[0] && ++counter[1])
    puts("64+ bit counter overflowed!");
    }

    This is trivially extendable to as much precision as you want. But if you need a counter
    bigger than a minimum of 64-bits, then I'd love to know what machine you're using and
    where I can pick one up!

    --
    Peter
    Peter Nilsson, Apr 17, 2004
    #15
  16. On Sat, 17 Apr 2004, Peter Nilsson wrote:
    >
    > "Ashutosh Iddya" <> wrote...
    > >
    > > I am performing an integer count of a particular operation in my program.
    > > After a sufficiently large value an overflow occurs. At the moment I have
    > > gone around the problem by declaring it as a double, even that has its
    > > limits. Is there a method of preventing this overflow or some method of
    > > recovering from it. Any help in this regard would be greatly appreciated.

    >
    > unsigned long counter[2] = { 0 };
    >
    > for (;;)
    > {
    > if (++counter[0] && ++counter[1])


    ITYM if (!(++counter[0] || ++counter[1]))

    You want to make sure they both *don't* go back to zero at once.

    > puts("64+ bit counter overflowed!");
    > }


    -Arthur
    Arthur J. O'Dwyer, Apr 17, 2004
    #16
  17. "Arthur J. O'Dwyer" <> wrote in message
    news:p...
    >
    > On Sat, 17 Apr 2004, Peter Nilsson wrote:
    > >
    > > "Ashutosh Iddya" <> wrote...
    > > >
    > > > I am performing an integer count of a particular operation in my
    > > > program. After a sufficiently large value an overflow occurs. At
    > > > the moment I have gone around the problem by declaring it as a
    > > > double, even that has its limits. Is there a method of preventing
    > > > this overflow or some method of recovering from it. Any help in
    > > > this regard would be greatly appreciated.

    > >
    > > unsigned long counter[2] = { 0 };
    > >
    > > for (;;)
    > > {
    > > if (++counter[0] && ++counter[1])

    >
    > ITYM if (!(++counter[0] || ++counter[1]))


    Or...

    if (++counter[0] == 0 && ++count[1] == 0)

    >
    > You want to make sure they both *don't* go back to zero at once.


    Yup, my bad. Thanks.

    --
    Peter
    Peter Nilsson, Apr 17, 2004
    #17
  18. Ashutosh Iddya

    Dan Pop Guest

    In <> (Darrell Grainger) writes:

    >I was thinking more of situations when (long long) would be 32 bit.


    No such thing. With 32-bit int and long, no point in adding a 32-bit
    long long.

    >On older compilers I remember seeing support for (long long) such that
    >sizeof(long) == sizeof(long long).


    True, but those were compilers with 64-bit long's (e.g. the Digital Unix
    compilers as well as gcc on any 64-bit Linux flavour).

    >Essentially they made it so source with
    >(long long) would not be considered a syntax error but still only
    >supported 32 bit integers.


    A brain dead idea: the code will compile but silently generate wrong
    results, because people using long long *really* expect more than 32 bits
    (otherwise they would be using long in the first place).

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
    Dan Pop, Apr 19, 2004
    #18
  19. Ashutosh Iddya

    Dan Pop Guest

    In <> Eric Sosman <> writes:

    >Grumble wrote:
    >> [...]
    >> For my information, are there implementations where double is wider
    >> than 64 bits? ^^^^^^

    >
    > VAX H-format floating point had/has 128 bits; I don't recall
    >how they're divided up between exponent and fraction. Also,
    >when I was working with VAXen the C implementations were not
    >able to use H-format.


    So, you're providing a non-example. long double would have been the
    right type for the VAX H_FLOAT type, but I don't know if any VAX C
    compiler actually supported it. VAX FORTRAN did support it as REAL*16.

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
    Dan Pop, Apr 19, 2004
    #19
  20. Ashutosh Iddya

    Dan Pop Guest

    In <> Keith Thompson <> writes:

    >"Ashutosh Iddya" <> writes:
    >> I am performing an integer count of a particular operation in my program.
    >> After a sufficiently large value an overflow occurs. At the moment I have
    >> gone around the problem by declaring it as a double, even that has its
    >> limits. Is there a method of preventing this overflow or some method of
    >> recovering from it. Any help in this regard would be greatly appreciated.

    >
    >Using double is probably the wrong solution. If you repeatedly add 1
    >to a double variable, you'll never get an overflow, just a loss of
    >precision; eventually, (d + 1.0 == d).


    No loss of precision until d + 1.0 == d, and the point where this happens
    can be detected. On typical implementation, this should be around 2 ** 53
    which should be enough for most applications needing to count something.

    >The type "long long" is guaranteed to be at least 64 bits, which
    >should be more than enough for whatever it is you're counting. This
    >type is new in C99, but many C90 compilers support it as an extension.


    Not that many out of the Unix world. They typically support a 64-bit
    integer type, but give it a name in the implementation name space. Even
    on 64-bit hardware...

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
    Dan Pop, Apr 19, 2004
    #20
    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. bartek
    Replies:
    3
    Views:
    3,090
    bartek
    Feb 6, 2004
  2. John Black
    Replies:
    1
    Views:
    4,507
    John Harrison
    Apr 15, 2004
  3. deancoo

    integer or long overflow...

    deancoo, Mar 5, 2005, in forum: C++
    Replies:
    11
    Views:
    763
    Pete Becker
    Mar 5, 2005
  4. Enrico 'Trippo' Porreca

    Integer overflow

    Enrico 'Trippo' Porreca, Aug 21, 2003, in forum: C Programming
    Replies:
    9
    Views:
    413
  5. Vivek Mohan

    Integer overflow in expression

    Vivek Mohan, May 5, 2004, in forum: C Programming
    Replies:
    7
    Views:
    8,652
    Richard Bos
    May 6, 2004
Loading...

Share This Page