CODEWITHSUNDEEP
c++calgorithmmath
Sangeet Kumar
Sangeet Kumar

Reputation: 109

What is the need of the statement of (num+mod)%mod?

What is the need of the statement ans = (ans + mod) % mod in this program ?

Assume that mod = 10^9+7. This function is computing a to the power of b under mod operation in O(log(n)) complexity:

long long power(long long a, long long b)
{
    if (b == 0) 
        return 1ll;
    long long ans = power(a, b/2);
    ans = (ans * ans) % mod;
    ans = (ans + mod) % mod;
    if(b % 2 == 1)
        ans = (ans * a) % mod;
    ans = (ans + mod) % mod;
    return ans;
}

Upvotes: 7

Views: 278

Answers (1)

Petr
Petr

Reputation: 9997

The most common usage of such a construct is to make sure the result is non-negative. The standard operator% behaves differently for positive and negative arguments: for example, 4%3==1, but (-2)%3==-2, while you might expect (-2)%3==1 and (-2)/3==-1, which is mathematically more correct.

This behavior can often cause problems when modular arithmetic is used, and this trick of adding mod is often employed to obtain the mathematically more correct non-negative result. Instead of simply writing a%b, if a can be negative, one writes (a%b+b)%b.

However, its usage in the code in your question is strange. In that case, it is easier to assume that a is positive before calling the power function from the main code (for example, by making the main call like power((a%mod+mod)%mod, b)). Probably the author just wanted to get additional assurance of correctness, although it was not needed.

Upvotes: 16

Related Questions