Nakochi's blog

Calculate first 50 digits and last 100 digits of N! (Factorial Problem, data is really large, N <= 10 ^ 8）Anyone can help?
By Nakochi, 11 years ago, In English

Time Limit: 3000ms Memory Limit: 65536kb Description Now, you are given three positive A, B, C, your task is to compute the first B digits and the last C digits of the factorial of A. For example A=5, B=2, C=1. Then A! =120, so you should output 12 0 separated by one blank. Input The first line, an integer T, representing T test cases below. (T<=200). Each test case contains three integers: A (1<=A<=10^8), B (1<=B<=50) and C (1<=C<=100). Notice: No illegal case is permitted. For example, the condition A=4, B=10, C=10 is not permitted in the input data. Output For each case, output the first B digits and the last C digits of the factorial of A separated by one blank. Sample Input 2 5 2 1 8 2 2 Sample Output 12 0 40 20

I've no idea about calculating the first B digits of the factorial. Please help.Thank you. If you want to submit your code , here is the link. http://acm.ustc.edu.cn/ustcoj/problem.php?id=1265 Anybody interested？

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

Comments Comments (25)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Some interesting fact about last digits: if A>=405 answer will be all zeroes.
And for the first digits there should be sublinear algo.

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

    sublinear algo? Any detail information, if you can give me a link to some pages that introduce the algo, that would be lovely. Thank you sincerely.^_^

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Have you tried this method?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Stirling's approximation is one of my failed choices. T^T,however N is not large enough for Stirling's approximation.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Did you used your own floating point arithmetics or some standard like double?
      If last, there will be lack of precision since even C++ long double holds out around 20 decimal digits.

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

        Previously, I used double... OK, I'll try.

        → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

H-m-m, I don't believe that Stirling's approximation is accurate enough to get 100 decimal digits.

What about such combination of stupid ideas:

1) Calculate only 2*B or 1.5*B eldest digits and forget all smaller, hoping that rounding error will not be very large

2) Pre-calc and store results for different A, with step, for example, 10^5, or even 10^4. (How large is source file size limit?)

?

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

    Less than 20MB. One problem, I need to be really careful about how large B is. How about b is not too big and also not too small. However ,worth a try.Thank you.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

About the first B digits, the problem has something same to this problems in hackerrank. The solution is to calculate the first k digits of x, we calculate log10(round(x/10^k)). => Editoral of it. The function can be calculate easily if we can calculate log(n!) in O(1) or O(log(n)). About calculate log(n!) you can see here.

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

    It's likely to be what I'm looking for. I'm coding now, to see if it works out. And thanks.

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

      Maybe I run into a wrong direction.Still can not solve the problem.Since even if I can calculate log(n!)in a short time,I can't get enough precisions to guarantee that I am able to get first 400 digits of n!.Maybe, I just didn't understand this method.Any help?

      → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

You can calculate first digits using prime numbers wiki. There is about 5761455 prime numbers less than 10^8. Use Sieve of Eratosthenes to construct them in one second. Don't forget to use long arithmetics. I think first 500 digits is enough to keep to calculate correctly first 400 digits. To make your solution faster on the testing server you can precompute intermediate multiplication results for n = k, k * 2, k * 3 .... for some fixed K, e.g. k = 100000.

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

    There is about 6500 different powers for prime numbers. so you can build segment tree with partial results of p[1] * p[2] * p[3] ... . then answer one query for 6500 * log (NumOfPrimes) * BigNumDigits

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

      Got it!

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

        Would you please tell the final way with which you were successful ?

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

          Can I just show you the code？I will soon give the link.

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

          Link. I don't not whether this link works, if not, tell me.

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

            Thanks, but unfortunately the link seems to direct me to chinese language(website) which I don't know and even there is some account creation stuff. If you can share it some where else.

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

              I just find it's the easiest way to share my code.... Link

              → Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

The constraints on B is (1<=B<=50). Why theme title says about 400 first digits?

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

    Sorry, it should be 50, my mistake. What do you mean by "using prime numbers"? --Counting how many times a prime number appears in N! for every prime,and use long arithmetics to multiple them up,and everytime just save first 100 digits(as you point out, B <= 50,100 is enough)? And thank you.

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think the last 100 digits can compute by make a list ,because while N>1000,all the last digits is 0. And the first B digits ,may I use the first B digits to compute?Such as,A=8,B=2,C=1,1*2*3*4=24,then use the first B digis to factory,24*5=120->12,12*6=72->72,72*7=504->50,50*8=400->40 I have not try ,I not sure it is an enable method!!! I hope more acmer provide more and better method.

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

    Seems to be very harsh roundation, so we loose precision. For ex. A=8, B=1:
    1*2*3=6, 6*4=2(4), 2*5=1(0), 1*6=6, 6*7=4(2), 4*8=3(2). So we have contradiction between your and my examples — 8! must be starting with 40 and 3.

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

Using HolyInq`s idea, you can use BigInteger to compute the factorial of A, always taking the remainder by 10**C. It will reach zero in not so much iterations, and you can break if it happens.

Getting the first digits is the toughest part, and I am still not sure of how is the best way to achieve that. I found a lot of ideas on this page and I suggest you take a look on the 100 digits challenge, maybe it helps you: http://www.luschny.de/math/factorial/approx/SimpleCases.html

I am sorry I do not have a very good idea to solve the second part yet...

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

    Anyway，thanks。 I will take a look and learn something.

    → Reply