0
$\begingroup$

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!)$.

$\endgroup$
  • 1
    $\begingroup$ @DennisMeng Anything language-specific is off-topic here; plenty of languages have no native support for very large numbers so perhaps the question is about the data structures and algorithms that underly "bignum" libraries. $\endgroup$ – David Richerby Jun 7 '14 at 8:06
  • 1
    $\begingroup$ @Harpreet Welcome to Computer Science Stack Exchange! If you want something C-specific, this is a programming question, which is off-topic here but might be on-topic at Stack Overflow. Are you looking for C specifics or general techniques for handling very large numbers. Please edit your question (there's a link just below it) to make it more precise. $\endgroup$ – David Richerby Jun 7 '14 at 8:08
  • 2
    $\begingroup$ @Harpreet It's 158 digits. You could store the decimal version as text in an SMS message so what's the issue? $\endgroup$ – David Richerby Jun 7 '14 at 9:25
  • 2
    $\begingroup$ That, or just store "100!" as string. What are your exact requirements? (cc @DavidRicherby) $\endgroup$ – Raphael Jun 7 '14 at 9:30
  • $\begingroup$ @DavidRicherby Good to know. I was just trying to get OP to narrow down the scope of what he's asking, since the question as is seems really broad. $\endgroup$ – Dennis Meng Jun 7 '14 at 20:11
2
$\begingroup$

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!.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.