Modular Factorial

December 13, 2013

This is a trick question. There is no better algorithm, regardless whether the modulus is prime or composite, than to calculate the modulus after each multiplication:

(define (mod-fact n m)
  (let loop ((k 2) (p 1))
    (if (< n k) p
      (loop (+ k 1) (modulo (* p k) m)))))

If it was possible to compute n! (mod m) in polynomial time, then it would be simple to factor integers in polynomial time: Given an integer m, the smallest f such that gcd(f! (mod m), m) > 1 is the smallest prime factor of m. For every n > f, every gcd(n! (mod m), m) is greater than 1, so we can use binary search to find f, reducing the task of factoring integers to the task of computing n! (mod m). Of course, we don’t do that because there is no polynomial-time algorithm to compute modular factorizations.

> (mod-fact 1000000 1001001779)
744950559

You might be amused to search for this task on the internet and see the complicated solutions that people have developed in the name of efficiency. You can run the program at http://programmingpraxis.codepad.org/HZwVjALJ.

About these ads

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

    Haskell:

    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.”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: