如何避免模数乘法溢出？

本文概述

• C ++
• Java
• Python3
• C#

考虑以下简单两个数相乘的方法。

// 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;
}

当乘法不会导致溢出时, 上述功能可以正常工作。但是, 如果输入数字的乘积结果大于最大限制。

例如, 当mod = 10时, 上述方法将失败11, a = 9223372036854775807(最大long long int)和b = 9223372036854775807(最大long long int)。请注意, 可能会有较小的值可能会失败。可以有更多的较小值的示例。实际上, 任何与之相乘可以导致大于最大值的值的集合。

如何避免溢出？

我们可以递归乘法来克服溢出的困难。要乘以a * b, 请先计算a * b / 2, 然后再相加两次。为了计算a * b / 2, 请计算a * b / 4, 依此类推(类似于

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

下面是实现。

C ++

// 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

// 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

# 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#

// 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

输出如下：

84232501249

感谢Utkarsh Trivedi提出上述解决方案。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。