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

Question

Hello,

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

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

Thanks,

(Sorry for my poor English)

Answer 1

Well, you'd have to write your own math routines using arrays. That's very easy for addition, multiplication is a bit harder, but still possible.

EDIT: Wanted to post an example, but Srivatsan Iyer's example is just fine.

Answer 2

Hi,

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..

Answer 3

A BigInteger class would solve your problem, and the C implementation above gives you an idea about how a BigInt would be implemented, except that the code is optimized for speed and tailored to computing the factorial only.

Answer 4

Nice solution by Srivatsan Iyer and my suggestion are :

1. It can still be made more memory efficient by using unsigned char array rather than using int array to store digits. It will take only 25% of the memory need to that of int array.

2. For the best memory optimization , we can also use single byte to represent a 2 digits. Since only 4 bits are suffice to represent any digit from 0 to 9. So we can pack two digits in a single byte using bitwise operations. It will take 12.5% of the memory need to that of int array.

Answer 5

Since everyone voted for Srivatsan, I just have a doubt related to the problem. Do you need to store all the digits? If yes, then Srivatsan's solution is fine. If not, why not just display the numbers, as you calculate the factorial? I am not formatting the output properly, but this could serve the purpose.

int factorial(int num)
{
   if (num <= 0)
      return 1;
   else
   {
      std::cout << num << std::endl;
      return num * factorial(num - 1);
   }
}