How do I find factorials of large numbers modulo 1000000007 in C++?

Question

Find the factorial of large number modulo 1000000007

In Python or Java, it's no problem, but in C++ there are overflow constraints.

This is the code I've tried:

#include<iostream>
 #define ull long long int
 #define mod 1000000007
 ull fact(ull n)
 {
           if(n==1 || n==0) return 1;
           return ((n%mod)*(fact(n-1)%mod)%mod);
 }
 int main()
 {
              cout<<fact(50000)<<endl;
              return 0;
 }

But the output is invalid.

Answer 1

check this code. There should not be any problem as unsigned long long can easily store any modular value 10^9+7. I mean if you are using modular value instead of actual one then why should you even care about it? (It's known that 10^9+7 can be stored in ull).

 ull ans;
    ull fact(int n)
    {
        if(n<INT_MAX)
        {
        ans=1;
        for(int i=2;i<=n;i++)
         ans=(ans*i)%mod;
         return ans;
        }
    }

This will simply do the factorial.

Here n< INT_MAX condition is used because if we don't use it then if n=INT_MAX the for loop's index increment(i++) may result in inceasing the value of INT_MAX which will make it 0. So the condition will never be false and it will run into infinite loop.

Note: If you want to precisely calculate the factorial in c++ you may take an array of 1000 chars where each of the char represent a digit. then you will multiply gradually to get the result. n*(n-1)*..2*1

Note: If you are making many recursive calls then it may cause overflow in stack memory as each function call results in pushing a frame(that contains it's return points etc).

Answer 2

If x!! = 1 * 3 * 5 * 7 * 9 * 11 * ..., then 2x! = 2x!! * 2^x * x!.

This gives us a more efficient factorial algorithm.

template<ull mod>
struct fast_fact {
  ull m( ull a, ull b ) const {
    ull r = (a*b)%mod;
    return r;
  }
  template<class...Ts>
  ull m( ull a, ull b, Ts...ts ) const {
    return m( m( a, b ), ts... );
  }
  // calculates x!!, ie 1*3*5*7*...
  ull double_fact( ull x ) const {
    ull ret = 1;
    for (ull i = 3; i < x; i+=2) {
      ret = m(i,ret);
    }
    return ret;
  }
  // calculate 2^2^n for n=0...bits in ull
  // a pointer to this is stored statically to make calculating
  // 2^k faster:
  ull const* get_pows() const {
    static ull retval[ sizeof(ull)*8 ] = {2%mod};
    for (int i = 1; i < sizeof(ull)*8; ++i) {
      retval[i] = m(retval[i-1],retval[i-1]);
    }
    return retval;
  }
  // calculate 2^x.  We decompose x into bits
  // and multiply together the 2^2^i for each bit i
  // that is set in x:
  ull pow_2( ull x ) const {
    static ull const* pows = get_pows();
    ull retval = 1;
    for (int i = 0; x; ++i, (x=x/2)){
      if (x&1) retval = m(retval, pows[i]);
    }
    return retval;
  }
  // the actual calculation:
  ull operator()( ull x ) const {
    x = x%mod;
    if (x==0) return 1;
    ull result = 1;
     // odd case:
    if (x&1) result = m( (*this)(x-1), x );
    else result = m( double_fact(x), pow_2(x/2), (*this)(x/2) );
    return result;
  }
};
template<ull mod>
ull factorial_mod( ull x ) {
  return fast_fact<mod>()(x);
}

live example

A faster version could reuse results of x!!, as those are repeated quite often.

Caching live example, which is about 2x as fast as the above for large n by caching x!! values reasonably smartly. Every call to double_factorial(n) creates lg k cache entries, where k is the distance between n and the largest old cache entry. As k is bounded by n. This in practice seems to reduce the weighted "cache misses" to nearly zero after the first call: the first calculation of n!! injects enough cached entries that we don't burn significant amounts of time on later calculations of !!.

This optimized version is about 41% faster than a naive iterative implementation (basically all of the time is spent calculating the first n!!).

Further improvements would probably involve making the first x!! calculation faster, with probably marginal improvements from optimizing the cache. The next question: how do you make x!! faster?