why using arrays to store factorial values will output wrong values when n>=34 in C

Question

The factorial values below 33 are correct.

but my code goes wrong from 34 as below:

34!=-134263930639604140847618609643520000000
35!=25226455986144929666651337523200000000
36!=908152415501217467999448150835200000000
37!=-9348033593545046315979581580902400000000
38!=-11627892614711760007224100074291200000000
39!=18958590953758640281739902897356800000000
40!=-100649821150345611269596115894272000000000

Here is the code:

#include <stdio.h>
#include <math.h>

#define N 100
int Fact(int a[], int n);
int a[N] = { 0 };

int main() {
    int n, i, j, index;
    printf("input n(1≤n≤40):");
    scanf_s("%d", &n);
    for (i = 1; i <= n; i++) { //printf every factorial value from 1 to 40
        for (j = 0; j < N; j++)
            a[j] = 0; /* reset the array as 0 in every loop */
        index = Fact(a, i);/*Calculates the factorial value and stores the result in array,
                        returning the array index of the highest bit of the factorial value*/
        printf("\n%d!=", i);
        for (j = index; j >= 1; --j)
            printf("%d", a[j]);
    }
    return 0;
}

int Fact(int a[], int n) {
    int i, j, temp, index = 1;
    a[1] = 1; //the index of array starts from 1, not 0
    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= index; j++)
            a[j] *= i; //Multiply each position of the array by 1 to i
        for (j = 1; j < index; ++j) {
            if (a[j] > 9) { //Judging if every position of array needs a carry
                temp = a[j];
                a[j] = a[j] % 10;
                a[j + 1] += temp / 10;
            }
        }
        if (a[index] > 9) { //Judging if the highest position needs a carry
            temp = a[index];
            a[index] = a[index] % 10;
            a[++index] += temp / 10;
        }
    }
    return index;
}

Expected output:

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

Answer 1

Inside the Fact function, an overflow is happening in this part of the code:

            if (a[index] > 9) {//Judging if the highest position needs a carry
                temp = a[index];
                a[index] = a[index] % 10;
                a[++index] += temp / 10;
            }

Solution: Change the if to a while loop.

            while(a[index] > 9) {  //   <---- if to while
                temp = a[index];
                a[index] = a[index] % 10;
                a[++index] += temp / 10;
            }

---

Explanation:

As far as I can understand, the a array should contain each digit of the resulting factorial. It's size is initialized to N which is 100. The internal representation of the digits are also reversed.

10! = 362880 = [0, 8, 8, 2, 6, 3, ... rest of unused indices]
                               ^
                            a[index]

In the snippet above, a[index] points to the most significant digit.

You are only taking care of a[index] once if it is greater than 9. In my tests, a[index] slowly creeps to become a big number. After doing the inside procedure once, a[index] > 9 still hold true for factorial of n>=15. Thus, you should perform the inside procedure until the condition no longer holds true.

This is a print out of the significant digits of the a array:

1!=1
2!=2
3!=6
4!=2 4
5!=1 2 0
6!=7 2 0
7!=5 0 4 0
8!=4 0 3 2 0
9!=3 6 2 8 8 0
10!=3 6 2 8 8 0 0
11!=3 9 9 1 6 8 0 0
12!=4 7 9 0 0 1 6 0 0
13!=6 2 2 7 0 2 0 8 0 0
14!=8 7 1 7 8 2 9 1 2 0 0
15!=13 0 7 6 7 4 3 6 8 0 0 0
16!=20 9 2 2 7 8 9 8 8 8 0 0 0
17!=35 5 6 8 7 4 2 8 0 9 6 0 0 0
18!=64 0 2 3 7 3 7 0 5 7 2 8 0 0 0
19!=121 6 4 5 1 0 0 4 0 8 8 3 2 0 0 0
20!=243 2 9 0 2 0 0 8 1 7 6 6 4 0 0 0 0
21!=510 9 0 9 4 2 1 7 1 7 0 9 4 4 0 0 0 0
22!=1124 0 0 0 7 2 7 7 7 7 6 0 7 6 8 0 0 0 0
23!=2585 2 0 1 6 7 3 8 8 8 4 9 7 6 6 4 0 0 0 0
24!=6204 4 8 4 0 1 7 3 3 2 3 9 4 3 9 3 6 0 0 0 0
25!=15511 2 1 0 0 4 3 3 3 0 9 8 5 9 8 4 0 0 0 0 0 0
26!=40329 1 4 6 1 1 2 6 6 0 5 6 3 5 5 8 4 0 0 0 0 0 0
27!=108888 6 9 4 5 0 4 1 8 3 5 2 1 6 0 7 6 8 0 0 0 0 0 0
28!=304888 3 4 4 6 1 1 7 1 3 8 6 0 5 0 1 5 0 4 0 0 0 0 0 0
29!=884176 1 9 9 3 7 3 9 7 0 1 9 5 4 5 4 3 6 1 6 0 0 0 0 0 0
30!=2652528 5 9 8 1 2 1 9 1 0 5 8 6 3 6 3 0 8 4 8 0 0 0 0 0 0 0
31!=8222838 6 5 4 1 7 7 9 2 2 8 1 7 7 2 5 5 6 2 8 8 0 0 0 0 0 0 0
32!=26313083 6 9 3 3 6 9 3 5 3 0 1 6 7 2 1 8 0 1 2 1 6 0 0 0 0 0 0 0
33!=86833176 1 8 8 1 1 8 8 6 4 9 5 5 1 8 1 9 4 4 0 1 2 8 0 0 0 0 0 0 0
34!=-1342639306 3 9 6 0 4 1 4 0 8 4 7 6 1 8 6 0 9 6 4 3 5 2 0 0 0 0 0 0 0
35!=25226455 9 8 6 1 4 4 9 2 9 6 6 6 6 5 1 3 3 7 5 2 3 2 0 0 0 0 0 0 0 0
36!=90815241 5 5 0 1 2 1 7 4 6 7 9 9 9 4 4 8 1 5 0 8 3 5 2 0 0 0 0 0 0 0 0
37!=-934803359 3 5 4 5 0 4 6 3 1 5 9 7 9 5 8 1 5 8 0 9 0 2 4 0 0 0 0 0 0 0 0
38!=-1162789261 4 7 1 1 7 6 0 0 0 7 2 2 4 1 0 0 0 7 4 2 9 1 2 0 0 0 0 0 0 0 0
39!=189585909 5 3 7 5 8 6 4 0 2 8 1 7 3 9 9 0 2 8 9 7 3 5 6 8 0 0 0 0 0 0 0 0
40!=-1006498211 5 0 3 4 5 6 1 1 2 6 9 5 9 6 1 1 5 8 9 4 2 7 2 0 0 0 0 0 0 0 0 0

As you can see, the most significant digit a[index] is overflowing. This output is generated by just adding a space in between digits when you output the resulting array.

    int main(){
        // ...
        // for loop
            // calc factorial

            /* output the result */
           printf("\n%d!=", i);
            for (j = index; j >= 1; --j)
                printf("%d ", a[j]); //     <---- add space between digits


        // end for loop
        return 0;
    }

Answer 2

Try this, maybe you can get what you wanted :

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

#define MAX 3000 

int str[MAX]; 

void calculateFactorial(int n); 

int main() 
{ 
  int n; 
  //while (scanf("%d", &n) != EOF) { 
  for(n = 0; n <=40; n++) { 
      printf("%d!=",n);
      if(n == 0) { 
        printf("1\n"); 
      } else { 
        calculateFactorial(n); 
      } 
  printf("\n");
  } 
  return 0; 
} 

void calculateFactorial(int n) 
{ 
  int i, j, temp, c, len; 
  memset(str, 0, sizeof(str)); 
  str[1] = 1; 
  for (i = 2, len = 1; i <= n; i ++) { 
      for (j = 1, c = 0; j <= len; j ++) { 
          temp = str[j] * i + c; 
          str[j] = temp % 10; 
          c = temp / 10; 
      } 
      while(c > 0){
        str[j ++] = c % 10; 
        c /= 10; 
      } 
      len = j - 1; 
  } 
  for (i = len; i >= 1; i --) { 
    printf("%d", str[i]); 
  } 
  printf("\n"); 
}

The output is :

0!=1

1!=1

2!=2

3!=6

4!=24

5!=120

6!=720

7!=5040

8!=40320

9!=362880

10!=3628800

11!=39916800

12!=479001600

13!=6227020800

14!=87178291200

15!=1307674368000

16!=20922789888000

17!=355687428096000

18!=6402373705728000

19!=121645100408832000

20!=2432902008176640000

21!=51090942171709440000

22!=1124000727777607680000

23!=25852016738884976640000

24!=620448401733239439360000

25!=15511210043330985984000000

26!=403291461126605635584000000

27!=10888869450418352160768000000

28!=304888344611713860501504000000

29!=8841761993739701954543616000000

30!=265252859812191058636308480000000

31!=8222838654177922817725562880000000

32!=263130836933693530167218012160000000

33!=8683317618811886495518194401280000000

34!=295232799039604140847618609643520000000

35!=10333147966386144929666651337523200000000

36!=371993326789901217467999448150835200000000

37!=13763753091226345046315979581580902400000000

38!=523022617466601111760007224100074291200000000

39!=20397882081197443358640281739902897356800000000

40!=815915283247897734345611269596115894272000000000

or if you want to correct your code :

try this :

#include <stdio.h>
#include <math.h>
#define N 3000
int Fact(int a[], int n);
int a[N] = { 0 };
int main() {
    int n, i, j, index;
    printf("input n(1≤n≤40):");
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {//printf every factorial value from 1 to 40
        for (j = 0; j < N; j++)
            a[j] = 0;/*reset the array as 0 in every loop*/
        index = Fact(a, i);/*Calculates the factorial value and stores the result in array,
                        returning the array index of the highest bit of the factorial value*/
        printf("\n%d!=", i);
        for (j = index; j >= 1; --j)
            printf("%d", a[j]);
    }
    printf("\n");
    return 0;
}

int Fact(int a[], int n) {
    int i, j, temp, index = 1;
    a[1] = 1;//the index of array starts from 1,not 0
    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= index; j++)
            a[j] *= i;//Multiply each position of the array by 1 to i
        for (j = 1; j < index; ++j) {
            if (a[j] > 9) {//Judging if every position of array needs a carry
                temp = a[j];
                a[j] = a[j] % 10;
                a[j + 1] += temp / 10;
            }
        }
        while (a[index] > 9) {//Judging if the highest position needs a carry
            temp = a[index];
            a[index] = a[index] % 10;
            a[++index] += temp / 10;
        }
    }
    return index;
}

The output is :

0!=1

1!=1

2!=2

3!=6

4!=24

5!=120

6!=720

7!=5040

8!=40320

9!=362880

10!=3628800

11!=39916800

12!=479001600

13!=6227020800

14!=87178291200

15!=1307674368000

16!=20922789888000

17!=355687428096000

18!=6402373705728000

19!=121645100408832000

20!=2432902008176640000

21!=51090942171709440000

22!=1124000727777607680000

23!=25852016738884976640000

24!=620448401733239439360000

25!=15511210043330985984000000

26!=403291461126605635584000000

27!=10888869450418352160768000000

28!=304888344611713860501504000000

29!=8841761993739701954543616000000

30!=265252859812191058636308480000000

31!=8222838654177922817725562880000000

32!=263130836933693530167218012160000000

33!=8683317618811886495518194401280000000

34!=295232799039604140847618609643520000000

35!=10333147966386144929666651337523200000000

36!=371993326789901217467999448150835200000000

37!=13763753091226345046315979581580902400000000

38!=523022617466601111760007224100074291200000000

39!=20397882081197443358640281739902897356800000000

40!=815915283247897734345611269596115894272000000000