overflow of cummulative sum

Question

Suppose I want to add 1+11+111....adding n times. It is clear that from a certatin value of n, there may be an overflow of the cummulative sum.

Suppose I use the following very simple function to calcuate the sum above:

int calcSum(int num)
{
    int sum = 0, sequnt = 1, i;

    for (i = 0; i < num; i++)
    {
        sum += sequnt;
        sequnt = (sequnt * 10) + 1;
    }

    return sum;
}

To that function I want to add a check for overflowing.

I have tried to get some help here How to check if a number overflows an 'int'

but I have to admit it made me confused, and I still find some difficulties with implementing it in my task.

Any help would be appreaciated.

Answer 1

Simply use INT_MAX from limits.h

int calcSum(int num)
{
    int sum = 0, sequnt = 1, i;

    for (i = 0; i < num; i++)
    {
        if (INT_MAX - sequnt < sum) exit(1); // overflow
        sum += sequnt;
        if (INT_MAX/10 <= sequnt) exit(1); // overflow on the two next sentences.
        sequnt *= 10;
        sequnt++;
    }

    return sum;
}

The exit(1) is just to make the example short. You can add whatever error handling that you like.

Answer 2

As either of the 2 additions or multiplication are roughly overflow candidates, call a safe overflow checker for each. Use constants in <limits.h> to guide range checking.

#include <limits.h>
int is_undefined_add(int a, int b) {
  return (a < 0) ? (b < INT_MIN - a) : (b > INT_MAX - a);
}

int is_undefined_mult(int a, int b) {
  if (a > 0) {
    if (b > 0) {
      return a > INT_MAX / b;       // a positive, b positive
    }
    return b < INT_MIN / a;         // a positive, b not positive
  }
  if (b > 0) {
    return a < INT_MIN / b;         // a not positive, b positive
  }
  return a != 0 && b < INT_MAX / a; // a not positive, b not positive
}

int calcSum(int num) {
  int sum = 0, sequnt = 1, i;

  for (i = 0; i < num; i++) {
    if (is_undefined_add(sum, sequnt) Handle_Overflow();
    sum += sequnt;

    if (is_undefined_mult(sequnt, 10) Handle_Overflow();
    sequnt *= 10;

    if (is_undefined_add(sequnt, 1) Handle_Overflow();
    sequnt++;
  }

  return sum;
}

---

is_undefined_add() and is_undefined_mult() are valid for all combinations of int a, int b.

Answer 3

If you are sure you are using two's complement signed integers, then you can check the following: Two positive numbers added must give a positive result and two negative numbers added must give a negative result. It's impossible in only one sum to get two overflows, so if you are adding positive numbers, an overflow will arrive when your result is negative for the first time.

Either case, if you want your code to be portable, then the recommendation is to do something similar to this:

#include <limits.h>
...
    if ((a > 0 && b > 0 && MAX_INT - a > b) ||
        (a < 0 && b < 0 && MIN_INT - a < b)) {
        /* OVERFLOW OF a + b WILL OCCUR */
        ...
    }

if signs of operands are different it is impossible for a + b to be greater than a or b in absolute value, so it is impossible for an overflow to happen.

For unsigneds you have a similar approach (while you save half of the test, as operands can be only positive) but this time the first way is valid always (as standard says unsigned addition is considered a sum module 2^n where n is the wordsize in bits) and in that case you can make the sum and later check if the result is less than any of the operands (if both are positive, sum must be larger than or equal than any of the operands):

unsigned a, b;

...
unsigned sum = a + b;
if (sum < a || sum < b) {
    /* OVERFLOW ON a + b HAS HAPPENED */
    ...
}

You have also to check for integer multiplication overflow. If a and b are to be multiplied, then a*b can overflow. But this time the problem goes further, as overflow can occur more than once, and you cannot do it a posteriori. In that case you can have overflow with equal or different signs, as you are adding a times b (and b has the same sign as itself) if both signs are equal the product will be positive, and overflows will occur

if (MAX_INT/b < a) { /* overflow */ }

if signs are different, the product should be negative, and then

if (MIN_INT/b < a) { /* overflow */ }

if one of the numbers is 0, then no overflow occurs on multipliying, as the result is 0.