Multiplica números enteros grandes por debajo de módulo grande

Dado un número entero a, b, m. Encuentre (a * b ) mod m, donde a, b pueden ser grandes y su multiplicación directa puede causar desbordamiento. Sin embargo, son más pequeños que la mitad del valor de int largo largo máximo permitido.

Ejemplos: 

Input: a = 426, b = 964, m = 235
Output: 119
Explanation: (426 * 964) % 235  
            = 410664 % 235
            = 119

Input: a = 10123465234878998, 
       b = 65746311545646431
       m = 10005412336548794 
Output: 4652135769797794

Un enfoque ingenuo es utilizar un tipo de datos de precisión arbitraria, como int en python o la clase Biginteger en Java. Pero ese enfoque no será fructífero porque la conversión interna de string a int y luego realizar la operación conducirá a ralentizar los cálculos de suma y multiplicación en el sistema numérico binario.

Solución eficiente: dado que a y b pueden ser números muy grandes, si tratamos de multiplicar directamente, definitivamente se desbordará. Por lo tanto, usamos el enfoque básico de la multiplicación, es decir,
a * b = a + a + … + a (b veces) 
Así que podemos calcular fácilmente el valor de la suma (bajo el módulo m) sin ningún 
desbordamiento en el cálculo. Pero si tratamos de sumar el valor de a repetidamente hasta b veces, definitivamente se agotará el tiempo de espera para el gran valor de b, ya que la complejidad temporal de este enfoque se convertiría en O(b).

Entonces dividimos los pasos repetidos anteriores de a de una manera más simple, es decir, 

If b is even then 
  a * b = 2 * a * (b / 2), 
otherwise 
  a * b = a + a * (b - 1)

A continuación se muestra el enfoque que describe la explicación anterior: 

// C++ program of finding modulo multiplication
#include <bits/stdc++.h>
 
using namespace std;
 
// Returns (a * b) % mod
long long moduloMultiplication(long long a, long long b,
                               long long mod)
{
    long long res = 0; // Initialize result
 
    // Update a if it is more than
    // or equal to mod
    a %= mod;
 
    while (b) {
        // If b is odd, add a with result
        if (b & 1)
            res = (res + a) % mod;
 
        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;
 
        b >>= 1; // b = b / 2
    }
 
    return res;
}
 
// Driver program
int main()
{
    long long a = 426;
    long long b = 964;
    long long m = 235;
    cout << moduloMultiplication(a, b, m);
    return 0;
}
 
// This code is contributed
// by Akanksha Rai

// C program of finding modulo multiplication
#include<stdio.h>
 
// Returns (a * b) % mod
long long moduloMultiplication(long long a,
                               long long b,
                               long long mod)
{
    long long res = 0;  // Initialize result
 
    // Update a if it is more than
    // or equal to mod
    a %= mod;
 
    while (b)
    {
        // If b is odd, add a with result
        if (b & 1)
            res = (res + a) % mod;
 
        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;
 
        b >>= 1;  // b = b / 2
    }
 
    return res;
}
 
// Driver program
int main()
{
    long long a = 10123465234878998;
    long long b = 65746311545646431;
    long long m = 10005412336548794;
    printf("%lld", moduloMultiplication(a, b, m));
    return 0;
}

// Java program of finding modulo multiplication
class GFG
{
 
    // Returns (a * b) % mod
    static long moduloMultiplication(long a,
                            long b, long mod)
    {
         
        // Initialize result
        long res = 0; 
 
        // Update a if it is more than
        // or equal to mod
        a %= mod;
 
        while (b > 0)
        {
             
            // If b is odd, add a with result
            if ((b & 1) > 0)
            {
                res = (res + a) % mod;
            }
 
            // Here we assume that doing 2*a
            // doesn't cause overflow
            a = (2 * a) % mod;
 
            b >>= 1; // b = b / 2
        }
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        long a = 10123465234878998L;
        long b = 65746311545646431L;
        long m = 10005412336548794L;
        System.out.print(moduloMultiplication(a, b, m));
    }
}
 
// This code is contributed by Rajput-JI

# Python 3 program of finding
# modulo multiplication
 
# Returns (a * b) % mod
def moduloMultiplication(a, b, mod):
 
    res = 0; # Initialize result
 
    # Update a if it is more than
    # or equal to mod
    a = a % mod;
 
    while (b):
     
        # If b is odd, add a with result
        if (b & 1):
            res = (res + a) % mod;
             
        # Here we assume that doing 2*a
        # doesn't cause overflow
        a = (2 * a) % mod;
 
        b >>= 1; # b = b / 2
     
    return res;
 
# Driver Code
a = 10123465234878998;
b = 65746311545646431;
m = 10005412336548794;
print(moduloMultiplication(a, b, m));
     
# This code is contributed
# by Shivi_Aggarwal

// C# program of finding modulo multiplication
using System;
 
class GFG
{
     
// Returns (a * b) % mod
static long moduloMultiplication(long a,
                            long b,
                            long mod)
{
    long res = 0; // Initialize result
 
    // Update a if it is more than
    // or equal to mod
    a %= mod;
 
    while (b > 0)
    {
        // If b is odd, add a with result
        if ((b & 1) > 0)
            res = (res + a) % mod;
 
        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;
 
        b >>= 1; // b = b / 2
    }
 
    return res;
}
 
// Driver code
static void Main()
{
    long a = 10123465234878998;
    long b = 65746311545646431;
    long m = 10005412336548794;
    Console.WriteLine(moduloMultiplication(a, b, m));
}
}
 
// This code is contributed
// by chandan_jnu

<?php
//PHP program of finding
// modulo multiplication
 
// Returns (a * b) % mod
function moduloMultiplication($a, $b, $mod)
{
    $res = 0; // Initialize result
 
    // Update a if it is more than
    // or equal to mod
    $a %= $mod;
 
    while ($b)
    {
         
        // If b is odd,
        // add a with result
        if ($b & 1)
            $res = ($res + $a) % $mod;
 
        // Here we assume that doing 2*a
        // doesn't cause overflow
        $a = (2 * $a) % $mod;
 
        $b >>= 1; // b = b / 2
    }
 
    return $res;
}
 
    // Driver Code
    $a = 10123465234878998;
    $b = 65746311545646431;
    $m = 10005412336548794;
    echo moduloMultiplication($a, $b, $m);
 
// This oce is contributed by ajit
?>

<script>
 
// JavaScript program for the above approach
 
// Returns (a * b) % mod
function moduloMultiplication(a, b, mod)
{
     
    // Initialize result
    let res = 0; 
 
    // Update a if it is more than
    // or equal to mod
    a = (a % mod);
 
    while (b > 0)
    {
         
        // If b is odd, add a with result
        if ((b & 1) > 0)
        {
            res = (res + a) % mod;
        }
 
        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;
 
        b = (b >> 1); // b = b / 2
    }
    return res;
}
 
// Driver Code
let a = 426;
let b = 964;
let m = 235;
 
document.write(moduloMultiplication(a, b, m));
 
// This code is contributed by code_hunt
 
</script>

119

Complejidad temporal: O(log b) 
Espacio auxiliar: O(1)

Nota: el enfoque anterior solo funcionará si 2 * m se pueden representar en el tipo de datos estándar; de lo contrario, se producirá un desbordamiento. 

Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.