大整数乘法

 

        在计算机中，长整型(long int)变量的范围是 -2147483648 至 2147483647，因此若用长整型变量做乘法运算，乘积最多不能超过 10位数。即便用双精度型(double)变量，也仅能保证 16 位有效数字的精度。在某些需要更高精度的乘法运算的场合，需要用别的办法来实现乘法运算。 
        比较容易想到的是做多位数乘法时列竖式进行计算的方法，只要写出模拟这一过程的程序，就能实现任意大整数的乘法运算。经过查阅资料，找到一种更易于编程的方法，即“列表法”。 

下面先介绍“列表法”： 
      例如当计算8765 x 234时，把乘数与被乘数照如下列出，见表1：                         

 

                        
      把表1中的数按图示斜线分组（横纵坐标和相等的数分为一组），把每组数的累加起来所得的和记在表格下方，见表 2：

        从最低位的 20 开始，保留个位数字“0”，把个位以外的数“2”进到前一位；把次低位的 39 加上低位进上来的 2 得 41，保留个位数字“1”，把“4”进到前一位；以此类推，直至最高位的 16，16 加上低位进上来的4得 20，保留“0”，把2进到最高位，得乘积答数 2051010。                      

根据以上思路就可以编写C 程序了，再经分析可得： 
1、一个m 位的整数与一个 n 位的整数相乘，乘积为m+n-1 位或m+n 位。 
2、程序中，用三个字符数组分别存储乘数、被乘数与乘积。由第 1 点分析知，存放乘积的字符数组
的长度应不小于存放乘数与被乘数的两个数组的长度之和。 

 

#include "StdAfx.h"
#include "subStr.h"
#include<iostream>
using namespace std;

#define MAX_LENTH 201


void mul(int lenA,int lenB,int *bigNumA,int *bigNumB,int *resultNum){

		int i,j,index,mid;
		for(i=0;i<lenA;i++){
			index=i;
			for(j=0;j<lenB;j++){
				resultNum[index++]+=bigNumA[i]*bigNumB[j];
			}
		}
		//以下为处理和值进位
		for(i=0;i<=index;i++){
			if(resultNum[i]>=10){
				mid=resultNum[i]/10;
				resultNum[i+1]+=mid;
				resultNum[i]%=10;
			}
		}
		//以下为输出
		if(resultNum[index]!=0){
			printf("%d",resultNum[index]);
		}
		for(i=index-1;i>=0;i--){
			printf("%d",resultNum[i]);
		}
		printf("\n");
}
int main(){
	char numA[MAX_LENTH],numB[MAX_LENTH];
	int bigNumA[MAX_LENTH],bigNumB[MAX_LENTH],resultNum[MAX_LENTH*2];
	int i,pos,len;
	while(scanf("%s %s",numA,numB)!=EOF){

		//注意两点，memset第三个参数是字节数，不能用strlen(bigNumA)。例如：
		//memset(bigNumA,0,strlen(bigNumA))是错误的。
		//bigNumA[MAX_LENTH]={0}这种将数组元素统一置为0的方式只有在声明的时候才能使用。
		//以下的“//”解开后是会出错的。
		memset(bigNumA,0,sizeof(bigNumA));
		memset(bigNumB,0,sizeof(bigNumB));
		memset(resultNum,0,sizeof(resultNum));
		//bigNumA[MAX_LENTH]={0};
		//bigNumB[MAX_LENTH]={0};

		//以下是将接收到的大整数numA和numB存储到bigNumA和bigNumB中，个位对应bigNumx[0],以此类推。

		pos=0;
		for(i=strlen(numA)-1;i>=0;i--){
			bigNumA[pos++]=numA[i]-'0';
		}
		pos=0;
		for(i=strlen(numB)-1;i>=0;i--){
			bigNumB[pos++]=numB[i]-'0';
		}

		if(strlen(numA)>strlen(numB))
		{
			len=strlen(numA);
		}else{
			len=strlen(numB);
		}
		mul(strlen(numA),strlen(numB),bigNumA,bigNumB,resultNum);
	}
	system("pause");
	return 0;
}