Why Does Computing Factorial of Relatively Small Numbers (34+) Return 0

Factorial loop becomes 0

Starting from 34!, all factorials are divisible by 2^32. So when your computer program computes the results modulo 2^32 (which, although you don't say what programming language you're using, this is likely), then the results are always 0.

Here is a program that computes factorials mod 2^32 in Python:

def sint(r):
    r %= (1 << 32)
    return r if r < (1 << 31) else r - (1 << 32)

r = 1
for i in xrange(1, 40):
    r *= i
    print '%d! = %d mod 2^32' % (i, sint(r))

Which gives this output, which agrees with the output from your own program:

1! = 1 mod 2^32
2! = 2 mod 2^32
3! = 6 mod 2^32
4! = 24 mod 2^32
5! = 120 mod 2^32
6! = 720 mod 2^32
7! = 5040 mod 2^32
8! = 40320 mod 2^32
9! = 362880 mod 2^32
10! = 3628800 mod 2^32
11! = 39916800 mod 2^32
12! = 479001600 mod 2^32
13! = 1932053504 mod 2^32
14! = 1278945280 mod 2^32
15! = 2004310016 mod 2^32
16! = 2004189184 mod 2^32
17! = -288522240 mod 2^32
18! = -898433024 mod 2^32
19! = 109641728 mod 2^32
20! = -2102132736 mod 2^32
21! = -1195114496 mod 2^32
22! = -522715136 mod 2^32
23! = 862453760 mod 2^32
24! = -775946240 mod 2^32
25! = 2076180480 mod 2^32
26! = -1853882368 mod 2^32
27! = 1484783616 mod 2^32
28! = -1375731712 mod 2^32
29! = -1241513984 mod 2^32
30! = 1409286144 mod 2^32
31! = 738197504 mod 2^32
32! = -2147483648 mod 2^32
33! = -2147483648 mod 2^32
34! = 0 mod 2^32
35! = 0 mod 2^32
36! = 0 mod 2^32
37! = 0 mod 2^32
38! = 0 mod 2^32
39! = 0 mod 2^32

And here's a table of the exact values of this range of factorials, showing how many powers of 2 each contains:

1! = 1. Divisible by 2^0
2! = 2. Divisible by 2^1
3! = 6. Divisible by 2^1
4! = 24. Divisible by 2^3
5! = 120. Divisible by 2^3
6! = 720. Divisible by 2^4
7! = 5040. Divisible by 2^4
8! = 40320. Divisible by 2^7
9! = 362880. Divisible by 2^7
10! = 3628800. Divisible by 2^8
11! = 39916800. Divisible by 2^8
12! = 479001600. Divisible by 2^10
13! = 6227020800. Divisible by 2^10
14! = 87178291200. Divisible by 2^11
15! = 1307674368000. Divisible by 2^11
16! = 20922789888000. Divisible by 2^15
17! = 355687428096000. Divisible by 2^15
18! = 6402373705728000. Divisible by 2^16
19! = 121645100408832000. Divisible by 2^16
20! = 2432902008176640000. Divisible by 2^18
21! = 51090942171709440000. Divisible by 2^18
22! = 1124000727777607680000. Divisible by 2^19
23! = 25852016738884976640000. Divisible by 2^19
24! = 620448401733239439360000. Divisible by 2^22
25! = 15511210043330985984000000. Divisible by 2^22
26! = 403291461126605635584000000. Divisible by 2^23
27! = 10888869450418352160768000000. Divisible by 2^23
28! = 304888344611713860501504000000. Divisible by 2^25
29! = 8841761993739701954543616000000. Divisible by 2^25
30! = 265252859812191058636308480000000. Divisible by 2^26
31! = 8222838654177922817725562880000000. Divisible by 2^26
32! = 263130836933693530167218012160000000. Divisible by 2^31
33! = 8683317618811886495518194401280000000. Divisible by 2^31
34! = 295232799039604140847618609643520000000. Divisible by 2^32
35! = 10333147966386144929666651337523200000000. Divisible by 2^32
36! = 371993326789901217467999448150835200000000. Divisible by 2^34
37! = 13763753091226345046315979581580902400000000. Divisible by 2^34
38! = 523022617466601111760007224100074291200000000. Divisible by 2^35
39! = 20397882081197443358640281739902897356800000000. Divisible by 2^35

For loop in c# vs For loop in python

What you're likely running into here is integer overflow with the C# version of the Factorial function (at least your implementation of it, or wherever its coming from).

In C#, an int is a numerical type stored in 32 bits of memory, which means it's bounded by -2^31 <= n <= 2^31 - 1 which is around +/- 2.1 billion. You could try using a long type, which is a 64 bit numerical type, however for even larger upper bounds in your for loop, like getting close to 100, you're going to overflow long as well.

When you run the Factorial function in C#, it starts off normally for the first little while, however if you keep going, you'll see that it all of a sudden jumps into negative numbers, and if you keep going even further than that, it'll get to 0 and stop changing. You're seeing the output of infinity due to division by 0, and C# has a way of handling that with doubles; that being to just return double.PositiveInfinity.

The reason why this doesn't happen in python is that it uses a variable number of bits to store its numerical values.

Added note: What you might also want to try is using a Factorial function that works with the double type instead of int or long, however by doing this, you'll lose precision on what the exact value is, but you get more range as the magnitude of the number you can store is larger

Further Note: As mentioned in the comments, C# has a type called BigInteger which is designed to handle huge numbers like the values you would expect from large inputs to a Factorial function. You can find a reference to the BigInteger docs here

---

What you can do is calculate each component of the factorial function separately with the power you're using. Here's what I mean:

public decimal Exp(decimal power, int accuracy = 100)
{
    decimal runningTotal = 1;
    decimal finalValue = 1;
    for (int i = 1; i <= accuracy; i++)
    {
        runningTotal *= power/i;
        finalValue += runningTotal;
    }
    return finalValue;
}

Calculating Factorials in C# - No Errors, But Doesn't Work?

It's always the simple things that get us.

In your loop you have this:

for (int i = 1; 1 <= userNumber; i++)

I believe you mean this:

for (int i = 1; i <= userNumber; i++)

In the conditional part of the loop you used a '1' rather than 'i'.

Here's a program to find the factorial of a number. Why am I getting 0 as the answer? Which datatype should I use instead?

33! is actually way out of the range of a 32 bit int, whether signed or unsigned. 12! has a value of 479001600, while 13! has a value of 6227020800, so you go out of range at 13!.

Note also that result is defined as an int and you return an int from fact. This means you end up with signed integer overflow which invokes undefined behavior. This can be fixed by changing the type of both to unsigned, although you're still limited to 12!.

You can try using unsigned long long for your types instead. That will get you up to 20!. If you want values larger than that, you need to use a bigint library such as GMP.

Why Is This Factorial Algorithm Not Accurate

Someone posted a similar question a while back. The consensus was if you're writing it for work use a big number library (like GMP) and if it's a programming exercise write up a solution using a character array.

For example:

/* fact50.c

   calculate a table of factorials from 0! to 50! by keeping a running sum of character digits
*/

#include <stdio.h>
#include <string.h>

int main (void)
{
    printf ("\n                            Table of Factorials\n\n");

    // length of arrays = 65 character digits

    char str[] =
    "00000000000000000000000000000000000000000000000000000000000000000"; 
    char sum[] =
    "00000000000000000000000000000000000000000000000000000000000000001"; 

    const int len = strlen (str);
    int index;

    for ( int i = 0; i <= 50; ++i ) {

        memcpy (str, sum, len);

        for ( int j = 1; j <= i - 1; ++j ) {

            index = len - 1;        
            int carry = 0;

            do {
                int digit = (sum[index] - '0') + (str[index] - '0') + carry;            
                carry = 0;
                if ( digit > 9 ) {
                    carry = 1;
                    digit %= 10;
                }            
                sum[index] = digit + '0';
                --index;
            }
            while ( index >= 0 );

        }

        printf ("%2i! = ", i);
        for ( index = 0; sum[index] == '0'; ++index )
            printf ("%c", '.');
        for ( ; index < len; ++index )
            printf ("%c", sum[index]);
        printf ("\n");        

    }

    return 0;
}

Calculate factorials in C#

Have a look at the BigInteger structure:

http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx

Maybe this can help you implement this functionality.

CodeProject has an implementation for older versions of the framework at http://www.codeproject.com/KB/cs/biginteger.aspx.

---

Related Topics