Factorial loop becomes 0
I ran a simple program with a compiled language that calculates the factorial of the first few natural numbers using two simple loops, the outer one to keep track of which is the number we calculate the factorial and the inner one to calculate the factorial by multiplying each natural number from 1 to the number itself. The program works perfectly for the first natural numbers, then from about the 13th value onwards, the calculations of factorials are clearly wrong. It has to do with integer arithmetic as implemented in modern computer and I can understand why negative values might occur. So I don't understand why, and this is what I have tested on different computers, after a very small amount of factorial computation always goes to zero. Of course, if the nth factorial evaluates to 0,will also evaluate the (n + 1) th factorial 0 and so on, but why is it that the number 0 always happens after a very small number of factorial calculations?
EDIT: You might be wondering why I used two different loops instead of one ... I did this to get the computer to recalculate each factorial from the beginning, just to check that indeed the factorial becomes always 0 and this is no coincidence.
Here's my output:
source to share
Starting at 34 !, all factorials are divisible by 2 ^ 32. So when your computer program calculates the results modulo 2 ^ 32 (which, although you don't say which programming language you are using, it is likely), then the results are always 0 ...
Here is a program that calculates mod 2 ^ 32 factorials 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 is consistent with exiting 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 is a table of the exact values of this range of factorials showing how many degrees of 2 it 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
source to share
Each multiplication adds zero bits to the right until, at some iteration, most of the remaining bits are discarded due to 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
Note that before we get zero we get INT_MIN . Adding one more zero bit - clears the sign bit and, therefore, from INT_MIN, we get equal to zero.
source to share