0


大整数乘法的详解

一.问题

由于编程语言提供的基本数值数据类型表示的数值范围有限,不能满足较大规模的高精度数值计算,因此需要利用其他方法实现高精度数值的计算,于是产生了大数运算。尤其是乘法运算,下面就是大整数的乘法的过程(加 减法都一样的原理)。

二.解决问题的方法

方法一(传统的相乘逐步相加)

乘法规律,一个数的第i位和另一个数的第j位相乘,一定会累加到结果的第i+j位,结果的数组一个数组元素存2位数,最后对结果整除得到进位,mod得到余数就是i+j位的数字,最后打印出来。

** 对于大整数比较方便的输入方法*是,①按字符型处理,存储在字符串数组s1、s2中,计算结果存储在整型数组ans中。 ②通过字符的ASCII码,数字字符可以直接参与运算,i位数字与j位数字相乘的表达式为:(s1[i]-‘0’)(s2[j]-‘0’)。 ③每一次数字相乘的结果位数是不固定的,而结果数组中每个元素只存储一位数字,所以用变量t暂存结果,对t mod运算得到的就是ans[i+j]的值,若超过1位数则进位,用变量b存储。

这种做法的时间复杂度为o(n^2)

c语言源码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int max(int a,int b){
    return a>b?a:b;
}
 
int main()
 {
  char s1[205], s2[205],ans[1000];
  int str1[205],str2[205];
  int len1, len2,i;
  while( scanf("%s%s", s1, s2)!=EOF){
     len1 = strlen(s1), len2 = strlen(s2);
     memset(str1,0,205);//初始化0
     memset(str2,0,205);
     memset(ans,0,1000);
     int len = 0;
     for(i = 0; i < len1; ++ i)
        str1[i] = s1[len1 - 1 - i] - '0';
     for(i = 0; i < len2; ++ i)
         str2[i] = s2[len2 - 1 - i] - '0';
 
    for( i = 0; i < len1; ++ i)
    {
         int b = 0;   //每遍历完数组a的一个数,进位b都要初始化为0
         for(int j = 0; j < len2 || b; ++ j)//当str[j]没遍历完,或者最高位满十需要进位,进位不为0
         {
             int t = ans[i + j] + str1[i]*str2[j] + b;
             ans[i + j] = t%10;  //余数就是该ans[i+j]位置的数
             b = t/10;//进位
             //len = max(len, j + i);
         }
        len = i+j-1  //最终的位数
     }
     for( i = len; i >= 0; -- i)  //倒置输出
        printf("%d", ans[i]);
     printf("\n");
  }
    return 0;
}

方法二(分治法)

分治算法解题的一般步骤:

  • 分解:将要解决的问题划分为若干个规模较小的同类问题
  • 求解:当子问题划分的足够小时,用较简单的方法解决
  • 合并:按原问题的要求,将子问题的解逐层合并构成原问题的解

①两个大整数在理想状态下:就是两个大整数的位数相同

现在有两个大整数X,Y; 设X, Y是n位十进制整数,分段表示如下:

即 X=A10^(n/2)+B, Y=C10^(n/2)+D 则:

本来可以直接算AD+BC,但是这样效率变低了,所以对AD+BC进行分解优化后得:

计算成本:3次n/2位乘法,6次不超过n位加减法,2次移位,所有加法和移位共计O(n)次运算。由此可得

理想状态下c语言代码:(不超过long long 型,后面做法会用字符串接收大整数

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define sign(x) ((x>0)?1:-1)

//_int64等同于long long 
//%I64d等同于%lld

 _int64 mutipy(_int64 a,_int64 b,int num){  //两个long long 类型的大整数相乘,后面会用字符串做法解决
     int s=sign(a)*sign(b);
     a=(a>0)?a:-a ;
     b=(b>0)?b:-b ;
     if(num==0)  //递归出口,
         return 0;
     else if(num==1){  //当a,b只有一位数时,直接相乘
         return s*a*b;  
     }
     else{

       _int64 A=a/(int)pow(10,(int)(num/2));  //分离大整数a的高位
       _int64 B=a%(int)pow(10,(int)(num/2)); //分离大整数a的低位
       _int64 C=b/(int)pow(10,(int)(num/2));   //分离大整数b的高位
       _int64 D=b%(int)pow(10,(int)(num/2));     //分离大整数b的低位

       _int64 AC=mutipy(A,C,(int)(num/2));  //分治计算AC
       _int64 BD=mutipy(B,D,(int)(num/2));  //分治计算BD
       _int64 ABCD=mutipy((A-B),(D-C),(int)(num/2))+AC+BD;  //计算(A-B)(D-C)+AC+BD
       return s*(_int64)(AC*pow(10,(int)(num/2)+(int)(num/2))+ABCD*pow(10,(int)(num/2))+BD);  //返回结果
     }
} 
int main()
 {
    _int64 a,b,c,temp;  //long long a,b,c;
    int len1=0,len2=0;

    while(scanf("%I64d %I64d",&a,&b)){
        temp=a;
        while(temp){  //计算a的位数
            len1++;
             temp=temp/10;
        }    
       c=mutipy(a,b,len1);
       printf("%I64d\n",c);    
    }
    return 0;
}

其实上述有个缺陷:那就是只能是long long 类型的大整数相乘,超出了long long 型就会报错。解决方法看下面的做法

②两个大整数在非理想状态下:就是两个大整数的位数不相同

我们还是假设有两个大整数X、Y,它们的位数不相同,现在要求X*Y的乘法,我们采用分治的算法,将X、Y分别拆分为A与B、C与D,如下图:

上式一共需要进行2次xn0的乘法(AC、AD各一次)、2次yn0的乘法(AC、BC各一次)和3次加法,因而该算法的时间复杂度为

跟上面一样,对AD+BC进行分解优化得:

修改后的时间复杂度:

由于T(min(m,n))<T(m)+T(n),所以修改后的算法更好,时间复杂度:T(m+n)=O(nlog3)=O(n1.59)

非理想状态下的c语言代码:(不超过long long 型,后面做法会用字符串接收大整数

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define sign(x) ((x>0)?1:-1)
//_int64等同于long long 
//%I64d等同于%lld

 _int64 mutipy(_int64 a,int numa,_int64 b,int numb){ //两个long long 类型的大整数相乘,后面会用字符串做法解决
     int s=sign(a)*sign(b);
     a=(a>0)?a:-a ;
     b=(b>0)?b:-b ;
     if(numa==0||numb==0)  //递归出口,
         return 0;
     else if((numa==1&&numb==1)||numa==1||numb==1){  //当a,b只有一位数时,直接相乘
         return s*a*b;  
     }
     else{
       int num1=numa/2;  //定义了大整数a的低位的位数x0
       int num2=numa-num1;  //定义了大整数a的高位的位数x1
       int num3=numb/2;   //定义了大整数b的低位的位数x2
       int num4=numb-num3; //定义了大整数b的高位的位数x3

       _int64 A=a/(int)pow(10,num1);  //分离大整数a的高位
       _int64 B=a%(int)pow(10,num1); //分离大整数a的低位
       _int64 C=b/(int)pow(10,num3);   //分离大整数b的高位
       _int64 D=b%(int)pow(10,num3);     //分离大整数b的低位

       _int64 AC=mutipy(A,num2,C,num4);  //分治计算AC
       _int64 BD=mutipy(B,num1,D,num3);  //分治计算BD
       _int64 ABCD=mutipy(((_int64)(A*pow(10,num1))-B),num2,(D-(_int64)(C*pow(10,num1))),num4);  //计算(A*10^num1-B)(D-C*10^num3)
       return s*(_int64)(2*AC*pow(10,(num1+num3))+ABCD+2*BD);  //返回结果     
     }
}
int main()
 {
    _int64 a,b,c,temp;  //long long a,b,c;
    int len1=0,len2=0;

    while(scanf("%I64d %I64d",&a,&b)){
        temp=a;
        while(temp){  //计算a的位数
            len1++;
             temp=temp/10;
        }
        temp=b;
        while(temp){      //计算b的位数
            len2++;
             temp=temp/10;
        }    
       c=mutipy(a,len1,b,len2);
       printf("%I64d\n",c);    
    }  
    return 0;
}

非理想状态下的c语言代码:(任意位数相乘,可以超出longlong类型)

#include<stdio.h>
#include<string.h>
int result[255];

 void cal( char a[],int numa,char b[],int numb,int s){
   int num1=numa/2;     //num1为B的位数,B属于低位的那一部分
   int num2=numa-num1;  //num2为A的位数,A属于高位的那一部分
   int num3=numb/2;    //num3为D的位数,D属于低位的那一部分
   int num4=numb-num3;  //num4为C的位数,C属于高位的那一部分
   char A[255],B[255],C[255],D[255];
   int k=0;
   if(numa==0||numb==0)  //当位数为0时
        return ;
   else if(numa==1&&numb==1){  //分治递归到当数组a和b的位数全为1时
         result[s]+=(a[0]-'0')*(b[0]-'0');  //直接计算,把他的结果直接加到对应数组result的位置
         return;
         }
   else{  //当数组a和b的位数至少有一个不为1时
       
       for(int i=0;i<num2;i++) //获取数组a的高位部分A
           A[k++]=a[i];
       k=0;
       for(i=num2;i<numa;i++)  //获取数组a的低位部分B
           B[k++]=a[i];
       k=0;
       for(i=0;i<num4;i++)  //获取数组b的高位部分C
           C[k++]=b[i];
       k=0;
       for(i=num4;i<numb;i++)  //获取数组b的高位部分D
           D[k++]=b[i];

       cal(A,num2,C,num4,s+num1+num3);  //AC ,在result[s+num1+num3]的位置存储AC,也是说偏移s+num1+num3位,s初始化为0
       cal(B,num1,C,num4,num3+s);  //BC,偏移num3+s位
       cal(A,num2,D,num3,num1+s);  //AD,偏移num1+s位
       cal(B,num1,D,num3,s);  //BD,偏移s位
   }
 }
 void exchange(int result[],int len){ //将result数组中的值进行整理,转化输出
    int i = 0;
    int t,p1,p2;
    while(i<=len){    //以特殊数最大位数为终止条件 
        if(result[i] < 10);      //当result[i]的值小于10,就不处理,直接保存在result[i]中
        else if(result[i] < 100){  //当0<=result[i]<100时
            t = result[i] % 10;  //余数就是该位置result[i]的值
            p1 = result[i] / 10;  //result[i]进位
            result[i] = t;       //将余数t保存至result[i]中
            result[i+1] += p1;   //进位把他加到result[i+1]中    
        }
        else{   //当result[i]>=100时
            t = result[i] % 10;     //余数就是该位置result[i]的值
            p1 = result[i] / 10 % 10;  //这是result[i]满十进位
            p2 = result[i] / 100;       //这是result[i+1]满十进位 
            result[i] = t;         //将余数t保存至result[i]中
            result[i+1] += p1;     //进位把他加到result[i+1]中
            result[i+2] += p2;     //进位把他加到result[i+2]中
        }
        i++;  //位数加1
    } 
}

 int main(){
   char a[100],b[100];
   int j,i=0,len1,len2;
  while(scanf("%s %s",a,b)!=EOF){
   len1=strlen(a);
   len2=strlen(b);
   cal(a,len1,b,len2,0);  
   exchange(result,len1+len2); 

   for(i=len1+len2-1;i>=0;){  //去高位的0去掉
       if(result[i]==0){  
         while(result[i]==0){
           i--;
         }
       }
       else
           break;
   }

   for(j=i;j>=0;j--) //从非零的位置打印
         printf("%d",result[j]);         
   printf("\n");
  }
   return 0;
 }

本文转载自: https://blog.csdn.net/hgnuxc_1993/article/details/110297000
版权归原作者 无尽的沉默 所有, 如有侵权,请联系我们删除。

“大整数乘法的详解”的评论:

还没有评论