## Modular Factorial

### December 13, 2013

This question appears from time to time as an interview question or on the coding-challenge web sites.

Write a function that calculates n! (mod p) when p is prime. Then extend the function to calculate n! (mod m) when m is not prime. Can you calculate the factorials using fewer than n−1 modular multiplications?

For instance, 1000000! (mod 1001001779) is 744950559.

Your task is to write the indicated functions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 6 Responses to “Modular Factorial”

1. Paul said

In Python. I used a few small optimizations. Of course, if n >= p (or k) than the factorial will be zero. If the mod is not for a prime, than time can be saved by checking the intermediate result. There is no point of continuing, if the intermediate result is zero. The functions return the factorial plus the number of multiplications done. For the case shown below the number of calculations can be much less than n-1 if the end result is zero.

```def fac_mod(n, p):
multiplications = 0
if n >= p:
return 0
f = 1
for i in xrange(1, n + 1):
f = f * i % p
multiplications += 1
return f, multiplications

def fac_mod2(n, k):
multiplications = 0
if n >= k:
return 0
f = 1
for i in xrange(1, n + 1):
f = f * i % k
multiplications += 1
if f == 0:
break
return f, multiplications

k = 1000005
with Timer(1):
print fac_mod(1000000, k)

with Timer(1):
print fac_mod2(1000000, k)

# (0, 1000000)
# elapsed time:  135 msec
# (0, 409)
# elapsed time: 81.6 usec
```
2. svenningsson said

``````facmod2 n p = go n 1 p
where go 0 acc p = acc
go n acc p = go (n-1) ((n*acc)`rem`p) p``````
3. jos said

There is a way to reduce the multiplications by factoring n!

eg; 100!

2: 50+25+12+6+3+1 = 97 = 64 + 32 + 1 –> M=8
3: 33+11+3+1= 48 = 32 + 16 –> M= 6 TOT=15
5: 20 +4 = 24 =16 +8 –> M=5, tot = 21
7 14+2=16 -> M=4 , tot =26
11 9 M=4, tot = 31
13 7 M=6 tot = 38
17 5 M=3 tot= 42
19 5 M=3 , tot = 46
23 4 M=2 , tot = 49
29 3 M=2, tot = 52
31 3 M=2 , tot = 55
37 2 M=1,tot = 57
41 2 M=1,tot =59
43 2 M=1,tot=61
47 2 M=1, tot=63
53 1 M=0, tot=64
59 1 M=0, tot=65
61 1 M=0, tot=66
67 1 M=0, tot=67
71 1 M=0, tot=68
73 1 M=0, tot=69
79 1 M=0, tot=70
83 1 M=0, tot=71
89 1 M=0, tot=72
93 1 M=0, tot=73
97 1 M=0, tot=74

so by factoring you can reduce the amount of modulo multiplications , on the other hand you have to do a lot divisions to calculate the factors

4. Graham said

Haskell, similar to @svenningsson, but incorporating a few optimizations from @Paul:

```facMod :: Integer -> Integer -> Integer
facMod n m = loop n 1
where loop 0 acc = acc
loop k acc | k >= m     = 0
| acc == 0   = 0
| otherwise  = loop (k - 1) ((acc * k) `mod` m)

main :: IO ()
main = print \$ 1000000 `facMod` 1001001779
```
5. treeowl said

Regarding the discussion on the second page: the last time I checked, the complexity class of integer factoring was an open problem. It’s certainly known to be in NP, but I don’t think it’s been proven NP-complete, so it’s conceivable that it is in P even if P≠NP.

6. programmingpraxis said

I didn’t say that quite right, did I. Perhaps it would be better if I said we don’t do that “because it is not possible to compute n! (mod m) in polynomial time.”