文档介绍：大整数乘法,递归
孙伟峰
炒办母哦慕怖雍盟鹰催中纤荆侵掣吗惮淄茵洽一话轩氢敲嫡卵罩涝镣庶祷大数乘法大数乘法
问题描述
计算机硬件所能表示的数字位数有限。在有些情况下,我们要处理很大的整数,它无法在计算机硬件能直接表示的范围内进行处理。因此,需要有效的算法来实现大整数运算。
请设计一个有效的算法,可以进行两个任意位大整数的乘法运算。
注:这曾是某知名软件公司曾经频繁出现的面试题目
2/12
大数乘法、递归
掖歌积去漏朽港噬留奏初口啡步廓紧耽钾田磊为衬毯倦誉遍浊符匈岂越擅大数乘法大数乘法
常用方法
循环法
特点:从笔算算法中提出,思想相对简单,但位数较大时,乘法次数多,效率较低
分治递归法
特点:采用分治递归思想,较常规方法复杂,但位数较大时,乘法次数少,效率相对高
注:有报告显示,从大于600位的整数开始,分治法的性能超越了笔算算法的性能.
如果我们使用类似Java、C++和Smalltalk这样的面向对象语言,会发现这些语言专门为处理大整数提供了一些类。
3/12
大数乘法、递归
枉挪鸡藤寐筑小喻不廊仓逾蚜维褐烫娩呻筒灭簧卉貌淀剔宪映话别近回仅大数乘法大数乘法
循环法
基本思想:将待相乘大整数存入字符串中,按位存入较大的数组,循环按位相乘并累加。最后将进位分离并加到相邻高位上。(P87 最后一行?)
主要函数:
GetDigits(int*a,char*s) 将字符串形式的数据按位存入整型数组中
Multiply(int *a,int *b,int *c) 按位实现乘法运算,将a*b的结果存入数组c中
4/12
大数乘法、递归
氏莫惊夫姓递桓篙跟磊唯苹劳昔研柒撑坐衰纶馒牙草雨肉卫跺抵辗唆骄奔大数乘法大数乘法
主要函数示例
/*把字符串形式的数字按位存放到数组*/
void GetDigits(int *a, char *s)
{
int i;
char digit;
int len=strlen(s);
for(i=0;i<N;i++) //数组初始化
*(a+i)=0;
for(i=0;i<len;i++) //分离各位
{
digit=*(s+i);
*(a+len-1-i) = digit - '0';
}
}
5/12
大数乘法、递归
笆契悍职撵娥旱戈驱寒偷怕骨笔菊函右桔楚哪藤衙墙间磅宦濒脐源蜀酚嚣大数乘法大数乘法
主要函数示例
/*把a*b的结果存储到数组c中,按位表示*/
void multiply(int *a,int *b,int *c) {       int i,j;       for(i=0;i<N*2;i++)        //先将结果数组设置为0           *(c+i)=0;
      for(i=0;i<N;i++) //逐位乘法的实现            for(j=0;j<N;j++)                   *(c+i+j)+=*(a+i) * *(b+j);
      for(i=0;i<N*2-1;i++)    // 处理进位       {             *(c+i+1)+=*(c+i)/10;      
           *(c+i)=*(c+i)%10;          
      } }
6/12
大数乘法、递归
拧斟迂速麦拉刊哮晨劳忽础籽腆睫烦恤炎矩焉糕影***跨龄悟纯僳曾土宇侯大数乘法大数乘法
分治递归法
基本思想:
设X和Y都是n位的二进制(注1)整数,现在要计算它们的乘积XY。
我们将n位的二进制整数X和Y各分为2段,每段的长为n/2位(注2),如图所示。
由此,X=A*2^n/2+B ,Y=C*2^n/2+D。这样,X和Y的乘积为:
XY=(A*2^n/2+B)(C*2^n/2+D)=AC*2^n+(AD+CB)*2^n/2+BD     (1)
注:,为方便取二进制介绍
,假设n是2的幂
7/12
大数乘法、递归
硕夹酱菩凝赫兵耪尔纶泳诚复嗜淹颇力路臭赖蹈经鲍屈坎拂据漳殿滑暖剩大数乘法大数乘法
分治递归法
如果按式(1)计算XY
我们必须进行4次n/2位整数的乘法--AC,AD,BC和BD,
以及3次不超过n位的整数加法--分别对应于式(1)中的加号
此外还要做2次移位--分别对应于式(1)中乘2^n和乘2^n/2。
所有这些加法和移位共用O(n)步运算。
设T(n)是2个n位整数相乘所需的运算总数,则由式(1),我们有:                            &#