《大整数乘法运算论文24561.doc》由会员分享，可在线阅读，更多相关《大整数乘法运算论文24561.doc（15页珍藏版）》请在三一办公上搜索。
1、摘要大整数乘法运算经常会遇到溢出或精度不够的问题，而在许多领域要求高精度大整数运算。因而，有很多人在这方面作过努力。大整数运算比较通用的方法有叠加法（小学生乘法）和分治法。叠加法与我们笔算乘法一样，用第一个数的每一位去乘第二个数的每一位，然后把运算结果按权值叠加；分治法是把大整数化为可直接运算的小整数，再进行乘法运算，最后把乘得的结果组合为所求结果。本文在总结这两种方法的基础上，提出一种把叠加与分治相结合的方法叠加分治法。叠加分治法吸收了叠加法和分治算法的优点。该算法基于分治思想，把大整数分解成较小整数（几十位），再用叠加法运算较小整数，最后把运算结果组合为所求的积。一方面，减少较小整数多次分
2、解与组合带来的在时间上和空间上的开销；另一方面，避免大整数叠加运算在时间上与规模成级数增加开销。最后，本文还设计了一个算法演示程序，对分治算法、叠加算法与本文提出的叠加分治法做出定量分析，并就它们的优劣和适用环境做出详尽阐述。关键词大整数、乘法、分治法、叠加法、叠加分治法第1章 算法设计1.1 叠加法叠加算法就是通用的笔算算法思想。在两个大整数相乘中，它用第一个数的每一位去乘第二个数的每一位，再把运算结果按权值叠加，进位处理后，得到所求的结果。具体描述如下文所示。将因数和表示如下：， 则和可以记为：， 因此，大整数乘法的计算公式为： （2.1）在本文中，为了方便起见，将的结果称为部分积，将、称
3、为部分因子。根据公式（2.1），大整数叠加算法的计算过程如图2.1所示。从图2.1可知，这种算法的思想是：按照部分积的权值从低到高的顺序，每次计算出所有权值为的部分积，同时完成它们之间的累加，然后再计算权值更高的部分积，依次类推，直到计算出所有的部分积。图2.1中，是权值为的部分积的累加之和，其计算方法如公式（2.2）所示： （2.2）图2.1叠加法大整数乘法算法根据图2.1所描述的算法思想，得到如下伪代码描述的算法：Function Mult(X, Y)/X和Y是记录两个整数的数组，返回结果为X和Y的乘积XYFor (i = 1； i len(x)；i+) /乘积叠加运算For (j = 1
4、；j len(y)；j+) R(i+j-1) += X(i) * Y(j)For (i = 1 ；i len(x) + len(y)；i+) R(i) 向R(i+1) 进位Return R/ Mult算法 2.1由公式（2.1）得，叠加算法共做次乘法。由2.1.1节和图2.1知，该算法还需做次加法运算和次进位处理。在计算时间主要由乘法决定的情况下，它的时间复杂度为： （2.3）又根据图2.1，存储和分别花费单元，存储积需要个单元，因此该算法的空间复杂度为： （2.4）1.2 分治法1.2.1 分治法思想简介分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击
5、破，分而治之。1、分治法所能解决的问题一般具有以下几个特征5：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征
6、，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。2、分治法的基本步骤6如图2.2所示，分治法在每一层递归上都有三个步骤：解答子问题1解答子问题2规模为的问题规模为的子问题1规模为的子问题2合并为原问题的解图2.2 分治技术（典型实例）（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。它的一般的算法设计模式如下：Divide-and-Conq
7、uer（P）if |P|n0 then return（ADHOC（P）将P分解为较小的子问题P1、P2、Pkfor i1 to kdo yi Divide-and-Conquer（Pi） / 递归解决PiT MERGE（y1，y2，yk） / 合并子问题Return（T）算法2.2其中|P|表示问题P的规模；为一阈值，表示当问题P的规模不超过时，问题已容易解出，不必再继续分解。ADHOC（P）是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过时，直接用算法ADHOC（P）求解。 算法MERGE（y1，y2，yk）是该分治法中的合并子算法，用于将P的子问题P1、P2、Pk
8、的相应的解y1、y2、yk合并为P的解。根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分
9、析。1.2.2 用分治法设计大整数乘法明显地，如果用经典的小学生乘法计算两个位数的大整数，将需要做次乘法运算。似乎不可能有一种算法能使乘法运算次数少于，但事实证明并非如此。分治法就是一个明显的例子。设和都是位的进制整数，现在要计算它们的乘积。将和分别分为2段，每段的长为位(为简单起见，假设是2的幂)，如图2.3所示。图2.3 大整数和的分段由此， ，。这样，和的乘积为： （2.5）如果按照公式（2.5）计算，则我们必须进行4次位整数的乘法(，和)，以及3次不超过位的整数加法(分别对应于公式(2.1)中的加号)，此外还要做2次进位处理(分别对应于公式（2.5）中乘和乘)。所有这些加法和进位共用步
10、运算。设是2个n位整数相乘所需的运算总数，由公式（2.5），则有： （2.6）由此可得。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式: （2.7）虽然公式(2.7)看起来比公式（2.5）要复杂些，但它仅需做3次位整数的乘法(，和)，6次加、减法和2次进位。由此可得： .（2.8）用解递归方程的套用公式法，可得其解为： （2.9）由此可见，改用分治法做大整数乘法，从理论上讲，效率有明显提高。根据以上描述的思想，得出大整数相乘的伪代码算法MULT，如下所示：Function MULT(X，Y，n)/X和Y为2个小于n位的无符号整数，返回结果为X和Y的乘积XYif（n =
11、 1）return(X * Y)elseA = X的左边n/2位： B = X的右边n/2位C = Y的左边n/2位： D = Y的右边n/2位ml = MULT(A, C, n/2)m2 = MULT(A-B, D-C, n/2)m3 = MULT(B, D, n/2)S = S * (m1左移2n位 + (m1 + m2 + m3)左移n位 + m3)return(S) /MULT算法2.3公式（2.9）已经给出分治算法的时间复杂度，现在只讨论该算法的空间复杂度。由公式（2.7）可以看出，存储、需要个单元格，存储、A、B、C、D需要个单元格，存储和需要个单元格。由此可得，X乘以Y需要存储空
12、间： .（2.10）用解递归方程的套用公式法，可得其解为： （2.11）于是，用分治法实现大整数相乘的时间复杂度为，空间复杂度为。1.3 叠加分治法由2.1节和2.2节对叠加法和分治法的描述及其效率的分析可知，在理论上讲，分治法的时间效率要高于叠加法。但是，在实际上并非如此6。当整数位数很小（如位数小于600）时，分治法的效率反而不如叠加法。这是因为分治法在分割和合并过程中要消耗掉大量的时间，规模越小，分割合并所占的时间比例越大。试想，用另一种方法。既可以避免叠加法在运算过程中因规模增大，时间复杂度以增大；又可以避免因分治法分得过细而带来的分割组合时间的大量增加。这就是本文要提出的叠加分治法。
13、叠加分治法是用分治思想，把超大整数分割成较小整数（一般在30位左右），再用叠加法计算较小整数的积，最后合并为超大整数的积。叠加分治法的伪代码描述如下所示：Function MULT(X，Y，n)/X和Y为2个n位的无符号整数，返回结果为X和Y的乘积XYif（n=LL） /LL为分割上限，当乘数的规模小于LL，不再分割，调用叠加运算Return Pen-and-Pencil(X ,Y) /用叠加法计算X，Y的积elseA = X的左边n/2位B = X的右边n/2位C = Y的左边n/2位D = Y的右边n/2位ml = MULT(A, C, n/2)m2 = MULT(A-B, D-C, n/
14、2)m3 = MULT(B, D, n/2)S = (m1左移2n位 + (m1 + m2 + m3)左移n位 + m3)return(S)算法2.4F2 分治与大整数乘法F2.1分治分治可能是最著名的通用算法设计技巧。虽然它的名气与它的名字易于记忆有关，但这是当之无愧的：相当多的高效率算法都是这种算法规则的特殊实现。分治法按如下规则运行：1. 将问题实例分成几个性质相同的规模较小的问题实例，最好是它们的规模相同。2. 解答较小的问题实例（典型的方法有递归，虽然当问题变得足够小时，有时引入有其他算法来解决问题）。3. 如果有必要，就把小问题的解合并起来，组成原问题的解。分治的流程如图1所示，它
15、描述了把一个问题分成两个更小的子问题的实例，这种实例是目前最广泛的实例（至少对于用分治法设计的单CUP机器上执行的算法规则是这样的）解答子问题1解答子问题2规模为的问题规模为的子问题1规模为的子问题2合并为原问题的解图1 分治技术（典型实例）待添加的隐藏文字内容2例如，先来考虑这样一个问题：计算个数的和。如果，可以把这个问题分成两个相同性质的子问题：计算前个数的和以及计算后个数的和。（当然，如果就只需要把作为返回值。）当这两个和都计算完备（通过递归应用上述方法），就可以得到原始问题的解：这是一种计算个数之和的高效的方法么？第一反应（这怎么会比简单地顺序相加效率高？），假定一个用这种方法给四个数
16、求和的例子，并且对它进行分析（参见下文），认为（我们不会这样加的，不是么？）所有这些将导致这个问题的否定答案。因此，分治法并不是在所有场合都比简单蛮算效率更高。但通过分析算法效率时，得到的答案是没有任何一种算法规则在时间上的开销比分治法少。实际上，在计算机科学上，许多最重要的高效的算法都是基于分治法。我们将在这章讨论一些经典关于分治法的例子。虽然在这儿考虑的仅仅是顺序算法，但值得我们记住分治技术是解决相同计算问题的理想技术，因为各个子问题都可以有不同的CPU同时计算。这个求和的例子是分治法应用中最典型的特例：一个规模为的问题分解成规模为的两个小问题。更一般地，一个规模为的问题可以分解成几个规模
17、为的小问题，其中有个小问题需要求解。（这儿，和为常数，并且，。）为简化分析，假设是的幂，我们将得到下面的运行时间的递归式： （1）其中是记录分解问题和合并小问题答案所花时间的函数。（如求和例子， 且。）递归式（1）就是一般的分治递归式。很明显，的答案的增长率由常数、的值和函数的增长率共同决定。许多分治算法的效率分析都向如下定理一样，非常简单。主定理 如果，并且在递归方程（1）中，那么， （2）（类似的结论对符号和也成立）例如，当时，用分治算法计算数组的和的递归式（如上所示）为： .(3)也就是说，对于这个例子，；因此，当时， (4)注意，通过这个定理，无需对递归式求解，就可以知道该算法的效率类
18、型。当然，这种方法只能在已知初始条件下求解一个算法的增长次数。F2.2大整数乘法某些应用软件，特别是现代的密码技术，需要对超过100位十进制整数进行乘法运算。显然，这种整数对于现代单“字”长计算机直接计算是太长了，因此它们需要作特别处理。这是研究高效的大整数乘法运算的现实需求。在这节中，我们略述了一个有趣的大整数乘法算法。明显地，如果我们用经典的小学生乘法计算两个位整数相乘，用第一个数的每一位去乘第二个数的每一位，将需要做次位乘法。（如果有一个数的位数少一些，我们可以在它的高位加零补足。）似乎不可能有一种算法能使位乘次数少于，但事实证明并非如此。分治技术的魔力帮助我们完成了这一壮举。为阐述这种
19、算法的基本思想，让我们来看看一个两位数的例子，23和14。它们可以描述如下： 和 现在把它们相乘：当然，上式的正确结果为322，但它如同小学生乘法一样，需要做四次位乘。幸运的是，我们可以利用必需计算的结果()和来计算中间项。当然，我们刚才计算的数字没有什么特别的。对于任意一对两位数，和，它们的积可以按如下公式计算：其中是它们高位数的积是它们低位数的积是的高半位加低半位之和与的高半位加低半位之和的积，再减去与的和，得到的结果。现在我们用这个诀窍来计算两个位整数和的积，其中为正偶数。让我们把两个数字一分为二毕竟，我们承诺利用分治技术。我们把的高半位记为， 的低半位记为；同样把的高半位和低半位分别记
20、为和。在这些符号中，的意思是，的意思是。因此，利用两位数计算技巧，可得：其中是它们高半位的积是它们低半位的积是的两个半位数值之和与的两个半位数值之和的积，再减去与的和，得到的结果。如果还是偶数，我们可以用同样的方法来计算，的值。因此，如果是2的幂，我们可以得到一个计算两个位数的递归算法。从形式上看，这个递归式结束的条件是等于1。也可以在小到可以直接计算的情况下结束这个递归式。这种算法需要做多少乘法运算？因为两个位数相乘，需要做3次两个位数的乘法，因此两个数相乘需要运算的次数如下式所示：当，将得到如下的解：令，则（在最后一步，我们利用了对数的性质：）应当知道，对于规模不是很大的整数，该算法运行的
21、时间可能比经典算法更长。Brassard和Bratley（BB96，7071页）曾经申明：他们的实验显示，当两个数位数超过600位时，分治法的性能超越了叠加算法的性能。如果你是在面向对象语言如Java、C+、Smalltalk中设计程序，会发现这些语言有专门处理大整数运算的的类。写不写都行。不写的话就删除这章好了。仅“同等学历”的同学需要写这个。什么是“同等学历”？我也不懂。L千万不要删除行尾的分节符，此行不会被打印。不要在此行和下页的注释之间填写任何内容下面的内容是参考文献，通过“插入”“引用”“脚注和尾注”，插入尾注到“文档结尾”后，word会自动生成序号。双击序号能自动定位。移动引用位置会自动重新编号。还可以插入“交叉引用”，实现对一篇文献的多次引用。因为本人能力所限，不能将其自动放入前面的“参考文献”章节内，也不能去掉接下来的这半条直线，所以就只能麻烦您这么做了：打印前，备份文档，然后将下面的内容copy & paste到“参考文献”内，并要手工修改序号。注意！copy前一定要备份！以后再做修改时，要修改备份文档。
