Niyati_Parekh's blog

Is there a sub-linear approach to find factorials of large numbers?
By Niyati_Parekh, history, 7 months ago, In English

Hello everyone, this is my first time writing a blog. So pardon any mistakes. I am writing this because I genuinely curious if there is sub-linear approach to find factorials of a large number (1e9) under some modulo. Like any approach better than O(n)? Such as O(n/B), O(√n) or any less/more around them.

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

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Niyati_Parekh (previous revision, new revision, compare).

→ Reply
»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As far as I know, there is no sublinear way to compute n! mod m in general. Since n! = 1 × 2 × … × n, every number contributes to the result, so you basically have to process all terms. That makes it O(n) in most cases. There are some special cases though. For example, if m is prime and n >= m, then n! == 0 (mod m). Also, when n is close to a prime modulus, Wilson’s theorem can sometimes help. But for large n like 1e9 and general m, I dont think anything better than linear time exists.

→ Reply
  • »
    »
    7 months ago, hide # ^ |
     
    Vote: I like it -11 Vote: I do not like it

    Hey! I saw the previous reply and while it's a solid baseline, it actually misses out on some high-level "magic" used in competitive programming and number theory to break that O(n) barrier. If you're looking for 10 9 specifically, you're right on the edge where O(n) might TLE (Time Limit Exceeded), but sub-linear approaches absolutely exist.

    Here is the deep dive into how we actually go sub-linear:

    1. The O( n

    ​ logn) Polynomial Approach When the modulus m is a prime p, we don't actually have to multiply every number. We can treat the factorial as a product of values of a polynomial.

    Imagine we split n into B blocks, where B≈ n

    ​ . We define a polynomial:

    P(x)=(x+1)(x+2)…(x+B)

    Now, if we evaluate this polynomial at x=0,B,2B,…,(B−1)B, we get the product of each block. For example:

    P(0)=1⋅2⋅⋯⋅B

    P(B)=(B+1)⋅(B+2)⋅⋯⋅2B

    By using Fast Multipoint Evaluation (which uses the Fast Fourier Transform or FFT), we can evaluate a degree-B polynomial at B different points in O(Blog 2 B) time. Since B= n

    ​ , your total complexity becomes roughly O( n

    ​ log 2 n). For n=10 9 ,
    n

    ​ is only about 31,622, which is well within the limits for a 1-second execution time!

    1. When n is close to the Modulus (Wilson's Theorem) If your n is very large but also very close to a prime modulus p (specifically when p−n is small), you can use a "backward" approach. Wilson's Theorem states that:

    (p−1)!≡−1(modp)

    Since (p−1)!=n!⋅(n+1)⋅(n+2)…(p−1), you can find n! by calculating the product of the small range from (n+1) to (p−1) and then finding its modular inverse. This turns an O(n) problem into an O(p−n) problem.

    1. The Prime Power "Sieving" Trick If you only need to find the exponent of a prime p in n! (like asking how many trailing zeros are in 10 9 !), you use Legendre's Formula:

    E p ​ (n!)= k=1 ∑ ∞ ​ ⌊ p k

    n ​ ⌋

    This is O(log p ​ n), which is incredibly fast—practically instantaneous for 10 9 .

    Summary Table of Approaches Scenario Complexity Technique General n<10 8 O(n) Standard Iteration Prime m, n≈10 9 O( n

    ​ logn) FFT + Multipoint Evaluation n close to m O(m−n) Wilson's Theorem + Modular Inverse n≥m O(1) Result is 0(modm) So, while the "naive" approach is linear, the mathematical reality is that we can squeeze a lot of performance out of the structure of factorials. If you're dealing with a prime modulus, that
    n

    ​ jump is your best friend.

    Would you like to see a breakdown of how the Chinese Remainder Theorem allows us to apply these tricks even when the modulus isn't prime?

    → Reply
    • »
      »
      »
      7 months ago, hide # ^ |
       
      Vote: I like it +8 Vote: I do not like it

      Thank you ChatGPT.

      Yes, please, proceed with the breakdown of how Chinese Remainder Theorem allows us to apply these tricks even when the modulus isn't prime.

      → Reply
»
7 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

you can precompute n! for n % 1e7 == 0 or n % 1e6 == 0, and it is O(1e6).

→ Reply
»
7 months ago, hide # |
← Rev. 2  
Vote: I like it +90 Vote: I do not like it

First of all, when I need to compute large factorials modulo, say, $$$m = 998\,244\,353$$$, I run it locally up to one billion and print every like 500000-th and then store this as a precomputed vector in my code (like const vector<int> facts = {1, 832944090, 373341033, 797725335, 45596018, ...}). Then I can compute any $$$k!\bmod{m}$$$ by just taking the closest precomputed factorial not exceeding $$$k$$$ and multiply by at most 500000 remaining numbers, usually that's okay for my purposes.

But answering your question, let us choose some $$$B$$$ and find the coefficients of the polynomial $$$P(x) = x(x+1)(x+2)\dots(x+B-1)$$$. It can be done in $$$O(B\log{B})$$$, see "Stirling numbers of the first kind". Then compute the values of this polynomial at points $$$1$$$, $$$B+1$$$, $$$2B+1$$$ and so on. It can be done in $$$O((m/B)\log{B}\log\max(B, m/B))$$$ or something, see "multipoint evaluation".

Now, to compute $$$k! \bmod{m}$$$, you multiply about $$$k/B$$$ precomputed values and at most $$$B$$$ single remaining values. So taking $$$B\approx\sqrt{m}$$$ gives you $$$\sqrt{m}\log^2m$$$ precalc time + $$$\sqrt{m}$$$ per query, taking $$$B\approx\sqrt{m\log{m}}$$$ gives you $$$\sqrt{m}\log^{3/2}m$$$ precalc time + $$$\sqrt{m\log{m}}$$$ per query, etc.

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

If you're processing the queries in offline, there's an even better solution: https://github.com/yosupo06/library-checker-problems/issues/1058. As stated, it runs in $$$O((Q+\sqrt{M}) \log^2(Q+\sqrt{M}))$$$ time.

For the actual fastest solution that I know, which is optimized $$$O(M+Q \log(M))$$$: https://codeforces.me/blog/entry/143279.

For the online algorithm, https://judge.yosupo.jp/submission/296988 is relatively fast for $$$O(M+Q\cdot B \log(M))$$$ (in this case $$$B = 256$$$).

→ Reply
»
7 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

I don't know if it answers Your question, but fast (say, polylogarithmic) oracle for $$$n! (mod k)$$$ would imply fast (polylogarithmic) oracle for factorization of $$$k$$$, which is thought to be hard at least on classical computer/Turing machine.

Why: binary search for $$$x$$$ over $$$[1, k]$$$, query oracle to get $$$f = x! (mod k)$$$, compute $$$gcd(f,k)$$$ (Euclid, polylog too) and compare to $$$1$$$. Smallest $$$x$$$ with $$$gcd \neq 1$$$ is the smallest prime factor $$$p$$$ of $$$k$$$. Divide $$$k$$$ by $$$p$$$ and repeat until $$$k = 1$$$ to get all factors.

Also: if entire $$$n!$$$ is needed (not just modulo): $$$n!$$$ contains $$$O(nlogn)$$$ digits, so can't be quicker than that.

→ Reply
»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thank you everyone for you support and suggestions. I will surely try them out.

→ Reply