calculate factorial of a number with 20 digits

Dec 19, 2012 at 10:29am
how can I do with the algorithm of this...

calculating the result of factorial of a number with 20 digits and print the result??
Dec 19, 2012 at 12:57pm
On a 32-bit platform type unsigned long long has the maximum value of factorial and the maximum acceptable value correspondingly

2432902008176640000
18446744073709551615
Dec 19, 2012 at 1:21pm
The factorial of large numbers is not easy for two reasons.
1. the number of digits involved rapidly grows very large.
2. the number of individual multiplications required is also very large.

If your number has 20 digits, the best you could aim for would be an estimate, for example using Stirlings approximation.
http://hyperphysics.phy-astr.gsu.edu/hbase/math/stirling.html

Even that may prove problematic. You will need to use a large-number library even to get the estimate, and not all libraries will be able to handle the size of the exponents.

Certainly taken at face value the task is impossible, printing the full result would not be practical, even storing the result in a file may require more storage than is available.
Dec 19, 2012 at 1:26pm
See if you can use this

https://mattmccutchen.net/bigint/
Dec 19, 2012 at 1:46pm
Note, the result will have about 10 billion digits.
Dec 23, 2012 at 5:38am
i know them ... my teacher said it is possible to calculate this by Arrays and a special algorithm
he said you have to find a way to keep digits in memory...
Last edited on Dec 23, 2012 at 5:39am
Dec 23, 2012 at 6:40am
Perhaps your instructor was talking about a number who's factorial was 20 digits as opposed to the factorial of a 20 digit number?
Dec 23, 2012 at 6:59am
There are large number arithmetic libraries that already exist. If you're on windows, grab MPIR (www.mpir.org), or GMP (www.gmplib.org) the *nix equivalent. (they're both the same library, MPIR was forked off of gmp for windows development.)

anyway, MPIR/GMP can handle an outrageously large digit amount. As far as I was aware (though i may be wrong), you're only limited by the amount of memory your computer has.
All maths I've ever done that involved digits larger than an unsigned int max size I've done with MPIR, and it's worked flawlessly (esp. useful for things like project euler).

Hope I could help.
Dec 23, 2012 at 8:57am
Again, actually calculating this is out of the question. See
http://www.wolframalpha.com/input/?i=log2%28%2810%5E20%29%21%29
and
http://www.wolframalpha.com/input/?i=10%5E10%5E1.3284+bits
In particular, look at "Comparisons as information" bit.
Dec 23, 2012 at 12:21pm
Actually, I'm pretty certain that Cire's interpretation is correct. It is the result which will have 20 digits, not the number itself.

Using type unsigned long long, which is (at least) 64 bits, that means the biggest factorial which can be calculated is 20! = 2432902008176640000. That result has just 19 digits.

Well, since there are a few trailing zeros, it is possible to go a little bit further, up to about 23! to make full use of precision available. Beyond that, as others have suggested, you'd need to use special large-number processing.
Last edited on Dec 23, 2012 at 3:11pm
Dec 23, 2012 at 3:00pm
Go here :
blog.codechef.com/2009/07/02/tutorial-for-small-factorials/
Dec 24, 2012 at 1:53pm
If we take the alternative interpretation, that the number itself has 20 digits and we want to find the factorial, lets consider how many digits there would be.

Using Stirlings approximation, if the number is 100000000000000000000, then the factorial would have 1956570551809674817246 digits.

Let's say the computer could arrive at 1 million more digits each second, it would take 62 million years to calculate the result. If we store the result on a 2 TB hard drive, it would require 978285275 such drives to hold the result.

If instead the number is printed out, using digits 1mm high and 1mm wide, it would require a piece of paper with an area of 1956570551 square km, which is roughly 4 times the surface area of planet Earth.


Last edited on Dec 24, 2012 at 3:18pm
Dec 24, 2012 at 2:01pm
Maybe long double is a good idea. It can hold up number...+e99 :)
Last edited on Dec 24, 2012 at 2:05pm
Dec 24, 2012 at 2:06pm
You are expected to create a BigNum class to do the math, then use it to solve the problem.
Topic archived. No new replies allowed.