When printing a large integer, the system automatically changed the number without giving error message. What can i do?

Question

Here's the piece of code:

int catalan(int n)
{
    if (n<0){
        return 0;
    }
    if (n<=1){
        return 1;
    }
    int total = 0;
    for(int i=0;i<n;i++)
    {
        total += catalan(i)*catalan(n-i-1);
    }
    return total;
}

int main(int argc, char* argv[])
{
    int res;

    try{
        res = catalan(stoi(argv[1]));
    }catch (const std::out_of_range& e) {
        cout << "Input number out of range.";
        return 0;
    }
    cout<<res<<endl;

    return 0;
}

When I do catalan(20), it should equal to 6,564,120,420, however since the maximum value a signed int can store is 2,147,483,647, the stored result as a signed int will result in an integer overflow and a weird answer '-2025814172'.

I handled the input out of range problem using the try catch, but I don't know how to handle the return value from the recursion function when it is too large. I wanted to print error message for it but not sure how to do that.

signed integer overflow is undefined behavior. [Is signed integer overflow still undefined behavior in C++?](https://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c) and [Allowing signed integer overflows in C/C++](https://stackoverflow.com/questions/4240748/allowing-signed-integer-overflows-in-c-c) — Jason, Feb 06 '23 at 04:16
Which line, exactly, do you expect to throw a `std::out_of_range` exception? Surely not `stoi(argv[1])`, since `20` is comfortably within the range an `int` can hold. But if you expect it to be code from `catalan`, it would be nice if you actually showed that code. — Nathan Pierson, Feb 06 '23 at 04:17
You've shown the `catalan` code. Can you please narrow down the portion of that code you think _might_ throw a `std::out_of_range` exception? I suspect you're expecting that something like `total += catalan(i) * catalan(n - i - 1);` will throw an exception if the values are out of range, but see Jason's links. There is no such guarantee that `*` or `+=` will do that. — Nathan Pierson, Feb 06 '23 at 04:21
You could do each step of the math with 64-bit integers, and throw an exception if the result doesn't fit in a 32-bit integer. — Drew Dormann, Feb 06 '23 at 04:24
@Awakoto *What can i do?* -- This is such a broad question. You can do other things you probably never thought of, such as [doing something like this that uses boost and memoization](https://godbolt.org/z/5eeYMojn3). Note that the value in the result is exactly what you say should be the correct answer. The code is basically identical to your current code, except that the previous calculations of `catalan(n)` are cached in a `std::map`. — PaulMcKenzie, Feb 06 '23 at 04:51
...and that cpp_int is used instead of `int`. Of course, this will make the need for checking for out_of_range not necessary. — PaulMcKenzie, Feb 06 '23 at 04:59

score 0 · Answer 1 · answered Feb 06 '23 at 04:25

You can add these logics before the addition:

if (std::numeric_limits< int_type >::max() / catalan(i) > catalan(n-i-1))
    throw std::out_of_range("overflow")
if (std::numeric_limits< int_type >::max() - catalan(i) * catalan(n-i-1) > total)
    throw std::out_of_range("overflow")

However,this would result in too many recursions, so it's better to store the calculation before these logic. Hence the catalan function would look like this:

int catalan(int n)
{
    int catalan_i;
    int catalan_n_i_1;
    if (n<0){
        return 0;
    }
    if (n<=1){
        return 1;
    }
    int total = 0;
    for(int i=0;i<n;i++)
    {
        catalan_i = catalan(i);
        catalan_n_i_1 = catalan(n-i-1);

        if (std::numeric_limits< int_type >::max() / catalan_i > catalan_n_i_1)
            throw std::out_of_range("overflow")
        if (std::numeric_limits< int_type >::max() - catalan_i * catalan_n_i_1 > total)
            throw std::out_of_range("overflow")
        total += catalan(i)*catalan(n-i-1);
    }
    return total;
}

When printing a large integer, the system automatically changed the number without giving error message. What can i do?

1 Answers1