Factorial program in C is wrong after 20

Question

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);
}

After the multiplication overflows, you are typically left with the least significant part, but it is a binary truncation, not a decimal one, which is why the value seems nonsenical. There are 2 courses of approach: use a big int library, or sometimes a modulus of the product is required afterwards - keep the number within limits by applying the modulus after every multiplication. — Weather Vane, Mar 09 '16 at 13:52
@CoolGuy `unsigned long long` is not enough (at least if compiler use the minimum size imposed by standard) — Garf365, Mar 09 '16 at 13:56
@banana1337 `ULONG_MAX` is a macro which contains maximum value which can be stored inside an `unsigned long`. — Garf365, Mar 09 '16 at 13:59
@Garf365 What do you mean? I thought that `unsigned long long` can store more values than an `unsigned long`. — Spikatrix, Mar 09 '16 at 14:04
@CoolGuy `long long` doesn't have to be longer than 64 bits. On OP's computer, `long` is 64 bits already. `int`, on the other hand, should not be longer than 32 bits on any system. — VLL, Mar 09 '16 at 14:12
In the duplicate question the OP was calculating terms for a Taylor series. The answer from @nickie pointed out that you don't even need to compute a factorial, since each term can be calculated from the previous term with a multiplication and division. — Weather Vane, Mar 09 '16 at 14:28
@CoolGuy in fact, it's not totally true : `unsigned long` should be _at least_ 32bits, `unsigned long long` should be _at least_ 64 bits, and `sizeof(unsigned long long) >= sizeof(unsigned long)`. So it's not impossible that `unsigned long long` and `unsigned long` have same size and so store same values — Garf365, Mar 09 '16 at 14:30
The numerical limits of the various integer types are among the very first things discussed when learning any programming language. Typically this is discussed in chapter 1 or 2 of any beginner-level programming book for any programming language. — Lundin, Mar 09 '16 at 14:32
@Ville-ValtteriTiittanen: There is no restriction on the width of any integer type. `int` can very well have 1024 bits. — too honest for this site, Mar 09 '16 at 14:36

axiac · Accepted Answer · 2016-03-09T15:34:33.457

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 :-(

score 0 · Answer 2 · answered Mar 09 '16 at 13:53

The number comes from overflow. Unsigned arithmetic is done modulo (max value of that type), so a little maths should explain why you get the result you do.

The result of signed integer overflow is undefined so you could have got anything if you'd been using signed integers (though the chances are it'd have been exactly the same on a lot of systems)

Factorial program in C is wrong after 20

2 Answers2

Linked