-1

Is it possible to calculate Factorial(x) mod m without looping through the whole expression chain 

((1 % m) * (2 %m) * (3 % m) * ... (x % m)) % m?

To be more precise m can be 1 <= m <= 10^7 and x : 1<= x < m

Christo S. Christov
  • 2,268
  • 3
  • 32
  • 57
  • This "forum" is mostly for folks coding an algorithm and having a coding problem .. and you are unlikely to get an anser here. You might look at http://www.luschny.de/math/factorial/scala/FactorialScalaCsharp.htm' and in Mathmatica http://www.luschny.de/math/factorial/scala/FactorialScalaCsharp.htm – ErstwhileIII Feb 14 '15 at 15:04
  • 2
    You have to loop through whole chain. If not that it is not factorial! – coder hacker Feb 14 '15 at 15:04
  • @CoderHacker Yeah, I assumed this is the case >.> – Christo S. Christov Feb 14 '15 at 15:05
  • 1
    Is x bigger or smaller than m? – Patricia Shanahan Feb 14 '15 at 15:06
  • You should perform the modulo after each multiplication to keep the numbers small. This will speed up the calculation considerably. – interjay Feb 14 '15 at 15:15
  • I'm looking for a way to avoid this loop @interjay – Christo S. Christov Feb 14 '15 at 15:22
  • 1
    I doubt you can. My point was that you're performing the loop extremely inefficiently. All your modulo operations except the last one do nothing. – interjay Feb 14 '15 at 15:26
  • Oh I see now what you are talking about, yeah that's true. – Christo S. Christov Feb 14 '15 at 15:32
  • I agree with @interjay, if `x < m` always, then it is simply a factorial of `x` and then `mod`ding with `m`. – Harsh Gupta Feb 14 '15 at 15:40
  • do we know if m is prime? if not, are the prime factors readily available? – thang Feb 14 '15 at 16:23
  • @Coder Hacker: That is not correct. That you might define factorial one way does not mean there is no faster way to compute it, much as repeated squaring beats repeated multiplication for exponentiation. In fact, there are faster methods for computing the factorial. http://fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/ – Douglas Zare Feb 14 '15 at 16:35
  • 1
    See http://stackoverflow.com/questions/9727962/fast-way-to-calculate-n-mod-m-where-m-is-prime, particularly the answers by ohad and Fredrik Johansson if you want O(m^0.5+epsilon) rather than the constant improvement in Mysticial's answer. – Douglas Zare Feb 14 '15 at 16:38
  • @DouglasZare those methods require m to be prime. If m isn't prime, I guess you can factorize it, but prime factorization isn't cheap... – thang Feb 14 '15 at 16:45
  • Oops, I should have said O(x^(0.5+epsilon)) instead of O(m^(0.5+epsilon)). @thang, I don't think the basic method requires that m is prime, it's just that a prime modulus was assumed in the other question, but if it only works for prime powers, it would still be faster to factor m and then use it as long as x is not too small relative to m. – Douglas Zare Feb 14 '15 at 16:54
  • @DouglasZare the basic method requires m to be prime. That is the main statement of Wilson's theorem. Depending on the value of x, it may not be faster to factor m. As a matter of fact, it most likely is not. Remember that prime factorization is a hard problem (otherwise most crypto algorithms would fall apart). Even with the prime factors, you'd still need to apply the Chinese Remainder theorem and Euclidean algorithm, which is also not free. – thang Feb 14 '15 at 16:59
  • 1
    @thang I think you are confused. This method for computing x! mod m does not require m to be prime. The motivating example was to be able to implement a primality test using Wilson's theorem. It makes no sense to have a primality test that only works when the number is prime. Wilson's theorem was not used in the answers I cited. The Fast Fourier Transform works when the modulus is not prime. – Douglas Zare Feb 14 '15 at 17:03
  • 1
    Here is another fast factorial in Guava: http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/math/BigIntegerMath.html#factorial%28int%29 – Douglas Zare Feb 15 '15 at 09:38
  • By the way, there is a current CodeChef problem that asks about computing factorials mod m. http://www.codechef.com/FEB15/problems/STFM Was that the origin of this problem? If so, you should state that. – Douglas Zare Feb 15 '15 at 10:21
  • @DouglasZare Yes this is the reason why I'm posting this question. I don't want to state it because it is still running. – Christo S. Christov Feb 15 '15 at 10:27

1 Answers1

1

There are few fast algorithms for Factorial out there

  • so the answer is: Yes you can compute factorial without looping through all values
  • all I saw uses primes decompositions (including mine algorithm)
  • so from that it is just matter of usein mod multiplication instead of normal multiplication
  • look here: Fast exact bigint factorial is mine fast algorithm
  • and the other answer also contains link to swinging primes algorithm ...

[Notes]

  • for N! you will need a list of primes up to N
  • but the rest of code can work on arithmetics capable of holding N,m
  • so no need for huge numbers ...

[edit1] mine 32bit C++ implementations

//---------------------------------------------------------------------------
DWORD modmul(DWORD a,DWORD b,DWORD n)
    {
    DWORD _a,_b,_n;
    _a=a;
    _b=b;
    _n=n;
    asm {
        mov eax,_a
        mov ebx,_b
        mul ebx     // H(edx),L(eax) = eax * ebx
        mov ebx,_n
        div ebx     // eax = H(edx),L(eax) / ebx
        mov _a,edx  // edx = H(edx),L(eax) % ebx
        }
    return _a;
    }
//---------------------------------------------------------------------------
DWORD modfact0(DWORD n,DWORD m)         // (n!) mod m (naive approach)
    {
    DWORD i,f;
    for (f=1,i=2;i<=n;i++) f=modmul(f,i,m);
    return f;
    }
//---------------------------------------------------------------------------
DWORD modfact1(DWORD n,DWORD m)         // (n!) mod m (mine fast approach)
    {
    if (n<=4)
        {
        if (n==4) return 24;
        if (n==3) return  6;
        if (n==2) return  2;
        if (n==1) return  1;
        if (n==0) return  1;
        }
    int N4,N2,p,i,j,e; DWORD c,pp;
    N4=(n>>2)<<2;
    N2=N4>>1;
    c=modfact1(N2,m); c=modmul(c,c,m);  // c=((2N)!)^2;
    for (i=0;;i++)                      // c*= T2
        {
        p=primes_i32.dat[i];
        if (!p) break;
        if (p>N4) break;
        for (e=0,j=N4;j;e+=j&1,j/=p);
        if (e)                          // c*=p^e
            {
            if (p==2) c<<=e;
            else for (pp=p;;)
                {
                if (int(e&1)) c=modmul(c,pp,m);
                e>>=1; if (!e) break;
                pp=modmul(pp,pp,m);
                }
            }
        }
    for (i=N4+1;i<=n;i++) c=modmul(c,i,m);
    return c;
    }
//---------------------------------------------------------------------------

primes:

  • DWORD primes_i32.dat[] is precomputed sorted (ascending) list of all primes up to n

Here the result:

[  18.529 ms] slow modfact0(1000000,1299721) = 195641
[   2.995 ms] fast modfact1(1000000,1299721) = 195641
[  96.242 ms] slow modfact0(5000000,9999991) = 2812527
[  13.305 ms] fast modfact1(5000000,9999991) = 2812527
  • 1299721 is first prime close to 1000000 I found
  • if m is not prime and subresult hits zero then you can ignore the rest of multiplication to massive speed up...

Hope the result is OK have nothing to compare with ...

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • You claim your algorithm is fast. How quickly does it compute n! for n about 10^6? If you need to generate a list of primes up to n, there are roughly n/log n of them, so I don't see how you will do better than n/log n, whereas other algorithms work in time sqrt(n)log(n)^c. – Douglas Zare Feb 15 '15 at 09:40
  • @DouglasZare mine approach have primes at its disposal already. If you add computation of primes then for standard no bigint values you are right but if you try to compute even `1000!` then the primes computation time is very small in comparison to the factorial itself. because even single multiplication is on bigint values far from `O(1)` which converts the naive approach from `O(N)` to more complicated polynomes very dependend on the implementation. That is why the estimation is very hard to do..and so I was capable estimate only roughly operations (in the end of that answer). – Spektre Feb 16 '15 at 07:43
  • @DouglasZare Anyway this question is about that if it is possible to compute ModFactorial in less then N iterations so the answer is true. You do not need to use my approach, and there are Prime tables available if you need to avoid their computation. And for modular arithmetics there may be more oprimization approaches ... but without knowing the constrains of solution (ranges of x,m) is hard to advice more ... – Spektre Feb 16 '15 at 07:45
  • You say O(log n) in that answer which I don't believe. Have you implemented and tested your method in comparison with the naive approach or the fast approaches which are O(x^(0.5+epsilon))? – Douglas Zare Feb 16 '15 at 07:55
  • @DouglasZare of coarse I did, for example `1000!` took with fast approach 32ms and with naive 101ms – Spektre Feb 16 '15 at 08:03
  • @DouglasZare The `O(log(N))` is for not accounting the bigint problems (and I wrote that it is just nearing to it not is it) ... when you look at the therms it is almost dividing by 2 .... which is `O(log(N))` but the rest is slowing that down up to a point ... to safely measure that you need to apply big enough numbers and that will screw direct complexity dependency of implementation and algorithm as I wrote before... If you know how to estimate complexity for bigint implementation then give it a shot I would be curios myself (the constant time is not constant with arbitrary bigints). – Spektre Feb 16 '15 at 08:21
  • Fredrik Johansson claimed 3.1ms for computing 1,000,000! and although his computer might be faster than yours so the figures are not directly comparable, I think the advantage of using something that runs in sqrt(x)log(x)^c instead of x/log(x) becomes clear if you look at the values of x required for this problem. – Douglas Zare Feb 16 '15 at 08:23
  • I don't see how O(log n) could be right even if you assume you can do bigint calculations in constant time. You have x/(log x) primes and you are doing at least one step for each prime, correct? – Douglas Zare Feb 16 '15 at 08:25
  • @DouglasZare You are comparing `n!` with `(n!) mod m` that is not a good idea ... – Spektre Feb 16 '15 at 08:46
  • Ah, right, his calculations were of (n-1)! mod n. What times do you get if you calculate mod m instead? What timings do you get on the size of inputs requested in this question, with x and m up to 10^7? There is a time limit for this problem in the CodeChef challenge. – Douglas Zare Feb 16 '15 at 09:07
  • @DouglasZare did not need such kind of computation myself so I did not code the `(n!) mod m`yet and do not have time/mood for it for now ... The added constraints on solution implies 32bit arithmetics so no bigints are needed and primes up to 10^7 are easily cached in memory... so it should be pretty fast in comparison to bigint non mod version ... – Spektre Feb 16 '15 at 09:21
  • @DouglasZare Did bug me a bit so I did the implementation anyways see edit1 in my answer – Spektre Feb 16 '15 at 10:57
  • @Chris added some code and measurements to answer – Spektre Feb 16 '15 at 11:01
  • Ok, it looks really good really. – Christo S. Christov Feb 16 '15 at 12:28