Calculating large factorials in C++

Question

Hi all, I understand this is a classic programming problem and therefore I want to be clear I'm not looking for code as a solution, but would appreciate a push in the right direction. I'm learning C++ and as part of the learning process I'm attempting some programming problems. I'm attempting to write a program which deals with numbers up to factorial of 1billion. Obviously these are going to be enormous numbers and way too big to be dealing with using normal arithmetic operations. Any indication as to what direction I should go in trying to solve this type of problem would be appreciated.

I'd rather try to solve this without using additional libraries if possible

Thanks

PS - the problem is here http://www.codechef.com/problems/FCTRL

---

Here's the method I used to solve the problem, this was achieved by reading the comments below:

Solution -- The number 5 is a prime factor of any number ending in zero. Therefore, dividing the factorial number by 5, recursively, and adding the quotients, you get the number of trailing zeros in the factorial result

E.G. - Number of trailing zeros in 126! = 31

126/5 = 25 remainder 1

25/5 = 5 remainder 0

5/5 = 1 remainder 0

25 + 5 + 1 = 31

This works for any value, just keep dividing until the quotient is less than 5

Answer 1

As you'll find in other answers, you need a Big Integer library. A very popular implementation is GNU's MP.

Concerning the real problem, I think there's a simple mathematical way to find the answer without actually calculating the factorial.

Answer 2

To start you off, you should store the number in some sort of array like a std::vector (a digit for each position in the array) and you need to find a certain algorithm that will calculate a factorial (maybe in some sort of specialized class). ;)

Answer 3

You need a "big number" package - either one you use or one you write yourself.

I'd recommend doing some research into "large number algorithms". You'll want to implement the C++ equivalent of Java's BigDecimal.

Another way to look at it is using the gamma function. You don't need to multiply all those values to get the right answer.

Answer 4

Hint: you may not need to calculate N! in order to find the number of zeros at the end of N!

Answer 5

This isn't a good answer to your question as you've modified it a bit from what I originally read. But I will leave it here anyway to demonstrate the impracticality of actually trying to do the calculations by main brute force.

One billion factorial is going to be out of reach of any bignum library. Such numbers will require more space to represent than almost anybody has in RAM. You are going to have to start paging the numbers in from storage as you work on them. There are ways to do this. The guy who recently calculated π out to 2700 billion places used such a library

Answer 6

To solve this question, as Chris Johnson said you have to look at number of 0's.

The factors of 10 will be 1,2,5,10 itself. So, you can go through each of the numbers of N! and write them in terms of 2^x * 5^y * 10^z. Discard other factors of the numbers.

Now the answer will be greaterof(x,y)+z.

One interesting thing I learn from this question is, its always better to store factorial of a number in terms of prime factors for easy comparisons.

To actually x^y, there is an easy method used in RSA algorithm, which don't remember. I will try to update the post if I find one.

Answer 7

Do not use the naive method. If you need to calculate the factorial, use a fast algorithm: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Answer 8

Skimmed this question, not sure if I really got it right but here's a deductive guess:

First question - how do you get a zero on the end of the number? By multiplying by 10.

How do you multiply by 10? either by multiplying by either a 10 or by 2 x 5...

So, for X! how many 10s and 2x5s do you have...?

(luckily 2 & 5 are prime numbers)

edit: Here's another hint - I don't think you need to do any multiplication. Let me know if you need another hint.

Answer 9

I think that you should come up with a way to solve the problem in pseudo code before you begin to think about C++ or any other language for that matter. The nature of the question as some have pointed out is more of an algorithm problem than a C++ problem. Those who suggest searching for some obscure library are pointing you in the direction of a slippery slope, because learning to program is learning how to think, right? Find a good algorithm analysis text and it will serve you well. In our department we teach from the CLRS text.