(a*b)%m splitting the operands

Question

I was performing (a*b)%m but all a,b and m are of order 10^18.

It is not possible to multiply a*b or even multiply (a%m * b%m) because m is also of order 10^18.

I believe it would be unnecessary to convert them into strings and then multiply them as strings,take the mod and then return back as long long int.

I got this question and there the accepted solution was to split my operands. (Please see the linked post). However I didn't understand the explanation of bit shifting that he mentioned.

I wrote a function to calculate the product of a and b modulo mod.

/*
   a=a1+k*a2
   b=b1+k*b2
   (a1+k*a2)*(b1+k*b2) % c = a1*b1 % c + k*a1*b2 % c + k*a2*b1 % c + k*k*a2*b2 % c
*/

ull MAM(ull a,ull b,ull mod)//multiply and mod;ull: unsigned long long
{
   ull a1,a2,b1,b2;
   ull k=4294967296; //2^32
   a1=a%k;
   a2=a/k;
   b1=b%k;
   b2=b/k;
   ull ans = (a1*b1)%mod + (((a1*k)%mod)*b2) %mod + (((k*a2)%mod)*b1)%mod + (((k*k)%mod)*((a2*b2)%mod))%mod;
   return ans;
}

But this wouldn't work without the shifts.Someone please explain the bit shifts that answer is talking about.

Jarod42 · Accepted Answer · 2015-08-02T19:53:35.983

With:

(((a1 * k) % mod) * b2) % mod

mod can be bigger than 2 ** 32, so (((a1 * k) % mod) * b2) can overflow.

as k == 2 ** 32 so (k * a1 * b2) % mod is ((a1 * b2) % mod) * (k % mod) % mod (the outer multiplication may still overflow, so split k in 2*2*...*2)

so

(((((a1 * b2) % mod) * 2) % mod) * 2) % mod)...
     ^^^^^^^^^^^^^^
     named x

if x < 2 ** 63 then 2 * x doesn't overflow and we can do our iteration (2 * x) % mod.
if x >= 2 ** 63 then 2*x overflows, but we have then 2 ** 63 <= mod (and we have x < 2 ** 64) so (2 * x) % mod can be compute as 2 * x - mod or written without overflow as x - (mod - x).

So the code becomes

const std::uint64 limit = 0x1000000000000000;
std::uint64_t x = (a1 * b2) % mod;
for (int i = 0; i != 32; ++i) {
    if (x < limit) {
        x = (2 * x) % mod; // No overflow
    } else {
        x -= mod - x;      // Manage overflow
    }
}

Similarly for a2 * b1 * k and a2 * b2 * k * k

I hope it is more clear now.

If you're going to do it that way, you're probably better off with `z = (z >= mod) ? (z - mod) : z` than `z = z % mod` — , Aug 02 '15 at 19:48
This is a good explanation :) I forgot to mention that addition can also overflow so one needs to implement addition modulo m carefully, but this is a bit easier than multiplication. — n. m. could be an AI, Aug 03 '15 at 03:08

rcgldr · Answer 2 · 2015-08-03T01:05:10.940

The bit shift equivalents to this would be a1 = a & 0xffffffffull; a2 = a>>32; or a1 = (a << 32) >> 32; a2 = a >> 32;

However, there's a problem with the example code: k*k = 0 (overflow), and the 2nd and 3rd terms: (((a1 * k) % mod) * b2) and (((a2 * k) % mod) * b1) can also overflow (mod could be 2^64-1). It seems that the multiplications are to be implemented similar to how it was done with one of the previously posted answers, but in that case, there's no need to split operands.

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
    uint64_t res = 0;
    uint64_t temp_b;

    if (a >= m)
        a %= m;
    if (b >= m)
        b %= m;
    while (a != 0) {
        if (a & 1) {
            if (b >= m - res) /* Equiv to if (res + b >= m), without overflow */
                res -= m;
            res += b;
        }
        a >>= 1;
        /* Double b, modulo m */
        temp_b = b;
        if (b >= m - b)       /* Equiv to if (2 * b >= m), without overflow */
            temp_b -= m;
        b += temp_b;
    }
    return res;
}

This is a great technique, obviously much better than mine. Thank you very much. — Raman, Aug 03 '15 at 02:59

score 0 · Answer 3 · answered Aug 02 '15 at 17:42

0

Let me explain A*B%k -

    Let us assume A = a1a2a3.......an 
    and           B = b1b2b3.......bn
    where ai & bi are numeric digits

    Then 
A*B%k = A*(b1*(pow(2,n-1))%k + A*(b2*(pow(2,n-2))%k + .......... A*(bn*(pow(2,n-n)%k.
OR 
A*B%k = B*(a1*(pow(2,n-1))%k + B*(a2*(pow(2,n-2))%k + .......... B*(an*(pow(2,n-n)%k.

every term on the right side will not exceed 2^63 before modulo. So doing this is safe and there wont be any overflow

answered Aug 02 '15 at 17:42

Jitendra Singh Rathor

333
4
13

If ai & bi are decimal digits then it should be `pow(10,n-1)`. And If ai & bi are binary digits, then It is ok but it is unnecessary. You can do it with decimal digits. I already know of these approaches. My question is a different approach to the same problem and I want help with that approach only and not a different technique. – Raman Aug 02 '15 at 18:05

score 0 · Answer 4 · answered Aug 03 '15 at 07:34

Let ah = a >> 1, and al = a & 1, then a = (ah << 1) + al = 2*ah + al, and a*b = 2*ah*b + al*b = ah*b + ah*b + al*b.

So we can calculate a*b % mod recursively with each subsequent a shifted right by one, until a is zero:

ull mulMod(ull a, ull b, ull mod) { // assuming a < mod and b < mod
   if (a == 0)
       return 0;

   ull ah = a >> 1;
   ull al = a & 1;

   ull ahb = mulMod(ah, b, mod);

   ull ahb2 = ahb < mod - ahb ? ahb + ahb : ahb - (mod - ahb);

   ull alb = al * b;

   return alb < mod - ahb2 ? ahb2 + alb : ahb2 - (mod - alb);
}

Here we only need to take care of addition modulus mod. And we can avoid overflow if we note that (x + y) % mod is just x + y when x < mod - y, and x - (mod - y) otherwise.

(a*b)%m splitting the operands

4 Answers4