Factorial program in C is wrong after 20

It works up until 20 but if 21 is entered it returns 1419745... when 21 factorial is actually 51090942171709440000. I'm assuming that this is because of the unsigned long maxing out but where does this wrong number (141...) come from and how can I allow the program to work out the factorial of larger numbers?

#include <stdio.h>

unsigned long fact(unsigned long input);

int main()

{

    int input;

    printf("Enter an integer to find the factorial of: ");
    scanf(" %d", &input);

    printf("The Factorial of %d = %lu\n" , input, fact(input)); 

    return 0;
}

unsigned long fact(unsigned long input)
{
    if (input == 0)
            return 1;
    else    
        return input * fact(input - 1);
}

Solution

This answers only to half of your question (why it works this way).

The result you get is 21! mod 2^64. This is because you are using a 64-bit system and 21! is greater than the greatest number that can be stored as unsigned integer on 64 bits.

All factorials you compute for values greater than or equal to 21 are wrong; they cannot be represented on 64-bit integers because they are longer than that.

You can try to use unsigned long long as the type of the values returned by function fact() (and change into the printf() format string %lu with %llu); it could help but it depends on some factors. It doesn't help on my architecture, for example.

You can find out if it can help you by checking the value returned by sizeof(unsigned long long). If if is 8 then you are out of luck. 20 is the largest number for what you can compute factorial on that system.

If your purpose is to compute factorials then you have to use a library that knows how to handle large numbers. However, if you need factorials for other computations (for example, for combinations) then you can try to avoid generating large numbers and find a way to match each multiplication with a division. This way the magnitude of the numbers you use is between the limits of 64-bit integers and you can go further than 21.

Or you can use double instead of integers and you are again back in business but with loss of precision. Large floating point numbers store correctly the magnitude of the number and its first digits. The last digits are lost.

I didn't program very much in C/C++ recently, I cannot recommend you a library that can help you do computations with large numbers :-(