1、第 1 页 共 31 页摘要大整数乘法运算经常会遇到溢出或精度不够的问题，而在许多领域要求高精度大整数运算。因而，有很多人在这方面作过努力。大整数运算比较通用的方法有叠加法（小学生乘法）和分治法。叠加法与我们笔算乘法一样，用第一个数的每一位去乘第二个数的每一位，然后把运算结果按权值叠加；分治法是把大整数化为可直接运算的小整数，再进行乘法运算，最后把乘得的结果组合为所求结果。本文在总结这两种方法的基础上，提出一种把叠加与分治相结合的方法叠加分治法。叠加分治法吸收了叠加法和分治算法的优点。该算法基于分治思想，把大整数分解成较小整数（几十位） ，再用叠加法运算较小整数，最后把运算结果组合为所求的积。
2、一方面，减少较小整数多次分解与组合带来的在时间上和空间上的开销；另一方面，避免大整数叠加运算在时间上与规模成级数增加开销。最后，本文还设计了一个算法演示程序，对分治算法、叠加算法与本文提出的叠加分治法做出定量分析，并就它们的优劣和适用环境做出详尽阐述。关键词 大整数、乘法、分治法、叠加法、叠加分治法第 2 页 共 31 页第 1 章 算法设计1.1 叠加法叠加算法就是通用的笔算算法思想。在两个大整数相乘中，它用第一个数的每一位去乘第二个数的每一位，再把运算结果按权值叠加，进位处理后，得到所求的结果。具体描述如下文所示。将因数 和 表示如下：XY， 0121.xxn 0121.yyYn则 和 可
3、以记为：， 10niirxX10njjry因此，大整数乘法的计算公式为：（2.1）10120nij jijinii ryxrRY在本文中，为了方便起见，将 的结果称为部分积，将 、 称为部分因子。jiyx ixjy根据公式（2.1） ，大整数叠加算法的计算过程如图 2.1 所示。从图 2.1 可知，这种算法的思想是：按照部分积的权值从低到高的顺序，每次计算出所有权值为 的部分积，ir同时完成它们之间的累加，然后再计算权值更高的部分积，依次类推，直到计算出所有的部分积。图 2.1 中， 是权值为 的部分积的累加之和，其计算方法如公式（2.2）所示：iRir（2.2）1)(0 1-2ni 0 ni
4、kkiikki yx第 3 页 共 31 页图 2.1 叠加法大整数乘法算法根据图 2.1 所描述的算法思想，得到如下伪代码描述的算法：Function Mult(X, Y)/X 和 Y 是记录两个整数的数组，返回结果为 X 和 Y 的乘积 XYFor (i = 1； i len(x)；i+) /乘积叠加运算For (j = 1；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
5、 节和图 2.1 知，该算法还需做2n次加法运算和 次进位处理。在计算时间主要由乘法决定的情况下，它的时间复杂度2nn2为：)(T（2.3）)(2OT又根据图 2.1，存储 和 分别花费 单元，存储积 需要 个单元，因此该算法XYnXYn2的空间复杂度为：（2.4）)(nS第 4 页 共 31 页1.2 分治法1.2.1 分治法思 想 简介分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。1、分治法所能解决的问题一般具有以下几个特征 5：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问
6、题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。2、分治
7、法的基本步骤 6如图 2.2 所示，分治法在每一层递归上都有三个步骤：第 5 页 共 31 页解答子问题 1 解答子问题 2规模为 的问题n规模为的子问n/2题 1规模为的子问n/2题 2合并为原问题的解图 2.2 分 治 技 术 （ 典 型 实 例 ）（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。它的一般的算法设计模式如下：Divide-and-Conquer（P ）if |P|n0 then return（ADHOC（P ） ）将 P 分解
8、为较小的子问题 P1、P2、Pkfor i1 to k do yi Divide-and-Conquer（Pi） / 递归解决 PiT MERGE（y1，y2，yk） / 合并子问题Return（T ）算法 2.2其中|P|表示问题 P 的规模； 为一阈值，表示当问题 P 的规模不超过 时，问题已0n 0n容易解出，不必再继续分解。ADHOC（P）是该分治法中的基本子算法，用于直接解小规第 6 页 共 31 页模的问题 P。因此，当 P 的规模不超过 时，直接用算法 ADHOC（P）求解。 0n算法 MERGE（y1，y2，yk）是该分治法中的合并子算法，用于将 P 的子问题P1、P2、Pk
9、的相应的解 y1、y2、yk 合并为 P 的解。根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k 个子问题的处理方法是行之有效的。许多问题可以取 k=2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具
10、体问题具体分析。1.2.2 用分治法设计大整数乘法明显地，如果用经典的小学生乘法计算两个 位数的大整数，将需要做 次乘法运算。n2n似乎不可能有一种算法能使乘法运算次数少于 ，但事实证明并非如此。分治法就是一2个明显的例子。设 和 都是 位的 进制整数，现在要计算它们的乘积 。将 和 分别分为 2XYnr XY段，每段的长为 位(为简单起见，假设 是 2 的幂)，如图 2.3 所示。/2n位位位位 ， 2/2/2/2/ DC nnnnBAX图 2.3 大整数 和 的分段 XY由此， ， 。这样， 和 的乘积为：r n/2DrCYn/2（2.5）BDC)r(Ar)B)(AXn/2n/ 如果按照公
11、式（2.5）计算 ，则我们必须进行 4 次 位整数的乘法( ， ，/ A和 )，以及 3 次不超过 位的整数加法(分别对应于公式(2.1)中的加号)，此外还要BCDn做 2 次进位处理( 分别对应于公式（2.5）中乘 和乘 )。所有这些加法和进位共用nr/2步运算。设 是 2 个 n 位整数相乘所需的运算总数，由公式（2.5） ，则有：On)T()第 7 页 共 31 页（2.6）1n )(2/(4 )1(OnT由此可得 。要想改进算法的计算复杂性，必须减少乘法次数。为此我们)OnT(2把 XY 写成另一种形式:（2.7）BDrAC)-B(DACrXYn/2n 虽然公式(2.7) 看起来比公式
12、（2.5）要复杂些，但它仅需做 3 次 位整数的乘法/( ， 和 )，6 次加、减法和 2 次进位。由此可得： ACBD-(.（2.8）1nc 3T(/) 1n用解递归方程的套用公式法，可得其解为：（2.9）)()()59.13log2O由此可见，改用分治法做大整数乘法，从理论上讲，效率有明显提高。根据以上描述的思想，得出大整数相乘的伪代码算法 MULT，如下所示：Function MULT(X，Y，n)/X 和 Y 为 2 个小于 n 位的无符号整数，返回结果为 X 和 Y 的乘积 XYif（n = 1）return(X * Y)elseA = X 的左边 n/2 位： B = X 的右边
13、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）已经给出分治算法的时间复杂度，现在只讨论该算法的空间复杂度。第 8 页 共 31 页由公式（2.7）可以看出，存储 、 需要 个单元格，存储、A 、B、C、D 需要XYn2个单元格，存储 和 需要 个单元格。由此可得，X 乘以 Y 需要存储空间：
14、24nBACD.（2.10）2n )(2/(31 )1(OnS用解递归方程的套用公式法，可得其解为：（2.11）)()()59.13log2于是，用分治法实现大整数相乘的时间复杂度为 ，空间复杂度为)()59.1nT。)()59.1nOS1.3 叠加分治法由 2.1 节和 2.2 节对叠加法和分治法的描述及其效率的分析可知，在理论上讲，分治法的时间效率要高于叠加法。但是，在实际上并非如此 6。当整数位数很小（如位数小于600）时，分治法的效率反而不如叠加法。这是因为分治法在分割和合并过程中要消耗掉大量的时间，规模越小，分割合并所占的时间比例越大。试想，用另一种方法。既可以避免叠加法在运算过程中
15、因规模增大，时间复杂度以增大；又可以避免因分治法分得过细而带来的分割组合时间的大量增加。这就是本文2n要提出的叠加分治法。叠加分治法是用分治思想，把超大整数分割成较小整数（一般在 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 的左边
16、n/2 位B = X 的右边 n/2 位C = Y 的左边 n/2 位第 9 页 共 31 页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 = (m1 左移 2n 位 + (m1 + m2 + m3)左移 n 位 + m3)return(S)算法 2.4F2 分治与大整数乘法F2.1 分治分 治 可 能 是 最 著 名 的 通 用 算 法 设 计 技 巧 。 虽 然 它 的 名 气 与 它 的 名 字 易 于 记 忆 有关 ， 但 这 是 当 之 无 愧 的 ： 相 当 多 的
17、高 效 率 算 法 都 是 这 种 算 法 规 则 的 特 殊 实 现 。 分 治法 按 如 下 规 则 运 行 ：1. 将 问 题 实 例 分 成 几 个 性 质 相 同 的 规 模 较 小 的 问 题 实 例 ， 最 好 是 它 们 的 规 模 相 同 。2. 解 答 较 小 的 问 题 实 例 （ 典 型 的 方 法 有 递 归 ， 虽 然 当 问 题 变 得 足 够 小 时 ， 有 时 引入 有 其 他 算 法 来 解 决 问 题 ） 。3. 如 果 有 必 要 ， 就 把 小 问 题 的 解 合 并 起 来 ， 组 成 原 问 题 的 解 。分 治 的 流 程 如 图 1 所 示 ，
18、 它 描 述 了 把 一 个 问 题 分 成 两 个 更 小 的 子 问 题 的 实 例 ， 这种 实 例 是 目 前 最 广 泛 的 实 例 （ 至 少 对 于 用 分 治 法 设 计 的 单 CUP 机 器 上 执 行 的 算 法 规则 是 这 样 的 ）第 10 页 共 31 页解答子问题 1 解答子问题 2规模为 的问题n规模为的子问n/2题 1规模为的子问n/2题 2合并为原问题的解图 1 分 治 技 术 （ 典 型 实 例 ）例 如 ， 先 来 考 虑 这 样 一 个 问 题 ： 计 算 个 数 的 和 。 如 果 ， 可 以 把n10,.na1n这 个 问 题 分 成 两 个 相
19、 同 性 质 的 子 问 题 ： 计 算 前 个 数 的 和 以 及 计 算 后 个 数2/ 2/的 和 。 （ 当 然 ， 如 果 就 只 需 要 把 作 为 返 回 值 。 ） 当 这 两 个 和 都 计 算 完 备 （ 通1n0a过 递 归 应 用 上 述 方 法 ） ， 就 可 以 得 到 原 始 问 题 的 解 ：).().(. 12/12/010 nnnn aaa这 是 一 种 计 算 个 数 之 和 的 高 效 的 方 法 么 ？ 第 一 反 应 （ 这 怎 么 会 比 简 单 地 顺 序相 加 效 率 高 ？ ） ， 假 定 一 个 用 这 种 方 法 给 四 个 数 求 和
20、的 例 子 ， 并 且 对 它 进 行 分 析（ 参 见 下 文 ） ， 认 为 （ 我 们 不 会 这 样 加 的 ， 不 是 么 ？ ） 所 有 这 些 将 导 致 这 个 问 题 的否 定 答 案 。因 此 ， 分 治 法 并 不 是 在 所 有 场 合 都 比 简 单 蛮 算 效 率 更 高 。 但 通 过 分 析 算 法 效 率时 ， 得 到 的 答 案 是 没 有 任 何 一 种 算 法 规 则 在 时 间 上 的 开 销 比 分 治 法 少 。 实 际 上 ， 在 计算 机 科 学 上 ， 许 多 最 重 要 的 高 效 的 算 法 都 是 基 于 分 治 法 。 我 们 将 在 这 章 讨 论 一 些 经 典关 于 分 治 法 的 例 子 。 虽 然 在 这 儿 考 虑 的 仅 仅 是 顺 序 算 法 ， 但 值 得 我 们 记 住 分 治 技 术 是解 决 相 同 计 算 问 题 的 理 想 技 术 ， 因 为 各 个 子 问 题 都 可 以 有 不 同 的 CPU 同 时 计 算 。这 个 求 和 的 例 子 是 分 治 法 应 用 中 最 典 型 的 特 例 ： 一 个 规 模 为 的 问 题 分 解 成 规n
