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

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.

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

The accepted answer is fine, but this is C++; we can do better. Let's make the start of our own Bignum class, with a totally unbounded number of digits.

For the highest efficiency we would work with pure binary numbers, packing each array element with as many bits as we can efficiently handle. The simpler approach is to store a single decimal digit in each element. Here I've gone for a compromise, storing 9 decimal digits in each uint32_t element.

The data is stored little-endian, since it's much easier to extend a vector at the end when we need higher order elements.

Once we have this class, the factorial function is simplicity itself.

#include <assert.h>
#include <iomanip>
#include <iostream>
#include <stdint.h>
#include <vector>

class Bignum
{
public:
    Bignum(int value)
    {
        assert(value >= 0 && value <= 999999999);
        parts.push_back(value);
    }

    Bignum& operator*=(int rhs)
    {
        assert(rhs >= 0 && rhs <= 999999999);
        uint32_t carry = 0;
        for (size_t i = 0; i < parts.size(); i++)
        {
            uint64_t product = (uint64_t)parts[i] * (uint64_t)rhs + carry;
            parts[i] = (uint32_t)(product % 1000000000LL);
            carry = (uint32_t)(product / 1000000000LL);
        }
        if (carry != 0)
            parts.push_back(carry);
        return *this;
    }

    friend std::ostream & operator<<(std::ostream& stream, const Bignum& num);

private:
    std::vector<uint32_t> parts;
};

inline std::ostream& operator<<(std::ostream& stream, const Bignum& num)
{
    char oldfill = stream.fill('0');
    for (std::vector<uint32_t>::const_reverse_iterator it = num.parts.rbegin(); it != num.parts.rend(); it++)
        stream << *it << std::setw(9);
    stream.fill(oldfill);
    stream.width(0);
    return stream;
}

Bignum factorial(int n)
{
    Bignum fac = 1;
    for (int i = 2; i <= n; i++)
        fac *= i;
    return fac;
}

int main(int argc, char* argv[])
{
    for (int n = 0; n <= 52; n++)
        std::cout << factorial(n) << std::endl;
    return 0;
}

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.

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.