Find factorial n modulo m faster than O(n)

Question

How can I find (n!) % m faster than O(n)?

1 <= n <= 1e18

1 <= m <= 1e6

For small `m`, `m <= n`, `(n! mod m) == 0` that's why whenever `n >= 1e6` you can just return `0` and in the worst case you have `O(m)` time complexity — Dmitry Bychenko, May 15 '22 at 07:41
You can use any Fast Factorial algorithm like [this one](https://stackoverflow.com/a/18333853/2521214) ... you just use modlular arithmetics so no need for bigints so the resulting complexity will be somwhere between `O(log2(n))` and `O(n)` but much less than `O(n)` ... — Spektre, May 16 '22 at 07:07

Dmitry Bychenko · Accepted Answer · 2022-05-15T07:54:53.113

5

You can easily have O(m) time complexity in the worst case (when m is a prime) and it seems to be good enough since you have m <= 1e6 (while n can be up to 1e18). Note, that when n >= m

 n! = 1 * 2 * ... * m * ... * n
                    ^
         factorial is divisible by m

and that's why

 n! % m == 0       # whenever n >= m

Another implementation detail is that you don't have to compute n! % m as 1 * 2 * ... * n % m but you can do it as ((..(1 % m) * 2 % m) ... * n % m) in order not to deal with huge numbers.

C# code example

private static int Compute(long n, long m) {
  if (n >= m)
    return 0;

  long result = 1;

  // result != 0 - we can well get 0 and stop looping when m is not prime 
  for (long d = 2; d <= n && result != 0; ++d) 
    result = (result * d) % m;

  return result;
}

edited May 15 '22 at 07:54

answered May 15 '22 at 07:48

Dmitry Bychenko

180,369
20
160
215

Why do you say "when m is a prime"? – Kelly Bundy May 15 '22 at 15:33
@Kelly Bundy: When `m` is prime, then we can guarantee, that all factorials `1!, 2!, ... (m - 1)!` are *not divisible* by `m` (and we have to compute remainders). If m! is not a prime it can occure that starting from some `k!` (`k < m`) all the factorials are divisible by `m`. For instance: `m = 6` (not a prime) and we have `3! == 6` divisibe by `m = 6`. So starting from `3` (not from `m - 1 == 5`) all factorials are divisible by `6` – Dmitry Bychenko May 15 '22 at 17:28
But it's still O(m). – Kelly Bundy May 15 '22 at 17:33
@Kelly Bundy: yes, for arbitrary `m` we have `O(m)` time complexity; *prime* `m` is the worst case - we have to compute till `(m - 1)!`, if `m` is not prime we will stop earlier – Dmitry Bychenko May 15 '22 at 17:37
Ah, ok. To me, the sentence reads as *"You can do it in O(m) if m is a prime [and if it's composite, it takes more time]"*. – Kelly Bundy May 15 '22 at 18:33

score 0 · Answer 2 · answered May 15 '22 at 13:29

As explained by Dmitry, you can suppose than m<n. Let p1....pk the list of primes smaller or equal to m. Then m! mod n=(p1^a1.p2^a2....pk^ak)mod n=(p1^a1)mod n.(p2^a2 mod n)....(pk ^ak mod n) (mod n) for some a1.... ak that I'll let you find by yourself.

Using https://en.wikipedia.org/wiki/Modular_exponentiation, you can then compute m! (mod n).

Find factorial n modulo m faster than O(n)

2 Answers2