pritishn's blog

How is this python code calculating large factorials so fast and without memory limit error?
By pritishn, history, 4 years ago, In English

Link to the problem : https://www.codechef.com/FCF32020/problems/PATHWAY
Link to the code : https://www.codechef.com/viewsolution/38865614

In this code , how can python compute factorials of (N+M) ( N+M is in the order of 10^5 ) so fast? Can anyone explain this ? How did the python interpreter optimize it ?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I googled. It's written in C and it seems that they have a clever algorithm for that too. $$$10^5!$$$ fits in memory nicely and it's not too bad if you have a fast multiplication algorithm too.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it
    $$$10^5!$$$ fits in memory nicely

    I had imagined it would be astronomically large number. But it has just around 5e5 digits.

    Thanks a lot for answering.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      $$$10^5! \le (10^5)^{10^5} = 10^{5e5}$$$, so it doesn't have that many digits. It is of course very big number, but there are different levels of being a huge number and this is still quite manageable as computations go

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, it was a stupid mistake of mine. I don't know why but thought it will have $$$10^{5e5}$$$ digits. I guess I was not thinking straight back then.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It will have 5e5 + 1 digits so if you have the available memory, python can do it

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This website calculates the factorial of 50 digit number in just a few seconds. I wonder how?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Well, this site doesn't calculate factorial of big number, it instead calculates some characteristics of that factorial (number of trailing zeroes, last non-zero digits, first digits). Obviously, one cannot hold such a big number in memory.

    → Reply