CODEWITHSUNDEEP
cmodulus
Surajeet Bharati
Surajeet Bharati

Reputation: 1433

modulo arithmetic steps for this program

I have written this code in C where each of a,b,cc,ma,mb,mcc,N,k are int . But as per specification of the problem , N and k could be as big as 10^9 . 10^9 can be stored within a int variable in my machine. But internal and final value of of a,b,cc,ma,mb,mcc will be much bigger for bigger values of N and k which can not be stored even in a unsigned long long int variable.

Now, I want to print value of mcc % 1000000007 as you can see in the code. I know, some clever modulo arithmetic tricks in the operations of the body of the for loop can create correct output without any overflow and also can make the program time efficient. Being new in modulo arithmetic, I failed to solve this. Can someone point me out those steps? 

ma=1;mb=0;mcc=0;
for(i=1; i<=N; ++i){
    a=ma;b=mb;cc=mcc;
    ma = k*a + 1;
    mb = k*b + k*(k-1)*a*a;
    mcc = k*cc + k*(k-1)*a*(3*b+(k-2)*a*a);
}
printf("%d\n",mcc%1000000007);

My attempt:

I used a,b,cc,ma,mb,mcc as long long and done this. Could it be optimized more ??

ma=1;mb=0;cc=0;
ok = k*(k-1);
for(i=1; i<=N; ++i){
    a=ma;b=mb;
    as = (a*a)%MOD;

    ma = (k*a + 1)%MOD;

    temp1 = (k*b)%MOD;
    temp2 = (as*ok)%MOD;
    mb = (temp1+temp2)%MOD;

    temp1 = (k*cc)%MOD;
    temp2 = (as*(k-2))%MOD;
    temp3 = (3*b)%MOD;
    temp2 = (temp2+temp3)%MOD;
    temp2 = (temp2*a)%MOD;
    temp2 = (ok*temp2)%MOD;
    cc = (temp1 + temp2)%MOD;
}
printf("%lld\n",cc);

Upvotes: 1

Views: 100

Answers (2)

marom
marom

Reputation: 5230

That's a good exercise to build a template class along these lines:

template <int N>
class modulo_int_t
{
public:
    modulo_int_t(int value) : value_(value % N) {}
    modulo_int_t<N> operator+(const modulo_int_t<N> &rhs)
    {
        return modulo_int_t<N>(value_ + rhs.value) ;
    }
    // fill in the other operations
private:
    int value_ ;
} ;

Then write the operations using modulo_int_t<1000000007> objects instead of int. Disclaimer: make use of long long where appropriate and take care of negative differencies...

Upvotes: 0

martin
martin

Reputation: 3239

Let's look at a small example:

mb = (k*b + k*(k-1)*a*a)%MOD;

Here, k*b, k*(k-1)*a*a can overflow, so can the sum, taking into account

(x + y) mod m = (x mod m + y mod m) mod m

we can rewrite this (x= k*b, y=k*(k-1)*a*a and m=MOD)

mb = ((k*b) % MOD + (k*(k-1)*a*a) %MOD) % MOD

now, we could go one step futher. Since 

x * y mod m = (x mod m * y mod m) mod m

we can also rewrite the multiplication k*(k-1)*a*a % MOD with with x=k*(k-1) and y=a*a to

((k*(k-1)) %MOD) * ((a*a) %MOD)) % MOD

I'm sure you can do the rest. While you can sprinkle % MOD all over the place, you should careful consider whether you need it or not, taking John's hint into account:

Adding two n-digit numbers produces a number of up to n+1 digits, and multiplying an n-digit number by an m-digit number produces a result with up to n + m digits.

As such, there are places where you will need use modulus properties, and there are some, where you surely don't need it, but this is your part of the work ;).

Upvotes: 2

Related Questions