print condition while integer overflow not working

Question

#include <iostream>

using namespace std;

int getFectorial(int n)
{
    int ans = 1;
    for (int i = n; i >= 1; i--)
    {
        ans = ans * i;
    }

    return ans;
}

int printNcr(int n, int r)
{
    if (getFectorial(n) > INT_MAX)
    {
        return 0;
    }
    return (getFectorial(n)) / ((getFectorial(r)) * (getFectorial(n - r)));
}

int main()
{
    int n = 14;
    for (int row = 0; row < n; row++)
    {
        for (int col = 0; col < row + 1; col++)
        {
            cout << printNcr(row, col) << " ";
        }

        cout << endl;
    }

    return 0;
}

When I give value of n more than 13th I want integer overflow condition should be working that given in printNcr() function, but it's not working and all line after 13th are printing wrong values instead of returning false.

How to make given INT_MAX condition work?

its not easy to detect signed overflow, once you overflow the product goes negative, but then it flips positive then negative. You can use unsigned instead but detecting overflow there is a mess too - see https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-overflow — pm100, Apr 26 '22 at 19:01

chux - Reinstate Monica · Accepted Answer · 2022-04-27T16:45:49.480

int oveflow cannot be reliably detected after it happens.

One way to detect upcoming int overflow in factorial:

int getFactorial(int n) {
  if (n <= 0) {
    return 1; // and maybe other code when n < 0
  }
  int limit = INT_MAX/n;
  int ans = 1;
  for (int i = 2; i <= n; i++) {
    if (ans >= limit) {
      return INT_MAX; // Or some other code
    }
    ans = ans * i;
  }
  return ans;
}

Another way is at startup, perform a one-time calculation for maximum n. With common 32-bit int, that limit is 12.

int getFactorial(int n) {
  if (n > getFactorial_pre_calculated_limit) {
    return INT_MAX;
  }
  ...

pm100 · Answer 2 · 2022-04-27T16:28:22.060

1

You can detect overflow by watching for negative value

int getFectorial(int n)
{
    int ans = 1;
    for (int i = n; i >= 1; i--)
    {
        ans = ans * i;
        if (ans < 0) <<<<======
            return -1;
    }

    return ans;
}

then

int printNcr(int n, int r)
{
    if (getFectorial(n) < 0)
    {
        return 0;
    }
    return (getFectorial(n)) / ((getFectorial(r)) * (getFectorial(n - r)));
}

Please note though that strictly speaking this is undefined behavior. It would be better to simply fail if you know the result is going to be too big (Ie n > 13)

Or better do it like this

int getFectorial(int n)
{
    long long ans = 1; <<<====
    for (int i = n; i >= 1; i--)
    {
        ans = ans * i;
        if (ans >INT_MAX) <<<<======
            return -1;
    }

    return (int)ans;
}

or you could throw std::overflow_error

BTW the word is factorial not fectorial

edited Apr 27 '22 at 16:28

answered Apr 26 '22 at 20:05

pm100

48,078
23
82
145

1

I would probably just update `getFectorial()` to `throw` an exception on overflow, no need to check the result on exit. – Remy Lebeau Apr 26 '22 at 20:10
1

I thought signed integer overflow [was undefined behavior](https://stackoverflow.com/q/16188263/10077). – Fred Larson Apr 26 '22 at 20:11
@FredLarson - yup, updated answer – pm100 Apr 26 '22 at 20:14
@pm100 Is `int` overflow _undefined behavior_ or is it specified to invoke `std::overflow_error`? – chux - Reinstate Monica Apr 27 '22 at 16:44
Off by 1 "going to be too big (Ie n > 13)" --> "(Ie n > 12)". – chux - Reinstate Monica Apr 27 '22 at 16:45
"if (ans < 0)" fails for 2 reasons: 1) `int` overflow is certainty UB 2) Typical result of `int` `ans * i` overflow is a truncated lower 32-bit response. In the case of 13! (which is 6227020800), the result is 1932053504. Looking for `ans < 0`, at best, detects half of the multiplication overflows. – chux - Reinstate Monica Apr 27 '22 at 16:57

print condition while integer overflow not working

2 Answers2