Why does this factorial function break after a certain point?

Question

So I have this factorial function written in C:

unsigned int factorial(unsigned int n){
        int fn = 1;

        if(n == 0 || n == 1){
                return 1;
        } else{
                for(int i = 1; i <= n; i++){
                        fn *= i;
                }
        }

        return fn;
}

I tested it out with smaller numbers like 5 and it worked. Then I put it into this loop:

for(int i = 0; i < 100; i++){
                printf("\n%d! = %d", i, factorial(i));
        }

When i reaches 17, the factorial is apparently -288522240 which is obviously wrong. These kinds of answers continue until i reaches 34 and it says that the factorial is 0. It then does this for the rest of the numbers.

I don't understand what's wrong with my code. I see no reason for the number to become negative or 0. What's happened here?

Every numerical type in C has a certain range of values it can contain. — Eugene Sh., Feb 11 '20 at 19:02
`unsigned int` is most likely a 32-bit integer. Those factorials get really big really quickly. — DeiDei, Feb 11 '20 at 19:02
Factorial of 100 is a 185-digit number. I doubt your ints are that big. — Lee Daniel Crocker, Feb 11 '20 at 19:22
If you're doing this as a homework assignment, learning about the limits of integer types is probably one of the goals. — Caleb, Feb 11 '20 at 19:30
Factorials up to 12! fit into a 32-bit integer. Factorials up to 20! fit into a 64-bit integer. After that, you've run out of bits on most machines. However, 34! fits into an unsigned 128-bit integer, 57! fits into a 256-bit integer, and 98! fits into an unsigned 512-bit integer. — Jonathan Leffler, Feb 11 '20 at 22:30

chux - Reinstate Monica · Answer 1 · 2020-02-12T13:11:15.933

100! or 9.3326...E+157 or 9332621544394415268169923885626670049071596826438162146859296389521759999322991560894146397615651828625369792082722375825118521091686400000000000000000000000, a 525 bit number, is outside the range of int - likely 32-bit [-2147483648 ... 2147483647]

Signed integer math that overflows is undefined behavior (UB). In OP's case, it appears that the lower 32-bits of the product fn * i, as 2's complement, was the result. Eventually enough multiplication of even numbers kept shifting the non-zero portion of the product "to the left" and resulted in that lower 32 bits becoming 0.

To calculate large factorials one needs another approach. Example

Why does this factorial function break after a certain point?

1 Answers1