Saturday 6 August 2016

Anirudh

How to calculate factorial of very large numbers in C/C++

In languages like C or C++, how can we find the factorial of large numbers like 100 or 1000? It seems difficult with limited range of data types at hand. Even with types like long long, the factorial of numbers only up to 20 can can be accurately stored (20! = 2432902008176640000).


So, here is an approach to calculate factorials of larger numbers in C, using array and the idea of old school mathematics: multiplying a number with another, one digit at a time, and taking the carry.

The idea:
1) Create an array res[] of some maximum size where the size is the number of maximum digits in output.
2) This array will have our resulting number (factorial) of given number N, digit by digit. Note that the number will be stored in the array in reverse order (for easier calculation and storage of digits).
2) Initialize value stored in res[] as 1 and also initialize the variable size (for holding the current size of res[]) as 1.
3) Now as we do while finding factorial, for every number n from 2 to N, keep on multiplying n with number stored in res[] digit by digit and update res[] and size to store the multiplication result.

How to multiply a number n with the number stored in res[]?
The idea is to use simple school maths - multiply n with every digit of res[] one by one. The important point to note here is that digits are multiplied from the rightmost digit to the leftmost digit. If we store digits of a number in their actual order in res[], then it becomes difficult to update the array without extra space. That is why res[] is maintained in reverse way, i.e. digits are stored from right to left.

Steps to multiply res[] and n:
1) Initialize carry as 0.
2) Do the following for i = 0 to size – 1
    a) Find value of (res[i] * n + carry). Let this value be stored in variable mul.
    b) Update res[i] by storing last digit of mul in it.
    c) Update carry by storing the remaining digits in carry.
3) At last, just put all digits of carry in res[] one by one and increase size by number of digits in carry.

Here is the program in C:

#include <stdio.h>
int main()
{
    int N, n, i, carry, size, mul;
    int res[3000];  // Let the array have capacity to store up to 3000 digits
                    // Numbers will be stored in reverse order in the array

    printf("\nEnter number to calculate factorial: ");
    scanf("%d", &N);

    res[0] = 1;     // Initialize the array with only 1 digit, i.e. 1
    carry = 0;      // Carry is initially 0
    size = 1;       // Initializes digit counter as 1 (no of digits in the array)

    for(n = 2; n <= N; n++)
    {
        for(i = 0; i < size; i++)      // Loop for multiplying numbers n and res[]
        {
            mul = (res[i] * n) + carry;  // Product of n with each digit + carry from previous operation
            res[i] = mul % 10;           // Put first digit of product with ith digit at position i itself
            carry = mul / 10;            // Remaining carry value that will be stored in later indexes
        }

        while(carry > 0)               // Loop for storing the remaining carry value to the array
        {
            res[size++] = carry % 10;
            carry /= 10;
        }
    }

    printf("\nFactorial = ");       // Printing the result
    for(i = size-1; i >= 0; i--)    // Array is stored in reverse so printing in reverse
        printf("%d", res[i]);

    return 0;
}

Anirudh

About the author →

Anirudh Khanna is a Computer Science student and a geek who firmly believes in the awesomeness of technology! He is a programmer and web designer, also keenly interested in the research of new and innovative ideas in Computer Science.

Subscribe to Geek Factorial via email :

1 comments

Write comments
Unknown
AUTHOR
July 04, 2021 7:28 pm delete

but what if we have to use this value in another code, and there was a problem because we couldnt store the number as it was very large

Reply
avatar