Optimising code for modular arithmetic

Question

I am trying to calculate below expression for large numbers.

N!/((N/2)!(N/2)!)

Since the value of this expression will be very large, I just need the value of this expression modulus some prime number. Suppose the value of this expression is x and I choose the prime number 1000000007; I'm looking for x % 1000000007.

Here is my code.

#include<iostream>
#define MOD 1000000007
using namespace std;
int main()
{
    unsigned long long A[1001];
    A[2]=2;
    for(int i=4;i<=1000;i+=2)
    {
        A[i]=((4*A[i-2])/i)%MOD;
        A[i]=(A[i]*(i-1))%MOD;

    while(1)
    {
        int N;
        cin>>N;
        cout<<A[N];
    }
}

But even this much optimisation is failing for large values of N. For example if N is 50, the correct output is 605552882, but this gives me 132924730. How can I optimise it further to get the correct output?

Note : I am only considering N as even.

As per answers it looks like there is nothing much that can be done to improve this code.I'll try using some other formula instead. — g4ur4v, Feb 06 '13 at 19:40
Possible duplicate of [Fast way to calculate n! mod m where m is prime?](http://stackoverflow.com/questions/9727962/fast-way-to-calculate-n-mod-m-where-m-is-prime). Also, this is an even better fit, but has no answers: [How to calc nCk % P for a big prime p and very big N?](http://stackoverflow.com/questions/14475139) — BlueRaja - Danny Pflughoeft, Feb 06 '13 at 21:28

user448810 · Answer 1 · 2016-01-10T16:44:45.150

When you do modular arithmetic, there is no such operation as division. Instead, you take the modular inverse of the denominator and multiply. The modular inverse is computed using the extended Euclidean algorithm, discovered by Etienne Bezout in 1779:

# return y such that x * y == 1 (mod m)
function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q, r := divide(b, x)
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

The divide function returns both quotient and remainder. All of the assignment operators given above are simultaneous assignment, where all of the right hand sides are computed first, then all of the left hand sides are assigned simultaneously. You can see more about modular arithmetic at my blog.

score 1 · Answer 2 · edited May 23 '17 at 11:44

For starters no modulo division is needed at all, your formula can be rewrited as follows:

N!/((N/2)!^2) =(1.2.3...N)/((1.2.3...N/2)*(1.2.3...N/2)) =((N/2+1)...N)/(1.2.3...N/2))
- ok now you are dividing bigger number by the smaller
- so you can iterate the result by multiplicating divisor and divident
- so booth sub results have similar magnitude
- any time both numbers are divisible 2 shift them left
- this will ensure that the do not overflow
- if you are at the and of (N/2)! than continue the the multiplicetion only for the rest.
- any time both subresults are divisible by anything divide them
- until you are left with divison by 1
- after this you can multiply with modulo arithmetics till the end normaly.
for more advanced approach see this.
- N! and (N/2)! are decomposable much further than it seems at the first look
- i had solved that for some time now,...
- here is what i found: Fast exact bigint factorial
- in shortcut your terms N! and ((N/2)!)^2 will disappear completely.
- only simple prime decomposition + 4N <-> 1N correction will remind

solution:

I. (4N!)=((2N!)^2) . mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]
II. (4N)!/((4N/2)!^2) = (4N)!/((2N)!^2)
----------------------------------------
I.=II. (4N)!/((2N)!^2)=mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]

the only thing is that N must be divisible by 4 ... therefore 4N in all terms.
if you have N%4!=0 than solve for N-N%4 and the result correct by the misin 1-3 numbers.

hope it helps

Optimising code for modular arithmetic

2 Answers2