Is there any way to calculate factorials of large no ie of about n<500

[anshulgupta]

occurence of each digit ie number of 0,1,2... in n! have to be calculated

[Dheeraj Joshi]

Have you written any code for this? Or asking us to write the code?
You might face datatype size limitation.

Regards
Dheeraj Joshi

Note: You may try long long int.

[newb16]

long long int will bork on n=30. So... custom long integer only.
Numbers that divide by 10, like p*10 may be replaced with p, keeping track of 'lost' trailing zeroes.

[Banfa]

The only way to do this is to write your own long integer that can handle large enough numbers. If you are using C++ the good news is that this is quite a common task so there are already a fair few unlimited precision integer implementations out there.

If you google an appropriate topic you will find lots of code snipets across the web as well as some actual implementations such as BigInt available in SourceForge.

[donbock]

How accurate does your computation need to be? Can you tolerate the imprecision of floating point?

[newb16]

As he needs to calculate occurrence count for each digit, floating point won't work.

[jkmyoung]

To add to newb16's earlier point, do not even multiply the 5's in if possible. Calculate the number of trailing zeroes before hand.

Let fives = n/5; // (rounded down, integer arithmetic)
five2s = fives/5;
five3s = five2s/5; // 125. don't need a five4s, since that would be 625, > 500.
totalFives = fives+five2s+fi ve3s
Then you will have totalFives trailing zeroes.

When multiplying in a number, say i, remove the multiples of 5.
while (i%5 == 0) i /= 5;
Also, keep a 2 count. and don't multiply these in until necessary.
if ((i&1 == 0) && (twoCount < totalFives)) i >>= 1;

[Banfa]

I can see you equation works jkmyoung from experiment but you you provided a proof/reason or a link to one?

[jkmyoung]

Do you mean with the multiples of 5, or with the cancelling out with 2's? Or the calculation of the number of trailing zeroes?

As a warning to anshulgupta : Do the problem the simple way first, then optimize.

Note, want one following clarification to the code:

product = 1;
for (j = 2; j < n; j++){
 i = j;   //set a different variable to the multiplier before 
          // you do the operations on them. eg i/=5 etc...
 do simplifications.
 multiply product by i.

Otherwise you'll constantly be multiplying 2, 3, 4, 1, 2, 3, 4, 1, etc..

[Banfa]

Sorry I meant the fives.

[jkmyoung]

Don't know if my explanation will just lead to more confusion.
Prime factorize n!.
1 * 2 * 3 * 4 * 5 * ... * n
= 1 * 2 * 3 * (2*2) * 5 * (3*2) * 7 * (2*2*2) * (3*3) * (2*5) *... * n
Take the first multiple of 5 from each number that has it. (every 5th number)
There will be exactly [fives] of these multiples, where [fives] is calculated above.
= 1 * 2 * 3 * (2*2) * 1 * (3*2) * 7 * (2*2*2) * (3*3) * (2*1) *...

Then take the second multiple of 5 from each number that still has one. (every 25th number still has a multiple of 5)
There will be exactly [five2s] of these.
etc...

Since we are taking a 5 from each factor each time, during each round we can never take a factor of 5 from a number that hasn't had a factor of 5 taken from it in each of the previous rounds; otherwise, the factor of 5 would already have been taken then!
======
To prove all multiples of 5 cancel with some power of 2:
Each factor of 5 corresponds to a factor of 2 like so
Take all natural numbers i, where 5i < n
2i < 5i < n, so is 5i exists as an individual number in the multiplication, so does 2i.
Take the 5 from 5i and the 2 from 2i and put them aside.

But then you say, what about a number that has 2 factors of 5? eg 5*5*i,
Well 2*2*i < 5*5*i.

Notice that 10 is used twice: Once as a multiple of 5, (cancelling against 2*2=4). Once as a multiple of 2, (cancelling against 5*5=-25) .

4 cancels twice as a multiple of 2. Once as a multiple of 2, (against 10) and once as a multiple of 4, (against 25)

25 cancels both multiples of 5. Once against 10, and once against 4.
===
so any number i*5^j, cancels with numbers i*2^j, i*2^(j-1)*5, i*2^(j-2)*5^2... i*2*5^(j-1)
Notice, (if we count by the powers of 2), there are exactly j terms, cancelling out with each of the j multiples of 5 in i*5^j
==========