C++ program to calculate large factorials

Question

How can I write a c++ program to calculate large factorials.

Example, if I want to calculate (100!) / (99!), we know the answer is 100, but if i calculate the factorials of the numerator and denominator individually, both the numbers are gigantically large.

Answer 1

Here's an example of how to do so:

http://www.daniweb.com/code/snippet216490.html

The approach they take is to store the big #s as a character array of digits.

Also see this SO question: http://stackoverflow.com/questions/1966077/calculate-the-factorial-of-an-arbitrarily-large-number-showing-all-the-digits

Answer 2

You can use the Gamma function instead, see the Wikipedia page which also pointers to code.

Answer 3

You can use a big integer library like gmp which can handle arbitrarily large integers.

Answer 4

To solve x!/y! for x > y:

int product = 1;
for(int i=0; i < x - y; i ++)
{
    product *= x-i;
}

If y > x switch the variables and take the reciprocal of your solution.

Answer 5

The only optimization that can be made here (considering that in m!/n! m is larger than n) means crossing out everything you can before using multiplication.

If m is less than n we would have to swap the elements first, then calculate the factorial and then make something like 1 / result. Note that the result in this case would be double and you should handle it as double.

Here is the code.

   if (m == n) return 1;

   // If 'm' is less than 'n' we would have
   // to calculate the denominator first and then
   // make one division operation
   bool need_swap = (m < n);
   if (need_swap) std::swap(m, n);

   // @note You could also use some BIG integer implementation, 
   // if your factorial would still be big after crossing some values

   // Store the result here
   int result = 1;
   for (int i = m; i > n; --i) {
      result *= i;
   }

   // Here comes the division if needed
   // After that, we swap the elements back
   if (need_swap) {
      // Note the double here
      // If m is always > n then these lines are not needed
      double fractional_result = (double)1 / result;
      std::swap(m, n);
   }

Also to mention (if you need some big int implementation and want to do it yourself) - the best approach that is not so hard to implement is to treat your int as a sequence of blocks and the best is to split your int to series, that contain 4 digits each.

Example: 1234 | 4567 | 2323 | 2345 | .... Then you'll have to implement every basic operation that you need (sum, mult, maybe pow, division is actually a tough one).

Answer 6

I asked a similar question, and got some pointers to some libraries:

http://stackoverflow.com/questions/1495856/how-can-i-calculate-a-factorial-in-c-using-a-library-call

It depends on whether or not you need all the digits, or just something close. If you just want something close, Stirling's Approximation is a good place to start.

Answer 7

Of course this particular expression should be optimized, but as for the title question, I like GMP because it offers a decent C++ interface, and is readily available.

#include <iostream>
#include <gmpxx.h>

mpz_class fact(unsigned int n)
{
        mpz_class result(n);
        while(n --> 1) result *= n;
        return result;
}

int main()
{
        mpz_class result = fact(100) / fact(99);
        std::cout << result.get_str(10) << std::endl;
}

compiles on Linux with g++ -Wall -Wextra -o test test.cc -lgmpxx -lgmp

Answer 8

By the sounds of your comments, you also want to calculate expressions like 100!/(96!*4!).

Having "cancelled out the 96", leaving yourself with (97 * ... * 100)/4!, you can then keep the arithmetic within smaller bounds by taking as few numbers "from the top" as possible as you go. So, in this case:

i = 96
j = 4
result = i
while (i <= 100) or (j > 1)
    if (j > 1) and (result % j == 0)
        result /= j
        --j
    else
        result *= i
        ++i

You can of course be cleverer than that in the same vein.

This just delays the inevitable, though: eventually you reach the limits of your fixed-size type. Factorials explode so quickly that for heavy-duty use you're going to need multiple-precision.