Calculate the Factorial of an Arbitrarily Large Number, Showing All the Digits

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

Getting factorial of a large number

Understand that the value is in the range of 10^5565708. It's going to take up about two megabytes of space, all by itself.

That said, Guava's BigIntegerMath.factorial(int) is good enough to handle it, and more importantly, it's actually been optimized for large factorials -- it'll do significantly better than a straightforward for loop. (Disclosure: I contribute to Guava...and wrote much of BigIntegerMath.factorial myself.)

That said, I wouldn't exactly call it fast -- my benchmarks indicate an average of 414ms for a factorial in that range -- but there isn't going to be a truly fast solution, not without extremely heavy-duty bignum libraries, and I wouldn't expect even those to be significantly faster.

That's if you need the exact value. If you can settle for the logarithm, then yeah, either use Apache's logGamma(n+1) to get ln(n!), or approximate it yourself:

double logFactorial = 0;
for (int i = 2; i <= n; i++) {
  logFactorial += Math.log(i);
}

Some rounding error will probably accumulate, but it's supposed to be an approximation anyway.

Calculate 100 factorial with all the digits

Doubles (which most Perls use) only have ~16 digits of precision. You need to use another system to get the 158 digits of precision you need.

use bigint;

This will cause Perl to automatically treat all numbers in your script as Math::BigInt objects.

If you need finer control (to treat some numbers as BigInt and some numbers as floating point) then see Krishnachandra Sharma's solution and explicitly use the Math::BigInt constructor.

Math::BigInt has a builtin factorial function, by the way:

$ perl -MMath::BigInt -e 'print Math::BigInt->bfac(100)'
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

---

Related Topics