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

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

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.

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.

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.

#include<stdio.h>
#include<string.h>
char f[10000];
char factorial[1010][10000];
void multiply(int k){
    int ci,sum,i;
    int len = strlen(f);
    ci=0;
    i=0;
    while(i<len){
        sum=ci+(f[i] - '0') * k;
        f[i] = (sum % 10) + '0';
        i++;
        ci = sum/10;
    }
    while(ci>0){
        f[i++] = (ci%10) + '0';
        ci/=10;
    }
    f[i]='\0';
    for(int j=0;j<i;j++)factorial[k][j]=f[j];
    factorial[k][i]='\0';
}
void fac(){
    int k;
    strcpy(f,"1");
    for(k=2;k<=1000;k++)multiply(k);
}
void print(int n){
    int i;
    int len = strlen(factorial[n]);
    printf("%d!\n",n);
    for(i=len-1;i>=0;i--){
        printf("%c",factorial[n][i]);
    }
    printf("\n");
}
int main()
{
    int n;
    factorial[0][0]='1';
    factorial[1][0]='1';
    fac();
    while(scanf("%d",&n)==1){
        print(n);
    }
    return 0;
}

Code shown below :

#include<bits/stdc++.h>
using namespace std;
#define MAX 5000

void factorial(int n)
{
    int carry , res_size = 1, res[MAX];
    res[0] = 1;

    for(int x=2; x<=n; x++)
    {
        carry = 0;
        for(int i=0; i<res_size; i++)
        {
          int prod = res[i]*x + carry;
          res[i] = prod % 10;
          carry  = prod/10;
        }
        while (carry)
        {
          res[res_size++] = carry%10;
          carry = carry/10;
        }
     }
     for(int i=res_size-1; i >= 0; i--) 
     {
         cout<<res[i];
     }
}
int main()
{
      int n;
      cin>>n;
      factorial(n);
      cout<<endl;
      return 0;
}

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);
   }
}

UPDATE For all the downvoters, though this 5 year old post, and the output for factorial(3);

3
2
1
6 // this is the result of the factorial and the digits above are the ones all the digits in the calculation.

I thought this is what asked.