How to handle when a factorial gets too big for int in C++?

Question

I have this recursive function for finding factorial, but I don't know how to modify it to throw an error when the factorial gets too big for int.

If my function was iterative, I could just put in an if-statement, checking if the factorial was 0 or less each time through, thereby finding where the overflow occurred, but this doesn't seem feasible for the recursive definition.

int factorial(int x)
{
    if (x < 0) error("Can't take factorial of a negative number.");
    else if (x == 0) return 1;
    else return x * factorial(x - 1);
}

If for example, I call the function with 50, it will return 0. I would like to throw an error message in cases like this. Could anyone straighten me out on this?

"_if the factorial was 0 or less each time through, thereby finding where the overflow occurred_" signed integer overflow is undefined behavior (even if it weren't - it could, theoretically, overflow from one positive integer, to another positive integer). — Algirdas Preidžius, May 28 '19 at 14:44
Just check if `x` is too big. 12! is the largest factorial that can be stored in a 32 bit int so just check if `x` is larger than 12. — NathanOliver, May 28 '19 at 14:44
To add to Nathan's you can use unsigned long long and then you can store up to 20!. — Michael Chourdakis, May 28 '19 at 14:48
The max size of an `int` is known, just like the size of a `long`. On your final else, instead of returning the value immediately, store it into a `long`, check if it's bigger than `int` max, and error accordingly or continue recursion. — jwatts1980, May 28 '19 at 14:51
@jwatts1980 That will only work on 64 bit *Nix machines. Windows still uses 32 bit longs. There can also be systems where `sizeof(int) == sizeof(long) == sizeof(long long)` so it would not work in those systems as well. — NathanOliver, May 28 '19 at 14:54
@NathanOliver for such systems all types would be 64 bit wide so it would "work" in a sense. — Dan M., May 28 '19 at 14:56
@DanM. How would it "work"? The result would never be larger than `INT_MAX`. — NathanOliver, May 28 '19 at 14:57
@NathanOliver ah, sorry, misread the comment you were replying to and assumed you were talking about factorials fitting into integers, You can detect overflow with unsigned types if you want, But it doesn't make much sense. — Dan M., May 28 '19 at 15:00
Why write such a crappy recursive function anyways? There is method that unrolls such recursive functions into loops, but yours won't. — ALX23z, May 28 '19 at 15:18

score 1 · Accepted Answer · answered May 28 '19 at 15:20

1

The factorial function is a static function whose output will always be the same, given the same input. Therefore, we can know in advance whether a given input will overflow or not.

int32_t factorial(int32_t val) {
    if(val > 12)
        throw std::runtime_error("Input too large for Factorial function (val must be less than 13)");
    if(val < 0)
        throw std::runtime_error("Input must be non-negative");
    if(val == 0)
        return 1;
    return factorial(val-1) * val;
}

int64_t factorial(int64_t val) {
    if(val > 20)
        throw std::runtime_error("Input too large for Factorial function (val must be less than 21)");
    if(val < 0)
        throw std::runtime_error("Input must be non-negative");
    if(val == 0)
        return 1;
    return factorial(val-1) * val;
}

If you'd like to instead detect integer overflow dynamically, you'll need to review rigorous methods for detecting possible overflow.

answered May 28 '19 at 15:20

Xirema

19,889
4
32
68

Thank you, I didn't realize I should just check the value before taking factorial. – Daniel May 28 '19 at 15:41
1

Of course you may not want to do the check every step/loop through the recursion, but then you might not want to do recursion. – Gem Taylor May 28 '19 at 15:58
A more general check involves taking MAX_INT and dividing by one of the factors, then checking if the result is less than the other factor, but this comes at the price of doing a divide. – Gem Taylor May 28 '19 at 15:59
@GemTaylor On a function this simple, I trust the compiler to find a way to optimize the logic. – Xirema May 28 '19 at 15:59
A faster check involves first checking if the two values to be multiplied cross a bit threshold. Number of bits in one plus bits in the other < the target bit size (31 or 63 for signed) => all good; greater => all bad; equal, then you might have to do the divide. – Gem Taylor May 28 '19 at 16:03

How to handle when a factorial gets too big for int in C++?

1 Answers1