Calculate the factorial of an arbitrarily large number, showing all the digits

Question

I was recently asked, in an interview, to describe a method to calculate the factorial of any arbitrarily large number; a method in which we obtain all the digits of the answer.

I searched various places and asked in a few forums. But I would like to know if there is any way to accomplish this without using libraries like GMP.

Thank you.

Answer 1

GNU Multiprecision library is a good one! But since you say using of external libraries are not allowed, only way I believe its possible is by taking an array of int and then multiplying numbers as you do with pen on paper!

Here is the code I wrote some time back..

#include<iostream>
#include<cstring>

int max = 5000;

void display(int arr[]){
    int ctr = 0;
    for (int i=0; i<max; i++){
        if (!ctr && arr[i])         ctr = 1;
        if(ctr)
            std::cout<<arr[i];
    }
}


void factorial(int arr[], int n){
    if (!n) return;
    int carry = 0;
    for (int i=max-1; i>=0; --i){
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i]/10;
        arr[i] %= 10;
    }
    factorial(arr,n-1);
}

int main(){
    int *arr = new int[max];
    std::memset(arr,0,max*sizeof(int));
    arr[max-1] = 1;
    int num;
    std::cout<<"Enter the number: ";
    std::cin>>num;
    std::cout<<"factorial of "<<num<<"is :\n";
    factorial(arr,num);
    display(arr);
    delete[] arr;
    return 0;
}

'arr' is just an integer array, and factorial is a simple function that multiplies the given number to the 'large number'.

Hope this solves your query..