large_integer_multiplication.cpp

算法分析与设计——大整数乘法。 计算两个超出机器数表示范围的整数的乘积。

#include<iostream>
#include<string.h>
using namespace std;

void main()
{
	char num1[32],num2[32];//存储大整数数组

	int digit1[16]={0};
	int digit2[16]={0};
	int e[64]={0};
	int f[64]={0};
	int j;

	//以字符流形式输入两个大整数,并存放在num1,num2中
	cout<<"请输入第一个大整数：";
	cin>>num1;
	int len1=strlen(num1);//字符流长度
	cout<<"请输入第二个大整数：";
	cin>>num2;
	int len2=strlen(num2);

	int p=len1/2;
	if(len1%2!=0) p++;

	for(int i=0;i<p;i++)
	{
		 digit1[p-i-1]=(int)num1[len1-i*2-1]-48+(num1[len1-i*2-2]-48)*10;//每二位一存，作为新的数
	}

	if(len1%2==1) 
		digit1[0]=(int)num1[0]-48;//数组最高位分别讨论情况

	int q=len2/2;
	if(len2%2!=0)
		q=q+1;
	for(i=0;i<q;i++)
	{
		 digit2[q-i-1]=(int)num2[len2-i*2-1]-48+(num2[len2-i*2-2]-48)*10;
	}
		if(len2%2==1) 
			digit2[0]=(int)num2[0]-48;//数组最高位分别讨论情况

		int r[64];
		int l[64];
		//存放最终结果
		for(i=0;i<64;i++)
		{
			r[i]=0;
			l[i]=0;
		}

		for(i=p-1;i>=0;i--)
			for(j=q-1;j>=0;j--)
			{
				r[i+j]=r[i+j]+digit1[i]*digit2[j];
			}
		l[p+q-1]=r[p+q-1]%100;
		for(i=p+q-2;i>0;i--)
			{
				l[i]=r[i]%100+r[i+1]/100;
			}
		l[0]=r[0]+r[1]/100;
		for(i=0;i<p+q-1;i++)
			cout<<l[i];
		cout<<endl;

}