5
$\begingroup$

I need to find N! (mod 232-5) such that 0 ≤ N ≤ 264 for i cases, 0 ≤ i ≤ 1000 in 1 sec.

Credits: https://dmoj.ca/problem/factorial2

I am aware that I only have to handle 0 ≤ N ≤ 2 ≤ 232-6 because once N ≥ 232-5, N!≡0 (mod 232-5) . A naive solution would take O((232-6)*1000). I have also tried using Wilson’s Theorem and a naive solution, which would run in approximately O(4000000000*1000) time (Calculated from the highest point when O(N) intersects with O(232-5-N)log(N))).

I cannot find a solution to this problem with a fast enough run time. Any help would be appreciated.

$\endgroup$
7
  • $\begingroup$ According to Wolfram Alpha, $2^{32}-5$ is prime. According to this article, computing $n!\mod m$ is as hard as factoring $m$. So you should probably look for algorithm that use the primality of $2^{32}-5$. $\endgroup$ – xavierm02 Mar 10 '17 at 15:19
  • $\begingroup$ Try sorting your inputs, and so save a factor of $i$. $\endgroup$ – Yuval Filmus Mar 10 '17 at 16:07
  • $\begingroup$ Yuval's advice, plus a massive amount of brute force on a decent computer, should just about do the job on a decent home computer with say 4 cores, and a good vector unit. $\endgroup$ – gnasher729 Mar 10 '17 at 16:46
  • 1
    $\begingroup$ Using a table of size M containing strategically precomputed values of $n! \bmod{2^{32}-5}$, you can save a factor of M in the computation time, though then you can't use my previous optimization. $\endgroup$ – Yuval Filmus Mar 10 '17 at 18:53
  • $\begingroup$ geeksforgeeks.org/compute-n-under-modulo-p $\endgroup$ – Eugene Mar 10 '17 at 20:04
1
$\begingroup$

First use Yuval's advice: With p = 2^32 - 5, remove all N ≥ p (the result is 0), then sort the rest, so now you have up to 1,000 numbers in sorted order from 0 to p-1. This is trivial to do by multiplying up to almost 2^32 numbers modulo p and recording results at the right moment; that's not much above a second worth of work but more than a second.

Let's say you have r processors, and you want to use them simultaneously. The largest number is t < p. You make each processor responsible for multiplying s = ceil (t / r) numbers. For example if r = 8 and t = 2^32 - 6, then s = 2^29. Processor 0 multiplies numbers from 1 to s, processor 1 multiplies numbers from s+1 to 2s and so on. Let's say one of your N's is 3s + 15900: Processor 3 multiplies 3s+1 to 4s. At some point you record the product of numbers 3s+1 to 3s+15,900. And when all the processors are done, you multiply with the final results of processors 0, 1 and 2.

You may have vector units being able to do for example 4 operations in parallel. In that case, you would multiply r by 4, and have 8 processors calculating 4 results simultaneously.

Say you have calculated x (x+1) modulo p, the product of two numbers. How can you get (x+2)(x+3) modulo p, the next product? (x+2)(x+3)-x(x+1) = 4x + 6, so the product modulo p changes by (4x + 6) modulo p. Let d(x) = (4x + 6) modulo p. As you increase x by 2, d(x) changes by 8 (modulo p), so the products x(x+1) modulo p, (x+2)(x+3) modulo p, (x+4)(x+5) modulo p etc. can be calculated very quickly. I think that should be enough to get you below one second.

Some additions: One, if p = $2^{32}-5$ is not prime, that makes the problem just faster to solve. If all prime factors are ≤ $p^{1/2}$ then the problem is trivial because N! = 0 (modulo p) if N ≥ $2^{17}$ (must be careful in case p is the square of a prime). Otherwise let p = a·q, where a ≥ 2 and q is a prime q ≥ $p^{1/2}$, then we can calculate N! modulo p easily from N! modulo a and N! modulo q. Since $a ≤ 2^{16}$ and N! modulo a = 0 if N ≥ a, calculating N! modulo a is trivial (only 65535 products needed). b would be at most half as large as p, making the problem at least twice as fast to solve. After applying this, we can assume p is prime.

Two, Wilson's Theorem lets you cut the time in half. We now assume p is prime (having cut down the time earlier if the original p wasn't). Wilson's Theorem says (p-1)! = -1 (modulo p). Now say we want to calculate (p-k)! modulo p. We have obviously (p-k)! · ((p-k+1)·(p-k+2)· ... · (p-1)) = (p-1)!. This product is equal to (p-k)! · (-(k-1))·(-(k-2))· ... · (-1)) = (p-k)! · (k-1)! · (-1)^(k-1). The result modulo p is -1, so (p-k)!·(k-1)! = (-1)^k modulo p. So if p/2 ≤ N < p, then we let k = p - N, calculate (k-1)! modulo p, and solve N! · (k-1)! = (-1)^k modulo p. The problem is now mostly reduced to the problem of calculating N! modulo p for about 1,000 values 0 ≤ N ≤ p/2 ≤ $2^{31}$.

Three, Yuval's idea using a table with pre-calculated values N! modulo p will work if the task is to solve the problem for fixed p and different sets of 1,000 values N. If there are 1,000 values N you need 1,000k precalculated values to save a factor k. It doesn't work if p is variable. And if it is possible to use multiple processors or vector units to do k calculations in parallel, then a factor k in time can be saved. Without these savings, it's 2 billion products modulo p in 1 second.

One idea is factoring N! into a product of powers primes. There are less than 100 million primes < $2^{31}$. However, since we have 1,000 values $N < 2^{31}$, I think many primes will have to be multiplied multiple times. Doing this in one second is tough.

$\endgroup$
4
  • 1
    $\begingroup$ I'm not sure you're allowed to use several processors. The program runs on an online judge. $\endgroup$ – Yuval Filmus Mar 10 '17 at 18:49
  • $\begingroup$ Yes I forgot to mention that I am using an online grader $\endgroup$ – WIR3D Mar 10 '17 at 21:41
  • $\begingroup$ Unfortunately 2^32 -5 is prime and Wilson's Theorem only has a run time of O(2^32-5-N)log(N))) as I mentioned in my question. Also N has 2^32-6 possible values and would take 16GB to store so that's out of the question $\endgroup$ – WIR3D Mar 12 '17 at 4:28
  • $\begingroup$ @WIR3D: What are you going on about there? I wrote a very simple method where (p-k)! modulo p is easily calculated from k! modulo p, which means you don't need to calculat N! modulo p for any N > p/2. "Wilson's Theorem" doesn't have a runtime, it's something you use. And it doesn't need any storage. $\endgroup$ – gnasher729 Mar 12 '17 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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