Why does N! stop overflowing the 32 bits output variable when N>=34?

Question

Is there any limitation of variable overflow for big numbers? There is an exercise in a C book about factorials.

My code:

#include <stdio.h>

int main(void) {
    unsigned int n, fn, counter;
    //puts("enter nonnegative int");
    //scanf("%u", &n);
    n = 1;
    while (n != 34) {
        fn = n;
        counter = n - 1;
        while (counter > 0) {
            fn *= counter;
            counter--;
        }
        printf("%u\n", fn);
        n++;
    }
}

The commented lines are for debugging.

This code prints the factorial of numbers from n(1) to 34 ('while(n!=34)'), but if you increase it to something like 36 it will just print 0 after first 34 outputs. I know most of the outputs are overflowed and am controlling these big numbers very poorly.

However, I would like to know what limits are causing these zeros to occur.

Answer 1

You complain that

N! stops overflowing the 32 bits output variable when N>=34

meaning that, after 34!, the result keeps remaining to 0.

Well, the answer is that it doesn't stop overflowing. What happens is that the value shown, that is the remainder of the division N! / 2^32, starting from N=34 becomes 0 and will never change.

In order to understand how it can happen, let's start with an example using a decimal number. We'll display the result of N! using a display with only two digits:

Factorial	Actual result	Displayed result	Notes
1!	1	01
2!	2	02
3!	6	06
4!	24	24
5!	120	20	Overflow!
6!	720	20	Overflow!
7!	5040	40	Overflow!
8!	40320	20	Overflow!
9!	362880	80	Overflow!
10!	3628800	00	Overflow and the shown value is 00!
11!	39916800	00	Overflow and the shown value is still 00!
12!	479001600	00	Overflow and the shown value is still 00!
..	..	00	The shown value will be 00 forever

As you can see, the display overflows at 5! where we can also notice how the result is a multiple of 5*2=10. For obvious reasons all the subsequent results will be a multiple of 5*2=10 so they will have a trailing 0.
But when we reach 10! a special condition occurs: the result becomes a multiple of (5^2)*(2^2)=10^2=100 so, whatever is the multiplication we perform afterwards, the shown value will always be 00.

Remember this info: we reached the all-0 condition when the result started having the common factor of B^N, where

• B is the base of the representation (10)
• N is the number of shown digits (2)

So, in this case, 10^2.

---

The same reasoning can be done using a binary (base-2) representation, limited by the size of a unsigned int. We will reach the all-0 condition when the result will start having the common factor of B^N = 2^32.

And when will the result become a multiple of 2^32? Let's count the multiplications introducing powers of 2:

• 2! will add a factor 2 (2^1 in total)
• 4! will add a factor 2^2 (2^3 in total)
• 6! will add a factor 2 (2^4 in total)
• 8! will add a factor 2^3 (2^7 in total)
• 10! will add a factor 2 (2^8 in total)
• 12! will add a factor 2^2 (2^10 in total)
• 14! will add a factor 2 (2^11 in total)
• 16! will add a factor 2^4 (2^15 in total)
• 18! will add a factor 2 (2^16 in total)
• 20! will add a factor 2^2 (2^18 in total)
• 22! will add a factor 2 (2^19 in total)
• 24! will add a factor 2^3 (2^22 in total)
• 26! will add a factor 2 (2^23 in total)
• 28! will add a factor 2^2 (2^25 in total)
• 30! will add a factor 2 (2^26 in total)
• 32! will add a factor 2^5 (2^31 in total)
• 34! will add a factor 2 (2^32 in total)

From now on the factorial will always be a multiple of 2^32, so the shown result, the remainder of N! / 2^32 will always be 0.