Strange Negative Modulo Multiplication

Правка en1, от DaysGone, 2018-02-10 09:34:22

Hello everyone i just came over to this problem somewhere that if i have two very very large numbers (10^9) and i want to multiply under some modulo mod...

then we have snippet like this works :

ll mulmod(ll a, ll b, ll mod)
{
    ll res = 0; // Initialize result
    a = a % mod;
    while (b > 0)
    {
        // If b is odd, add 'a' to result
        if (b % 2 == 1)
            res = (res + a) % mod;
 
        // Multiply 'a' with 2
        a = (a * 2) % mod;
 
        // Divide b by 2
        b /= 2;
    }
 
    // Return result
    return res % mod;
}

But how to handle this when b is large negative number of the order (-10^9).. plzz help thanks

Теги number theory, modulo multiplication

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский DaysGone 2018-02-10 09:34:22 759 Initial revision (published)