Factorials of large numbers

Algorithm for finding the factorials of a large number.

In C++ 64 bit compilers, the sizeof unsigned long long is 8 bytes i.e 64bits. 8 bytes can hold a positive number in range 0 to 18,446,744,073,709,551,615.
20! (20 factorial) = 2,432,902,008,176,640,000
21! (21 factorial) = 51,090,942,171,709,440,000
20! < range of (unsigned long long) < 21!
Thus factorials beyond 20! cannot fit in the data type unsigned long long.

The idea behind this algorithm is to calculate and store the factorial in an integer array. Since calculating a factorial of a large number ‘N’ requires N-1 multiplications, we carry out all these multiplications using the same integer array that would store the end result i.e N!.

Note : The trick for doing the multiplications of numbers from N, N-1, N-2, … till 1 is to store the digits of the result of multiplication operations in a reverse order in the array. So that further multiplication operations are easier to carry out.

Steps to carry out the multiplications while finding the factorial of a large number.
Example : Finding the factorial of 25.
25 ! = 25 * 24 * 23 * 22 * … * 1
25 * 24 = 24 * 5 + 24 * 20 = 120 + 480 = 600; which can also be calculated as below
25 * 24 = Step 1 : 24 * 5 = 120 [ store the last digit (0) and carry the remaining digits (12) ]
               Step 2 : 24 * 2 = 48 + 12 (12 was carried from the previous operation) = 60 [ store 60 in reverse order ]

Example of finding the factorial of a large number
Large Factorial


C++14 : Finding factorials of large number

#include<iostream>
using namespace std;

class Factorial {

    public:

    void GetFactorial (int number) {

        int store[1000] = {0};
        int index = 0;
        int result = number;

        // Store the number in the reverse order. 
        // Example: Number 123 is stored as 3, 2, 1
        //                                  ^  ^  ^
        //                                  |  |  |
        //                          Index   0  1  2
        while (result >= 1) {
            store[index++] = result%10;
            result /= 10;
        }
        number--;

        int carry = 0;
        while (number > 0) {
            int i = 0;
            while (i < index) {
                result = store[i] * number + carry;
                store[i++] = result%10;
                carry = result/10;
            }
            while (carry > 0) {
                store[i++] = carry%10;
                carry /= 10;
            }
            number -= 1;
            index = i;
        }

        cout << "Factorial : ";
        for (int i=index-1; i>=0; i--) {
            cout << store[i];
        } cout << endl;
    }
};

int main() {

    Factorial f;
    int num;
    cout << "Enter number : ";
    cin >> num;
    f.GetFactorial(num);

    return 0;
}

Output

Enter number : 30
Factorial : 265252859812191058636308480000000
Enter number : 100
Factorial : 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Copyright © 2019-2020, Algotree.org.
All rights reserved.