c - 如何避免模乘中的溢出？

Question

我知道，

(a*b)%m = ((a%m)*(b%m))%m

但是有溢出的可能。为简单起见，我们假设整数的大小为 2 位。如果 a = 2（即 10 ₂）和 b = 2（即 10 ₂），m = 3（即 11 ₂），则 a%m 和 b%m 变为 2，乘法后，答案为 4（即100) 不适合整数大小。如果从 4 考虑 2-lsb，则最终答案将为 0。但实际答案为 1。

我应该怎么做才能避免这种情况？

Answer 1

如果m-1平方不适合您的整数类型，则需要执行长乘法。对于您的两位示例，这意味着将您的两位数字分成一对一位数字（一个高位和一个低位）并将所有四对相乘（高乘以高，高乘低，低乘高，低低）单独。然后，您可以获得m每对的结果 mod（注意它们所代表的实际位置，即四、二或一）并添加结果 mod m。

Answer 2

许多小型处理器 C 实现可以直接检查数学运算的结果是否有上溢/下溢。

另一种方法是使用两倍于底层 int 大小 IE 长度的接收字段，用于 int 大小为 2，使用 4 字节的结果字段。（可能通过 long long int）或将两个数字传输到双字段并将它们相乘然后转换回 int（但是，结果中的某些精度（即最低有效位）可能不准确。

另一种方法是使用 math.h 库中的适当函数。

另一种方法是使用数组使用长乘法：这是从http://www.cquestions.com/2010/08/multiplication-of-large-numbers-in-c.html复制的

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10000

char * multiply(char [],char[]);
int main(){
    char a[MAX];
    char b[MAX];
    char *c;
    int la,lb;
    int i;
    printf("Enter the first number : ");
    scanf("%s",a);
    printf("Enter the second number : ");
    scanf("%s",b);
    printf("Multiplication of two numbers : ");
    c = multiply(a,b);
    printf("%s",c);
    return 0;
}

char * multiply(char a[],char b[]){
    static char mul[MAX];
    char c[MAX];
    char temp[MAX];
    int la,lb;
    int i,j,k=0,x=0,y;
    long int r=0;
    long sum = 0;
    la=strlen(a)-1;
    lb=strlen(b)-1;

    for(i=0;i<=la;i++){
            a[i] = a[i] - 48;
    }

    for(i=0;i<=lb;i++){
            b[i] = b[i] - 48;
    }

    for(i=lb;i>=0;i--){
        r=0;
        for(j=la;j>=0;j--){
            temp[k++] = (b[i]*a[j] + r)%10;
            r = (b[i]*a[j]+r)/10;
        }
        temp[k++] = r;
        x++;
        for(y = 0;y<x;y++){
            temp[k++] = 0;
        }
   }

   k=0;
   r=0;
   for(i=0;i<la+lb+2;i++){
        sum =0;
        y=0;
        for(j=1;j<=lb+1;j++){
            if(i <= la+j){
                sum = sum + temp[y+i];
            }
            y += j + la + 1;
        }
        c[k++] = (sum+r) %10;
        r = (sum+r)/10;
   }
   c[k] = r;
   j=0;
   for(i=k-1;i>=0;i--){
      mul[j++]=c[i] + 48;
   }
   mul[j]='\0';
   return mul;

}

上述代码的示例输出：

输入第一个数字：55555555

输入第二个号码：3333333333

两个数相乘：

185185183314814815

大数乘法的逻辑

正如我们在 c 中所知道的，没有任何这样的数据类型可以存储非常大的数字。例如我们要求解表达式：

55555555 * 3333333333

上述表达式的结果是一个非常大的数字，超出了甚至 long int 或 long double 的范围。那么问题是如何在c中存储这么大的数字？

解决方案非常简单，即使用数组。上面的程序使用了相同的逻辑，即我们使用通常的逻辑来将两个数字相乘，除了将数据存储在我们存储到数组中的普通变量中。