大整数乘法的实现 学号：E30714041 成绩： 姓名：张龙涛 专业：07 级网络 1 班 目的：在计算机语言中，整数最大可以设置为 unsigned long 类型的，但是表示 有限，当涉及到两个大整数相乘的时候，会出现不能表示的情况，鉴于此编制此 算法予以解决大整数相乘。 算法实现思想：本程序使用分治法实现，将 n 位二进制整数 X 和 Y 都分为 2 段， 每段的长为 n/2 位。对输入的数转化为 8 的倍数，使用分治法转化为 1 位，然后 递归调用计算。  XY AC A B D C )( AC BD  BD )2 )  n /2  n 2  ((   算法源程序如下： //张龙涛于 2010 年 5 月 8 日晚完成，此程序实现了大整数相加和相乘 //但由于时间原因并未完成大整数相减的功能，所以并未实现时间 //复杂度为 O(n^1.59).但程序后留有大整数相减的方法，留由以后 //有时间进行推展。 //该程序处理 10 进制数。 #include #include #include using namespace std; string compute(string str1,string str2);//计算大整数相乘。 string move(string str1,int n);//对大整数进行移位 string bigplus(string str1,string str2);//完成大整数相加的功能。 void input(string a,string b)//对刚输入的大整数进行初始处理 { string str1,str2,str3,str4,total; int length1=a.length(); int length2=b.length(); while(length1 % 8!=0)//把 a,b 两个数都改成 8 的倍数，以方便后面对其切割。 { a="0"+a; length1=a.length(); } while(length2 % 8!=0) { b="0"+b; length2=b.length(); } //下面完成使两个大整数位数相同。 if(length1>length2) { while(length1>length2) { b="0"+b; length2=b.length(); } 

} if(length1length1) { a="0"+a; length1=a.length(); } } string ad=compute(a,b);//对其进行乘法运算 while(ad.substr(0,1)=="0")//把返回来的字符串前面的 0 去掉 { ad=ad.substr(1,ad.length()-1); if(ad.length()==1) break; } cout<

string rs=bigplus(bigplus(move(compute(str1,str3),length1),move( bigplus(compute(str1,str4),compute(str2,str3)),length1/2)),compute(str2,str4)); result=rs; return result; } string move(string str1,int n)//移位，十进制移位。 { for(int i=0;istr2.length()) maxlength=str1.length(); else maxlength=str2.length(); int length=maxlength+1;//存储数组长度 int * s=new int[length]; for(int n=0;n=10) { s[length-2]=s[length-2]+1; s[length-1]=s[length-1]-10; } if(i>0) i--; if(j>0) j--; length--; } char array[10]; //对数组进行组合成 string，然后返回。 if(s[0]==0)//去掉前面的 0 for(int i=1;i

else for(int i=0;i>c1>>c2; input(c1,c2); return 1; } 运行结果：