On computing (a*b)%c when a,b,c are of the order of (x) e+18 in c

Question

I found these two codes to compute (a*b)%c when a, b, c is of the order of 10^18 , but could not get how they work can anyone explain me how these functions works line by line

long long int mult(long long int x, long long int y, long long int mod)
{
    x = x % mod;
    y = y % mod;
    long long int z = 0;
    for (1; x; x >>= 1){
            if(x & 1)
            if((z =z+ y) >= mod)
               z = z- mod;
            if((y = 2 * y) >= mod)
           y =y- mod;
     }
     return z;
}

and

long long multiple(long long a, long long b, long long c) // a * b % c
{
        if (b == 0) 
           return 0;

        long long ret = multiple(a, b >> 1, c);
        ret = (ret + ret) % c;
        if (b & 1) 
             ret = (ret + a) % c;
        return ret;
}

i have used these functions in solving online competitions and i have seen that the first function is way better/faster than the latter but why?

Answer 1

The bit-shifts are converting a multiplication operation into (conditional) addition. Each time around the loop (1st method) or recursive call (2nd method) the code looks at the least-significant bit of one of the operands: if it is set, it adds the other operand to the running total. It then shifts the first operand to the right (divides by two) and doubles the other operand (using modulus or subtraction if necessary).

For example, if the numbers were 5 and 7, 5 == 101 in binary so:

x      y      z
--     ---    ---
101    7      7   (bottom bit set, add 7 to z)
10     14         ( x = x >> 1 ; y = y * 2 )
10     14     7   (bottom bit not set, don't add)
1      28     7   ( x = x >> 1 ; y = y * 2 )
1      28     35  (bottom bit set, add 28 to z)
0                 ( x = x >> 1 ; x is zero so stop)