GeeksforGeeks - Factorial of a large number

GeeksforGeeks - Factorial of a large number

Factorial of 100 has 158 digits. It is not possible to store these many digits even if we use long long int. Following is a simple solution where we use an array to store individual digits of the result. The idea is to use basic mathematics for multiplication.

In Java, Use BigInteger.

multiply(res[], x)
1) Initialize carry as 0.
2) Do following for i = 0 to res_size – 1
….a) Find value of res[i] * x + carry. Let this value be prod.
….b) Update res[i] by storing last digit of prod in it.
….c) Update carry by storing remaining digits in carry.
3) Put all digits of carry in res[] and increase res_size by number of digits in carry.

void factorial(int n)

{

    int res[MAX];

 

    // Initialize result

    res[0] = 1;

    int res_size = 1;

 

    // Apply simple factorial formula n! = 1 * 2 * 3 * 4...*n

    for (int x=2; x<=n; x++)

        res_size = multiply(x, res, res_size);

 

    cout << "Factorial of given number is \n";

    for (int i=res_size-1; i>=0; i--)

        cout << res[i];

}

 

// This function multiplies x with the number represented by res[].

// res_size is size of res[] or number of digits in the number represented

// by res[]. This function uses simple school mathematics for multiplication.

// This function may value of res_size and returns the new value of res_size

int multiply(int x, int res[], int res_size)

{

    int carry = 0;  // Initialize carry

 

    // One by one multiply n with individual digits of res[]

    for (int i=0; i<res_size; i++)

    {

        int prod = res[i] * x + carry;

        res[i] = prod % 10;  // Store last digit of 'prod' in res[]

        carry  = prod/10;    // Put rest in carry

    }

 

    // Put carry in res and increase result size

    while (carry)

    {

        res[res_size] = carry%10;

        carry = carry/10;

        res_size++;

    }

    return res_size;

}

GeeksforGeeks - Factorial of a large number