calculate factorial of a number with 20 digits
how can I do with the algorithm of this...
calculating the result of factorial of a number with 20 digits and print the result??
calculating the result of factorial of a number with 20 digits and print the result??
On a 32-bit platform type unsigned long long has the maximum value of factorial and the maximum acceptable value correspondingly
2432902008176640000
18446744073709551615
2432902008176640000
18446744073709551615
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.
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.
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...
he said you have to find a way to keep digits in memory...
Last edited on
Perhaps your instructor was talking about a number who's factorial was 20 digits as opposed to the factorial of a 20 digit number?
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.
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.
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.
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.
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
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.
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
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.
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
Maybe long double is a good idea. It can hold up number...+e99 :)
Last edited on
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.