World's most popular travel blog for travel bloggers.

[Solved]: How to store factorials?

, , No Comments
Problem Detail: 

Can someone help me to store the factorial of large numbers such as 100! efficiently?

UPDATE: obviously, storing the argument rather than the factorial digits themselves achieves a significant saving. The true challenge is to find a data compression scheme that achieves a significant compression ratio, but with a lighter computational complexity than recomputing the factorial(s) from the argument.

More precisely, can you design an algorithm to produce all decimal digits of $n!$, for $n\le N$, using $o(N\log N!)$ storage and small computational cost, such as the lower bound $O(\log n!)$.

Asked By : LUSer

Answered By : Yuval Filmus

We can calculate 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000. You can store this in any way you want: as 100!, as the ASCII string 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000, as a Unicode string, or in binary in any number of formats. It all depends on what you want to do with the value. If you want to display the value on screen as a decimal, you might as well store the decimal string. If you want to do arithmetic, then you should be using a library for dealing with "big numbers" such as GMP, and in this case the library will provide its own means for storing numbers. If you're just interested in storing the expression 100!, and intend to use it in a computer algebra software (CAS), you might as well store it as just 100!.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback