¿Cómo evitar el desbordamiento en la multiplicación modular?

Considere el siguiente método simple para multiplicar dos números.
 

// A Simple solution that causes overflow when
// value of (a % mod) * (b % mod) becomes more than
// maximum value of long long int
#define ll long long
 
ll multiply(ll a, ll b, ll mod)
{
   return ((a % mod) * (b % mod)) % mod;
}

// A Simple solution that causes overflow when
// value of (a % mod) * (b % mod) becomes more than
// maximum value of long int
 
 
static long multiply(long a, long b, long mod)
{
   return ((a % mod) * (b % mod)) % mod;
}
 
// This code contributed by gauravrajput1

# A python program to handle overflow
# when multiplying two numbers      
 
def multiply(a,b,mod):
    return ((a % mod) * (b % mod)) % mod;
 
# Code contributed by Gautam goel (gautamgoel962)

// C# program to implement
// the above approach
using System;
 
class GFG{
     
 
// A Simple solution that causes overflow when
// value of (a % mod) * (b % mod) becomes more than
// maximum value of long int
static long multiply(long a, long b, long mod)
{
   return ((a % mod) * (b % mod)) % mod;
}
}
 
// This code is contributed by code_hunt.

<script>
 
function multiply(a,b,mod)
{
    return ((a % mod) * (b % mod)) % mod;
}
 
 
// This code is contributed by rag2127
</script>

La función anterior funciona bien cuando la multiplicación no da como resultado un desbordamiento. Pero si los números de entrada son tales que el resultado de la multiplicación es más que el límite máximo.
Por ejemplo, el método anterior falla cuando mod = 10 ¹¹ , a = 9223372036854775807 ( mayor largo int largo ) y b = 9223372036854775807 ( mayor largo largo int ). Tenga en cuenta que puede haber valores más pequeños para los que puede fallar. Puede haber muchos más ejemplos de valores más pequeños. De hecho, cualquier conjunto de valores para los que la multiplicación puede dar como resultado un valor superior al límite máximo.
¿Cómo evitar el desbordamiento? 
Podemos multiplicar recursivamente para superar la dificultad del desbordamiento. Para multiplicar a*b, primero calcula a*b/2 y luego súmalo dos veces. Para calcular a*b/2 calcule a*b/4 y así sucesivamente (similar al algoritmo de exponenciación log n ). 
 

// To compute (a * b) % mod
multiply(a,  b, mod)
1)  ll res = 0; // Initialize result
2)  a = a % mod.
3)  While (b > 0)
        a) If b is odd, then add 'a' to result.
               res = (res + a) % mod
        b) Multiply 'a' with 2
           a = (a * 2) % mod
        c) Divide 'b' by 2
           b = b/2  
4)  Return res 

A continuación se muestra la implementación. 
 

// C++ program for modular multiplication without
// any overflow
#include<iostream>
using namespace std;
 
typedef long long int ll;
 
// To compute (a * b) % mod
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;
}
 
// Driver program
int main()
{
   ll a = 9223372036854775807, b = 9223372036854775807;
   cout << mulmod(a, b, 100000000000);
   return 0;
}

// Java program for modular multiplication 
// without any overflow
 
class GFG
{
 
    // To compute (a * b) % mod
    static long mulmod(long a, long b,
                            long mod)
    {
        long 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;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        long a = 9223372036854775807L, b = 9223372036854775807L;
        System.out.println(mulmod(a, b, 100000000000L));
    }
}
 
// This code is contributed by Rajput-JI

# Python3 program for modular multiplication
# without any overflow
 
# To compute (a * b) % mod
def mulmod(a, b, mod):
 
    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;
 
# Driver Code
a = 9223372036854775807;
b = 9223372036854775807;
print(mulmod(a, b, 100000000000));
 
# This code is contributed by mits

// C# program for modular multiplication
// without any overflow
using System;
 
class GFG
{
 
// To compute (a * b) % mod
static long mulmod(long a, long b, long mod)
{
    long 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;
}
 
// Driver code
public static void Main(String[] args)
{
    long a = 9223372036854775807L,
         b = 9223372036854775807L;
    Console.WriteLine(mulmod(a, b, 100000000000L));
}
}
 
// This code is contributed by 29AjayKumar

<script>
// JavaScript program for modular multiplication
// without any overflow
 
// To compute (a * b) % mod
function mulmod(a, b, mod){
    let 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;
}
 
 
// Driver Code
let a = 9223372036854775807;
let b = 9223372036854775807;
document.write(mulmod(a, b, 100000000000));
 
// This code is contributed by Gautam goel (gautamgoel962)
</script>

Producción: 

84232501249

Gracias a Utkarsh Trivedi por sugerir la solución anterior.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.