成百上千位的大数相乘算法(Java&C++)

发布于 2020-05-12  971 次阅读


关于大数,比如java中的BigInteger类型数据可以存放任意大小的数并进行乘法运算,大至两个位数成百上千的数字相乘也没有问题,这是怎么做到的呢?

我们可以按位乘并进位,先来研究普通乘法的运算规则,比如我们计算26x68:

image.png

image.png

image.png

可以看作每一位上运算出来以后超过十的部分向前加,根据这种思路,就可以给出大数相乘不受数据类型限制的算法,这里先给出java代码:

package trying;
import java.util.*;
public class Trying {
public static void main(String[] args) {
int time=0,trigger=0;
@SuppressWarnings("resource")
Scanner in = new Scanner(System.in);
char[]ch1=new char[1000];
char[]ch2=new char[1000];
        String st1 = in.nextLine();
        String st2 = in.nextLine();
        int n=st1.length();
        int m=st2.length();
        ch1 = st1.toCharArray();
        ch2 = st2.toCharArray();
        int []result=new int[2000];
        for(int i=0;i<2000;i++)
            result[i]=0;
        for(int i=n-1;i>=0;i--)
            for(int j=m-1;j>=0;j--)
                result[m+n-2-i-j]+=(ch1[i]-48)*(ch2[j]-48);
        //ascii转换后按位乘
        while(time!=n+m){
             for(int i=0;i9) {result[i+1]+=result[i]/10;result[i]%=10;}}
             time++;}
             //进位操作
             for(int i=n+m;i>=0;i--){
                 if(result[i]>0)trigger=1;
                 if(trigger==0&&result[i]==0)continue;
                 System.out.print(result[i]);}}}
                 //去除前置0

运行结果:

image.png

当然因为java本来就有BigInteger类型,此种算法在java内用处不大,因此再给出c++代码

#include
#include
#include
int n,m,time,trigger,i,j;
void main(){
char ch1[1000],ch2[1000];
 printf("请输入两数\n");
scanf("%s%s",ch1,ch2);
n=strlen(ch1),m=strlen(ch2);
long result[2000];
 for(i=0;i<2000;i++)
 result[i]=0;
 //初始化结果数组
  for(i=n-1;i>=0;i--)
  for(j=m-1;j>=0;j--)
  result[n+m-2-j-i]+=(ch1[i]-48)*(ch2[j]-48);
  //ascii转换后按位乘
 while(time!=n+m){
 for(i=0;i9)result[i+1]+=result[i]/10,result[i]%=10;}
 time++;}
 //进位操作
 for(i=n+m;i>=0;i--){
 if(result[i]>0)trigger=1;
 if(trigger==0&&result[i]==0)continue;
 printf("%ld",result[i]);}}
 //去除前置0

运行结果:image.png

因此在没有大数类型的语言中对于超过最大数据类型最大值的数字乘法,可以利用这种算法计算。当然java中BigInteger的运算跟二进制和补码等有关系,CSDN上有很详细的文章说明,就不在这里阐述。


华科菜鸡计科学生