calculating large factorials

[E093605o]

Hello everbody,
I am given an integer n that can be at most 10^8. Now, I have to calculate the factorial of that number. I have been struggling with this problem for 2 days now. Can somebody help me? :)
Thanks!

[helios]

Are you sure you have to compute the entire factorial? 10^8! is a number with over 750 million decimal digits.

[lastchance]

Maybe he/she is after this one:
https://projecteuler.net/problem=754

[E093605o]

Hey, thanks for your replies. No, I'm not after the project euler problem. I got confused, sorry. n can be at most 10^3 not 10^8, you are right that number is way too large.

[againtry]

1000! =
40238726007709377354370243392300398571937486421071463254379991042
99385123986290205920442084869694048004799886101971960586316668729
94808558901323829669944590997424504087073759918823627727188732519
77950595099527612087497546249704360141827809464649629105639388743
78864873371191810458257836478499770124766328898359557354325131853
23958463075557409114262417474349347553428646576611667797396668820
29120737914385371958824980812686783837455973174613608537953452422
15865932019280908782973084313928444032812315586110369768013573042
16168747609675871348312025478589320767169132448426236131412508780
20800026168315102734182797770478463586817016436502415369139828126
48102130927612448963599287051149649754199093422215668325720808213
33186116811553615836546984046708975602900950537616475847728421889
67964624494516076535340819890138544248798495995331910172335555660
21394503997362807501378376153071277619268490343526252000158885351
47331611702103968175921510907788019393178114194545257223865541461
06289218796022383897147608850627686296714667469756291123408243920
81601537808898939645182632436716167621791689097799119037540312746
22289988005195444414282012187361745992642956581746628302955570299
02432415318161721046583203678690611726015878352075151628422554026
51704833042261439742869330616908979684825901254583271682264580665
26769958652682272807075781391858178889652208164348344825993266043
36766017699961283186078838615027946595513115655203609398818061213
85586003014356945272242063446317974605946825731037900840244324384
65657245014402821885252470935190620929023136493273497565513958720
55965422874977401141334696271542284586237738753823048386568897646
19273838149001407673104466402598994902222217659043399018860185665
26485061799702356193897017860040811889729918311021171229845901641
92106888438712185564612496079872290851929681937238864261483965738
22911231250241866493531439701374285319266498753372189406942814341
18520158014123344828015051399694290153483077644569099073152433278
28826986460278986432113908350621709500259738986355427719674282224
87575867657523442202075736305694988250879689281627538488633969099
59826280956121450994871701244516461260379029309120889086942028510
64018215439945715680594187274899809425474217358240106367740459574
17851608292301353580818400969963725242305608559037006242712434169
09004153690105933983835777939410970027753472000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000

[againtry]

@OP Somebody might have a smart algorithm but if you are just playing around out of interest then use Python print(sympy.factorial(1000))

[E093605o]

Yep, I know.
I was thinking of creating a vector<int> and incrementally multiply the contents in ascending order of the products of n!. But I think this is very slow.

[E093605o]

Thanks for your answer, againtry. Unfortunately, I cannot use python (I am not just playing around out of interest). It has to be c++ and I need to display that number.

[lastchance]

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

const int MOD = 1000000000;    // the square of this has to be small enough to fit in unsigned long long
const int WMOD = 9;            // width of field per "big digit" (up to MOD - 1)

class BigInt
{
public:
   vector<unsigned long long> digits;       // digits stored in REVERSE order;
   BigInt( unsigned long long n = 0 );      // construct from integer
};

//------------------

BigInt::BigInt( unsigned long long n )
{
   digits.clear();
   if ( n == 0 )
   {
      digits.push_back( 0 );
   }
   else
   {
      while ( n )
      {
         digits.push_back( n % MOD );
         n /= MOD;
      }
   }
}

//------------------

BigInt operator * ( const BigInt &a, const BigInt &b )
{
   BigInt result = 0;

   int asize = a.digits.size();
   int bsize = b.digits.size();

   for ( int i = 0; i < asize; i++ )        // Multiply by the ith digit of a and i tens
   {
      unsigned long long carry = 0;
      for ( int j = 0; j < bsize || carry > 0; j++ )
      {
         if ( i + j < result.digits.size() ) carry += result.digits[i+j];
         if ( j     < bsize                ) carry += a.digits[i] * b.digits[j];
         unsigned long long digit = carry % MOD;
         carry /= MOD;
         if ( i + j < result.digits.size() ) result.digits[i+j] = digit;
         else                                result.digits.push_back( digit );
      }
   }
   return result;
}

//------------------

ostream &operator << ( ostream &out, const BigInt &a )
{
   out << a.digits.back();
   for ( int i = a.digits.size() - 2; i >= 0; i-- ) out << setw( WMOD ) << setfill( '0' ) << a.digits[i];
   return out;
}

//======================================================================

int main()
{
   const int N = 1000;
   BigInt fac = 1;
   for ( int n = 2; n <= N; n++ )
   {
      fac = fac * BigInt( n );
   }
   cout << fac << '\n';
}

[E093605o]

hey thanks alot, lastchance :)