Factorial loop becomes 0

Question

I ran a simple program with a compiled language that calculates the factorial of the first few natural numbers using two simple cycles, an outer one to keep track of which is the number that we are calculating the factorial and an inner one to calculate the factorial by multiplying every natural number from 1 till the number itself. The program works perfecty for the first natural numbers, then approximately from the 13th value onwards the factorial calculated are clearly wrong. This is due to the integer arithmetic implemented in a modern computer, and I can undestand why negative values can arise. What I don't understand though is why, and this is something I've tested on different computers, after a very small amount of factorial calculated it always hits the number zero. Of course, if a the n-th factorial is evaluated to be 0, also the (n+1)-th factorial will be evaluated 0 and so on, but why is it that the number 0 always occurs after a very small number of factorial calculations?

EDIT: You may be wondering why I used two different cycles instead of only one... I did so to force the computer to recalculate every factorial from the beginning, just to test against the fact that indeed the factorial becomes always 0 and it is not by chance.

Here is my output:

Output of my program

"a compiled language"... Meaning? You seem to know terminology, but your" modern computer" still suffers from integer overflow — OneCricketeer, Apr 12 '17 at 12:46

Paul Hankin · Accepted Answer · 2017-04-12T13:22:24.690

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

I hadn't heard of that fact before. Do you have a link to a proof? — paddy, Apr 12 '17 at 12:55
@paddy You can just count factors of 2. In 1...34, there's floor(34/2) numbers divisible by 2, floor(34/4) numbers divisible by 4, floor(34/8) numbers divisible by 8, and so on. `(34 // 2) + (34 // 4) + (34 // 8) + (34 // 16) + (34 // 32) = 32`. — Paul Hankin, Apr 12 '17 at 12:59
Isn't it that 1 bit is used for the sign (+ or -) of the integer? Then shouldn't it be always 0 already when the numbers is divisible by 2^31? — John, Apr 12 '17 at 13:00
@John most modern programming languages implementations use a 2's complement representation for fixed sized 32-bit ints since that's how modern processors work. That corresponds to modulo 2^32 arithmetic. — Paul Hankin, Apr 12 '17 at 13:02
Oh now I see, but another last question, then if the calculation of the factorials are wrong already starting approximately from 13!, then how can we be sure that the computer will indeed know that there is a 2^32 factor in 34! ? — John, Apr 12 '17 at 13:09
Don't think of them as wrong -- think of the program as correctly computing factorials modulo 2^32. — Paul Hankin, Apr 12 '17 at 13:12

Agnius Vasiliauskas · Answer 2 · 2017-04-14T19:27:47.527

Each multiplication appends zero bits from the right until at some iteration left-most bits gets discarded because of overflow. Effect in action:

    int i, x=1;
    for (i=1; i <=50; i++) {
        x *= i;
        for (int i = 31; i >= 0; --i) {
            printf("%i",(x >> i) & 1);
        }
        printf("\n");
    }

Output bits:

00000000000000000000000000000001
00000000000000000000000000000010
00000000000000000000000000000110
00000000000000000000000000011000
00000000000000000000000001111000
00000000000000000000001011010000
00000000000000000001001110110000
00000000000000001001110110000000
00000000000001011000100110000000
00000000001101110101111100000000
00000010011000010001010100000000
00011100100011001111110000000000
01110011001010001100110000000000
01001100001110110010100000000000
01110111011101110101100000000000
01110111011101011000000000000000
11101110110011011000000000000000
11001010011100110000000000000000
00000110100010010000000000000000
10000010101101000000000000000000
10111000110001000000000000000000
11100000110110000000000000000000
00110011100000000000000000000000
11010000000000000000000000000000
10000000000000000000000000000000
00000000000000000000000000000000

Notice that before we get zero - we get INT_MIN. Appending yet another zero bit - discards sign bit and thus from INT_MIN we get plain zero.

Factorial loop becomes 0

2 Answers2