DaysGone's blog

Strange Negative Modulo Multiplication
By DaysGone, history, 7 years ago, In English

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

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
return (a * b) % mod

10^18 is in range of long long

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but more over when b is negative a*b < 0 and direct modulo with mod yeilds wrong ans plzz correct me if iam wrong

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well if direct mod is wrong, what is your definition of mod?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i just readed somewhere that 

        ( ((a*b) % mod + mod) % mod)

        this is the correct way what do u think mate ?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          it's good if you always want the positive mod

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            ya for negative b above statement is valid iff (a*b) is >= -10^18 but when exceeds the range overflow occurs so thats why i want to handle the overflow cases for negative values of b pllz help if anyone know how to modify above code for b <0.

            → Reply
»
7 years ago, # |
← Rev. 12   Vote: I like it +1 Vote: I do not like it

Dear DaysGone,

The following is a possible solution when b < 0.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll mulmod( ll a, ll b, const ll c )
{
    assert( c > 0 );

    ll y = 0; bool negative = false;

    if ( a < 0 )
        a = -a, negative = !negative;

    if ( b < 0 )
        b = -b, negative = !negative;

    if ( a < b )
        swap( a, b );

    for ( a %= c; b; a <<= 1, b >>= 1, a %= c )
        if ( b & 1 )
           y += a, y %= c;

    return ( negative && y ) ? c - y : y;
}

int main()
{
    ll a, b, c;

    cin  >> a >> b >> c;

    cout << ( a * b ) % c << endl;

    cout << mulmod( a, b, c );
}

The test program returns two equal numbers when b < 0.

Best wishes,

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but if i give an input 2 -2 1000000007

    your code gives first by normal way (-4) % 1e9+7 which is -4

    but if i call your function mulmod(2,-2,1000000007) which is (-4) % 1e9+7 the answer comes out to be -4 again.

    but actual ans is 1000000003

    sorry bro but i dnt think this is the correct way what do u think ?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 9   Vote: I like it +11 Vote: I do not like it

      Dear DaysGone,

      Thanks for your comment.

      Please refer to the following www.cplusplus.com Forum blog for more information about the behavior of the binary a % boperator in C++, which used to be different from the behavior of the modulus operator a mod b in discrete mathematics when a < 0.

      If you would like to have the mulmod( a, b, mod ) function behaving like the modulus operator in mathematics, whose range is the positive integer interval [ 0, mod - 1 ] and mod > 0, then it is necessary and sufficient to update the return statement of the function in the aforementioned suggested code to

          return ( negative && y ) ? ( mod - y ) : y;

      Best wishes,

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes ur absoultely right thaankss for ur help

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 7   Vote: I like it +3 Vote: I do not like it

          With pleasure.

          Please check the latest update to the suggested solution.

          This update considers all possible cases for the signs of a and b, so that negative stores the sign of a * b, and the sum-and-shift loop uses the absolute values |a| and |b|. It also includes an assertion statement to validate that c > 0 in accordance with the mathematical definition of the modulus operator. The absolute values of a and b are also swapped before the for loop when |a| < |b| so as to reduce the number of iterations.

          Please note that it is possible in C++ to compute a % b without run-time error when b < 0, but a division-by-zero exception is thrown by the executable code when b == 0. In discrete mathematics, the constraint b > 0 must be satisfied for the remainder function a mod b.

          Best wishes,

          → Reply