毕业设计（论文）-超大整数算术运算算法的设计与实现.pdf

目目 录录 第一章 绪论 . 1 1.1 题目的背景 . 1 1.2 本课题研究内容 . 1 第二章 大整数的结构 . 2 2.1 大整数的存取 . 2 2.2 预定义的变量 . 2 2.3 大整数基本函数定义 2 2.4 大整数的输入和输出函数 3 第三章 大整数加法和减法实现 6 3.1 符号相同的加法运算及符号位不同的减法运算 . 6 3.2 减法运算及符号不相同的加法运算 . 9 第四章 大整数乘法的实现 .13 4.1 笔算乘法 .13 4.2 笔算乘法的机器实现 13 第五章 大整数除法实现.17 5.1 模拟笔算除法 17 5.1 模拟笔算除法的机器实现 .17 结 论 .21 参 考 文 献 21 致 谢 .22 附录 a .23 附录 b .31 超大整数算术运算算法的设计与实现超大整数算术运算算法的设计与实现 安徽师范大学, 数学计算机科学学院 摘 要：随着计算机信息安全要求的不断提高，密码学被大量应用到生活中。 本文基于 32 位的系统，首先采用模块化的思想建立大整数运算库的基础框架， 在实现一些辅助函数后在此框架上讨论并实现高精度大整数的基本加法、减法、 乘法、除法等算法。所用程序均采用 java 语言编写，所采用的优化也均建立在 java 语言这一层面上，在保证算法有足够高的效率的同时力求代码清晰易懂， 函数接口简单明了，具有可移植性和稳定性。 关键词：超大整数；二分查找；模块化思想 the design and realization of super integer arithmetical algorithm anhui normal university，school of mathematics and computer science abstract：nowadays, as computer information security requirements improve continuously, the cryptology has been widely applied to life. this paper is based on the 32 bit system. first of all, we found the modular foundation of multiple precision arithmetic library; after some auxiliary function is formed, we discuss and implement the multiple precision integer basic addition, subtraction,multiplication, , kinds of square algorithms,division,reduction, and some relational function. all the algorithm discuss in this paper is implement entirely in portable iso c/c+and the optimization of those algorithms implementations is built on the c/c+ language level. the algorithm has high enough to ensure the efficiency of the code at the same time strive to clearly understand, simple interface function with portability and stability. key words：oversized integer,；binary search； modular thought 1 第一第一章章 绪论绪论 1.11.1 题目的背景题目的背景 科学技术和网络的发展使计算机深入到了各行业的方方面面， 计算机在带来 方便和提高了工作效率的同时却也带来了各种各样的新问题， 其中信息安全问题 最为突出， 随着计算机信息安全要求的不断提高, 计算机保密系统已变得越来越 重要。随着香农定理的发表，信息安全技术得到了迅猛的发展。密码学应用不再 是局限于军事、国防等有限领域，而是迅速的走进了千家万户。rsa、elgamal、 dsa、ecc 等公钥密码算法和数字签名等算法得到了快速发展。其实现都是建 立在大整数运算的基础上，耗时的大整数乘法、除法、模乘、幂运算、模幂乘等 运算更是被上述算法大量使用。 而计算机微机的字长限制对信息安全中大整数的 操作，带来了巨大的困难。它们的运算速度对这些算法的高效实现起着重要的作 用，如何快速实现上述几种运算是公钥密码领域普遍关注的热点问题。 1.21.2 本课题研究本课题研究内容内容 本文基于 32 位的系统，首先采用模块化的思想建立大整数运算库的基础框 架， 在实现一些辅助函数后在此运算库框架上讨论并实现多精度大整数的基本加 法、减法、乘法、除法等算法。本文讨论的所用程序均采用 java 语言编写，所 采用的优化也均建立在 java 语言这一层面上，在保证算法有足够高的效率的同 时力求代码清晰易懂，函数接口简单明了，具有可移植性和稳定性。 2 第二章第二章 大整数的结构大整数的结构 2.12.1 大整数的存取大整数的存取 大整数运算是一些相当复杂的运算，本文要实现的是大整数基本运算，采用 模块化思想按照层次结构来设计及实现一些其它的辅助函数， 而不是把它们内嵌 在算法函数内，这样既能够避免算法函数的程序代码的过分冗长，使代码清晰易 懂、突出算法过程又能够使程序易于测试、排错、更新和复用。由于本文是介绍 大整数的基本算法，在本文开始之前只介绍一些关键的辅助函数，其它辅助函数 是在相关算法实现的时候再简略介绍它的功能。 在一般的高级语言中，对数组的使用都是先定义后使用，并用在定义时就要 申明数组的大小，但本文所使用的 java 语言中，对数组的使用可以在定义时不 申明数组的大小，而是在函数调用时自动为其分配一定的空间。所以在本文中对 数组的临时存储问题变得简单。 2.22.2 预定义的变量预定义的变量 因为在编程的时候很多的变量字符比较长，很容易略写某个字符，造成编程 错误，所以本文首先对一些变量进行预定义。 string s1 = “ “; string s2 = “ “; calculatenumber c = new calculatenumber(); string s3, s4, s5; system.out.println(s3 = c.div(s1, s2); system.out.println(s4 = c.getremnant(); system.out.println(s5 = c.add(s4, c.mul(s2, s3); system.out.println(s1.equals(s5); 对于大整数的符号，本文只区分正数与负数，若其第一个字条符为“-” ，表 示该大整数为负数，若其第一个字符为数字或者是“+” ， 则表示该大整数是一 个正数。若文本中含有其它的符号均不能被识别。 2.32.3 大整数基本函数定义大整数基本函数定义 因为在大整数的基本运算中，很多的操作都是类似和重复的，所以本文在 开始介绍基本运算之前，先对这些基础函数进行说明。 public string add(string num1, string num2) throws numberexception/加法 public string del(string num1, string num2) throws numberexception/减法 public string mul(string num1, string num2) throws numberexception/乘法 private byte stringtobytearray(string str) throws numberexception/除法 3 2.2.4 4 大整数的输入和输出函数大整数的输入和输出函数 由于本文是对大整数进行操作，而大整数的长度一般都很长，所以在程序实 现时，对数据的读取和输出全部都能过记事本来操作，这样既便于数据的操作， 又能很好的掌握和分析运算的结果。 public void actionperformed(actionevent e) try if (e.getactioncommand().equals(“scan1“) fileinputstream fis = null; try jfilechooser jfc = new jfilechooser(); jfc.showopendialog(frame); file f1 = jfc.getselectedfile(); if (f1 = null) return; jtf1.settext(f1.getabsolutepath(); byte b = new byte(int) f1.length(); fis = new fileinputstream(f1); fis.read(b); s1 = new string(b); finally if (fis != null) try fis.close(); catch (ioexception e1) else if (e.getactioncommand().equals(“scan2“) fileinputstream fis = null; try jfilechooser jfc = new jfilechooser(); jfc.showopendialog(frame); file f2 = jfc.getselectedfile(); if (f2 = null) return; jtf2.settext(f2.getabsolutepath(); byte b = new byte(int) f2.length(); fis = new fileinputstream(f2); fis.read(b); s2 = new string(b); finally if (fis != null) try 4 fis.close(); catch (ioexception e1) 因为我们最为熟悉的数字和使用的最多的也是十进制表示形式， 所以本文对 大整数的输入和输出都是使用十进制形式。只是由于是对大整数进行操作，字符 长度大都超过千位，所以本文对大整数的读取和输出都通过生成记事本文件，并 将结果保存在与执行文件相同的目录下。函数 read_radix(mbigint *bi,char *str) 是 将 十 进 制 表 示 的 字 符 串 读 入 并 转 换 为 大 整 数 结 构 表 示 ； 函 数 write_radix(mbigint *bi,char *str)将大整数转换为十进制的字符串表示。 当然可以 通过对以上两个函数的修改，形成不同的 b 进制输入和输出方式。 图 2.2 程序运行界面 说明：程序界面中有两个输入框和六个按钮，其中 scan1 和 scan2 分别是用 来浏览操作数的文件位置，开始时，输入框内显示“数字 1（2）所在的文本文 件” ，而选择好操作数文件后，会自动显示操作数文件所在的地址。其余四个按 钮的名称是加/减/乘/除运算的英文简称，它们的作用分别是对所选择的操作数进 行相应的加/减/乘/除操作。界面下方也显示两行内容，如图，第一行始终不变， 而第二行结束时显示如上图，运行时则显示“正在计算” 。 5 是 否 图 2.3 程序总流程图 说明：上图是程序的总体框架流程图，程序运行以后，用户只需要指定两个 操作数所在的文件和所要进行何种运算即可，其它的都是内部流程，由程序自己 执行。当用户操作结束时，程序根据用户选择的操作调用相应的类算法，在各算 法中判断有无异常用，若没有，则程序往下执行，得到结果，并最终将结果保存 到 result.txt 文档中，除法的余数保存到 factorial.txt 中，若有异常，则程序直接 返回异常得到结果。 开始 找到两个操作数所在的.txt 文件 将.txt 文件内容转换为数字串 调用加/减/乘/除类 是否异常 将结果及除法的余数 保存到.txt 文件中 结束 6 第三章第三章 大整数加法和减法实现大整数加法和减法实现 由于大整数有正负之分，所以两个大整数相加有四种情况：a+b，a+（-b） ， （-a）+b 和-a+（-b） 。对于 a+b 和-a+(-b)，可以通过对数组对应位元素相加即可， 主要是考虑进位问题。而 a+（-b）和（-a）+b，其实就是两个大整数的减法，其 主要考虑的问题是向高位借位的问题。所以减法可以通过加法的运算得到结果。 3.13.1 符号相同的加法运算及符号位不同的减法运算符号相同的加法运算及符号位不同的减法运算 符号相同的加法运算的实现过程是基于这样的一个原因：因为两个整数的符 号相同，可以直接对两个整数数组对应位元素相加，并考虑进位问题。因为两个 整数的数位存在以下三种情况（不妨设两个大整数分别为 src1 和 src2） ： src1-length = src2-length；src1-length src2-length； src1-length length。所以在处理加法的时候，对数位较大的整数一分为二，第一部分是 跟另一大整数的长度相等。可以先把相同长度部分先计算，然后再对多出的长度 部分直接赋值，这样可以不用考虑谁大谁小问题，而且可以加快运算速度。 7 同 异号 负 同 正 有 无 图 3.1 加法运算流程图 说明：上图是程序中加法运算类的流程图，这个图只是对加法类算法主要部 分图解。当程序无异常并调用加法时，首先判断两个操作数的符号，并有三种分 支，同负、同正、异号。若异号则调用减法，若同负则提取负号后作为正数算， 若同正则直接往下执行。再用两个字节数组 b1 和 b2 来存放两个操作数，并且保 证 b1=b2。完成数据转换后从 b2 按位加到 b1 并完成进位。最后再加上前面的 保留符号即可得到结果。 /符号相同的加法运算实现 public string add(string num1, string num2) throws numberexception if (!num1.startswith(“-“) byte b2; if (num1.length() = num2.length() b1 = stringtobytearray(num1); b2 = stringtobytearray(num2); else b1 = stringtobytearray(num2); 开始 num1 和 num2 的符号 num1,num2 放入字节数 b1,b2 中，且 b1b2 从 b2 按位加到 b1 并完成进位 得结果 有保留负号？ 加上负号 结果 调用减法 保留负号 8 b2 = stringtobytearray(num1); / 保证 b1 数组=b2 数组 for (int i = 0; i = 10) / 进位 b1i -= 10; b1i + 1+; else / 没有进位 if (i b2.length) break; stringbuilder sb = new stringbuilder(); for (int i = b1.length - 1; i = 0; i-) sb.append(b1i); if (sb.length() = 0) sb.append(0); return sb.tostring(); else if (num1.startswith(“-“) /符号位不同的减法实现 else if (num1.startswith(“-“) else if (!num1.startswith(“-“) 运行结果如下： 图 3.2 符号相同的加法运算结果 说明：上图是用本程序所进行的一次大整数加法运算，其中左边两个分别是 加数和被加数，而右边的一个数是加法运算的结果。由于篇幅限制，文中不再列 举加法运算的其它图例。 9 3.23.2 减法运算及符号不相同的加法运算减法运算及符号不相同的加法运算 符号不同的加法运算的过程，也是跟符号相同的加法过程类似。也是对数 位较大的整数进行分段，不过，它也有不同的地方。因为符号不相同，这个加法 就是减法。因为不知道是哪个大整数较大，当它们做减法运算的时候，就有可能 会在最高数位出现负数问题，而大整数各位元素都为正数，所以要多处理一步， 即对负数转换成正整。而如果把无符号整数的较大者作为被减数，就可以省略这 一步。 所以此运算过程是： 先对两个大整数进行无符号比较， 最大者作为被减数， 然后进行减法操作。 10 不同正 是 否 同正 否 + + 是 有 无 图 3.3 减法运算流程图 说明：上图是程序中减法运算类的流程图，这个图只是对加法类算法简要说 明。当程序无异常并调用减法时，首先判断两个操作数的符号，并有两种分支， 同正、不同正。若同正，再判断是否 num1=num2 若是则直接往下执行，否则 保留负号，想到交换后往下执行。若不同正，再判断是否同负，若是，则提取负 号后按同正往下执行，若异号则再进行一次判断，若 num1 为正则调用 |num1|+|num2|，否则提取负号调用|num1|+|num2|，判断符号完成后，用 b2 按位 减 b1 并清除借位，最后加上前面的保留符号便可返回结果。 b2 按位减 b1,并清除借位 保 留 负 号 开始 获得num1 和 num2 num1,num 2 的符号 num1num2 ? num1,num2 放入字节数组 b1,b2 中，且 b1=b2 得结果 有保留负号? 结果 加上负号 同负？ num1的符 号 提 负 号 调 用 num1-num2 调用 |num1|+|num2 提取负号调用 |num1|+|num2 11 /符号不相同的加法运算（减法运算） else if (num1.startswith(“-“) else if (!num1.startswith(“-“) /符号相同的减法运算 f (!num1.startswith(“-“) byte b2; int result = num1biggerthannum2(num1, num2); if (result = 1) b1 = stringtobytearray(num1); b2 = stringtobytearray(num2); else if (result = -1) b1 = stringtobytearray(num2); b2 = stringtobytearray(num1); else return “0“; / 保证 b1 数组 b2 数组 for (int i = 0; i b2 数组, 最高位不可能再借位，因此不会数组越界 stringbuilder sb = new stringbuilder(); for (int i = b1.length - 1; i = 0; i-) if (b1i != 0) / 从第一个不为 0 的数字开始记录进字符串 for (; i = 0; i-) sb.append(b1i); if (sb.length() = 0) return “0“; if (result = 1) return sb.tostring(); else return “-“ + sb.tostring(); else if (num1.startswith(“-“) else throw new numberexception(“unexcepted here“); 12 运算结果如下： 图 3.4 减法运算结果 说明：上图是用本程序所进行的一次大整数减法运算，其中左边两个分别是 被减数和减数（被减数的位数比减数的位数长） ，而右边的一个数是减法运算的 结果。由于篇幅限制，文中就不再列举减法运算的图例。 13 第四章第四章 大整数乘法的实现大整数乘法的实现 现在流行的公钥算法很多都是以模幂为基础的，而计算模幂的过程中大量地 使用了乘法，所以乘法非常重要。然而，通用的乘法都需要 o(n2)次的基本运算， 直到 1962 年发现了 karatsuba 乘法人们才有了历史的突破， 同时该技术也促使人 们发现了更多的有效算法，如基于傅立叶变换的方法。 4.1 4.1 笔算乘法笔算乘法 对于 m 位和 n 位的输入， 传统的乘法需要 m*n 次基本的乘法， 也即算法复杂 度为 o(n2)。我们用纸和笔做乘法运算时，用乘数的每一位乘以被乘数的每一位 并加上上一列的进位而产生一行适当移位的中间结果， 然后再将各行中间结果相 加即得到乘法的最终结果，例如 10 进制下计算 456*32 的过程如表 4.1： 表 4.1 笔算乘法的运算过程 4 5 6 * 3 2 9 1 2 + 1 3 6 8 1 4 5 9 2 本算法按照上述过程进行计算，但在计算机上最好是把内部的乘法和加法并 行的执行，即计算每一行中间结果的同时将该行加到最终结果上，这样既可以省 去不少步骤，也避免了中间结果的空间开销和内存管理操作，这个简单的优化能 够一定程度上提高效率。 由于两个 16 位的乘积将超过 16 位所能表示的最大数， 我们知道一个 32 位的 数能够完整地保存两个 16 位数的乘积，上面的伪码中用一个 32 位来保存两个 16 位的数乘积再加上两个单字后的结果，下面讨论一下它的安全性（是否会产 生溢出） ：上面表达式计算的最大的结果为 (216-1)* (216-1)+(216-1)+(216-1)，化简 后为 232-1，正好是一个 32 位数的最大值，所以一个 32 位数能够保存该表达式 的结果而不产生溢出，程序不会损失精度。 4 4. .2 2 笔算乘法笔算乘法的机器实现的机器实现 在机器中，使用字节数组保存操作数，当两个数相乘时，从低位开始按位向 前乘。两个一位十进制数相乘的可能最大结果为两位数，由于使用字节数组，其 每个元素所能保存的最大十进制数是 127，所以在 b3 数组中的一位能完全保存 当前位乘积的结果，而不用立即进行进位。当 b2 当前位与 b1 乘结束时，将 b3 错位加到 b4 中，再将 b3 置零，依次循环向前乘，直到全部乘完，此时的 b4 是 个无符号的结果，要得到正确的结果，只要找到前面对操作数进行变化时的保留 符号并添加上去就是正确结果。 14 开始 获得 num1,num2 num1,num2 的 符号 |num1|,|num2|放入字节数 组 b1,b2 中，且 b1=b2 b1 与 b2 按位相乘放到 b3 中， b3 错位相加到 b4 中并清除进位 b4 作为结果 有保留负号？ 结果 加上负号 保留负号 异号 同号 有 无 图 4.1 乘法运算流程图 说明：上图是程序中乘法运算类的流程图，这个流程图只是对乘法类算法简 要概括。当程序无异常并调用乘法时，首先判断两个操作数的符号，并有两种分 支，同号、异号。若异号，则提取负号后按正数处理，若同号则直接往下执行。 下一步将两个数放到 b1 和 b2 两个字节数组中，并且在 b1 中放较大的数。接下 来是进行乘法运算的关键，b1 与 b2 按拉相乘放到 b3 中当当前位相乘结束后把 此时的 b3 错位加到 b4 中并将 b3 置零。 所有位都乘结束后， b4 是无符号的结果， 再加上前面的保留符号即得到乘法运算的结果。 /乘法运算算法部分代码 public string mul(string num1, string num2) throws numberexception 15 int res; if (!num1.startswith(“-“) else if (num1.startswith(“-“) res = -1; else if (!num1.startswith(“-“) res = -1; else if (num1.startswith(“-“) num2 = num2.substring(1); res = 1; else throw new numberexception(“unexcepted here“); byte b1; byte b2; int result = num1biggerthannum2(num1, num2); if (result = 1) b1 = stringtobytearray(num1); b2 = stringtobytearray(num2); else b1 = stringtobytearray(num2); b2 = stringtobytearray(num1); byte b3 = new byteb1.length; for (int i = 0; i = 10) / b4 数组被影响的部分进位 b4k + i -= 10; b4k + i + 1+; 16 stringbuilder sb = new stringbuilder(); for (int i = b4.length - 1; i = 0; i-) if (b4i != 0) / 从第一个不为 0 的数字开始记录进字符串 for (; i = 0; i-) sb.append(b4i); if (sb.length() = 0) return “0“; if (res = 1) return sb.tostring(); else return “-“ + sb.tostring(); 图 4.2 笔算乘法运算结果 说明：上图是用本程序所进行的一次大整数乘法运算，其中左边两个分别是 被乘数和乘数，而右边的一个数是乘法运算的结果。由于篇幅限制，文中就不再 列举乘法运算的其它图例。 （本例与下章除法运算是相互验证的） 17 第第五五章章 大整数除法实现大整数除法实现 5 5.1.1 模拟笔算除法模拟笔算除法 此算法是模拟笔算除法的形式，变形而来。根据笔算除法的特性，我们知 道最重要的也是较难的一步是，对商的估算。在此，本程序的设计思路是不进行 试商，而是用减法代替试商，使用错位相减，每向后移一位都做若干次减法，直 到当前位不能再减时向后移位，在 b3 中累计做减法的次数，移位时 b3 也相应移 位，最后再把 b3 转换成字符串，得到结果。 5.15.1 模拟笔算除法模拟笔算除法的机器实现的机器实现 在实际操作时，同字节数组来存放所要用到的操作数，先将将两个操作数放 到字节数组 b1、b2 中，并判断它们的符号，如果异号，则保留负号，然后作为 正数来处理。用 b2 从 b1 的高位开始减 b1，并将当前位上做减法的次数保存到 字节数组 b3 中， 当移位到下一位是， 同样将相减的次数存放到 b3 的对应字节中， 再把 b3 转换成数字串，最后再判断前面是否有保留的负号并得到结果。 18 否 是 否 是 有 无 图 5.1 除法运算流程图 说明：上图是程序中除法运算类的流程图，这个流程图只是对除法类算法简 要概括。当程序无异常并调用除法时，首先判断两个操作数的符号，并有两种分 支，同号、异号。若异号，则提取负号后按正数处理，若同号则直接往下执行。 接着比较两个操作数的大小，若被除数小于除数，则直接返回 0，若被除数较大 开始 获得 num1,num2 num1,num2 同号？ |num1|num2| ？ 将num1,num2放入到字节数 组 b1,b2 中,且 b1=b2 b1 依次错位减去 b2 直到当前位 不能减，相减次数放到 b3 中 b3 转换为字条串 有保留负号？ 结果 保留负号 加上负号 结果为 0 19 则将两个数放到 b1 和 b2 两个字节数组中。接下来是进行除法运算的关键，b1 从高位开始按位减去 b2，每次都减到当前位不能再减时再移到下一位，并将相 减的次数保存到 b3 数组的对应字节中。 所有位都减结束后， b3 是无符号的结果， b1 除法运算的余数。最后在 b3 上加上前面的保留符号即得到乘法运算的结果。 /除法运算部分代码 public string div(string num1, string num2) throws numberexception if (num2.equals(“0“) / 除数为 0 异常 throw new arithmeticexception(“/ by zero“); int res; if (!num1.startswith(“-“) res = 1; else if (num1.startswith(“-“) res = -1; else if (!num1.startswith(“-“) res = -1; else if (num1.startswith(“-“) num2 = num2.substring(1); res = 1; else throw new numberexception(“unexcepted here“); int result = num1biggerthannum2(num1, num2); byte b1; byte b2; b1 = stringtobytearray(“0“ + num1); b2 = stringtobytearray(num2); if (result = 0) b1array = new byte1; b1array0 = 0; return “1“; else if (result = -1) b1array = b1; return “0“; b1array = b1; / result = 1 byte b3 = new byteb1.length - b2.length; for (int i = b3.length - 1; i = 0; i-) while (del(b1, b2, i) / 给 b3 数组的第 i 位，即 b3i赋值 20 b3i+; b2len = b2.length; stringbuilder sb = new stringbuilder(); for (int i = b3.length - 1; i = 0; i-) if (b3i != 0) / 从第一个不为 0 的数字开始记录进字符串 for (; i = 0; i-) sb.append(b3i); if (sb.length() = 0) return “0“; if (res = 1) return sb.tostring(); else return “-“ + sb.tostring(); 图 5.2 模拟笔算除法运算结果 说明：上图是用本程序所进行的一次大整数除法运算，其中左边两个分别是 除数和除法运算的结果（被除数的位数比除数的位数长） ，而右边的一个数是除 法运算的结果。为了更好的检验程序运行的正确性，本次除法运算是对上面乘法 运算的戏证，即本例中的被除数是前面乘法运算的积，而除数则是前面乘法运算 的被乘数。由于篇幅限制，文中就不再列举除法运算的图例。 21 结结 论论 本文基于 32 位的系统，采用模块化的思想建立了大整数运算库的基础框架， 在此框架上讨论并实现了多精度大整数的基本加法和减法、乘法、除法、及相关 的算法。虽然本文讨论和实现的算法程序采用 java 语言编写而没有使用汇编、 sse2 指令、多线程等技术，但算法仍然有足够的效率，并且换来了代码的清晰 性和易懂性，函数代码的平均长度约 50 行左右，所有函数的接口、参数顺序等 均采用统一的规范，同时函数、变量的名字也直观易懂，能够表明其用途。 本文基本完满地完成了当初的设计目标，已经达到一个基本的大数运算库的 规模，但由于时间有限等因素，一些适合特定场合的较少使用的好算法（例如 toom-cook 3-way 乘法， 缩减基缩减算法） 并没有没有在文中讨论并实现。 同时， 本文所讨论的算法实现均假设目标机器具有一定的内存， 并没有考虑到机器内存 非常有限的时候的特殊处理。 本文讨论的主要是大数算术运算中的最常用到的基 本算法，而要实现一个比较好的大数运算库则除此之外还有很多工作要做。大数 算法是一个很大的考验， 既要有不错的软件编码知识又要对硬件细节有足够的了 解，还要求会根据情况自己推导数学公式，优化算法，同时也需要很强的耐心、 足够的细心和大量的时间。 参参 考考 文文 献献 1 宋震.密码学m.北京：中国水利水电出版社. 2002：87-151. 2 王永祥. 超高精度超大数算法与程序设计m. 陕西:西安交通大学出版 社,1990：75-105. 3 耿祥义 张跃平 java 2 实用教程（第三版） 清华大学出版社 2006.8 4 stanley b.lippman, josee lajoie, barbara e.moo. c+ primerm. 北京：人民 邮电出版社，2006：102-180. 22 致致 谢谢 值此毕业论文完成之际，四年的大学生活即将结束，我谨向所有关心、爱 护、帮助过我的人们表示最诚挚的感谢与最美好的祝愿。 首先，感谢我的导师董尼讲师。几个月以来，我时刻体会着董老师严肃的科 学态度，严谨的治学精神，精益求精的工作作风，我想这是够我一生受用的人格 魅力。从专业课学习，课题选择、开题，到程序开发、论文写作，整个过程，董 老师都倾注了大量的心血。正是在董老师科学、严谨的指导下，我的研究课题才 能顺利完成。 感谢数计学院的各位老师和同学在我的生活、 学习和论文撰写过程中给予我 热心的帮助。 最后，向百忙中抽出时间来评审论文的老师表示深深的感谢。再次感谢大家 给予我的指导、支持和帮助。 23 附录附录 a a /程序主函数实现代码 package calculate; import java.math.bigdecimal; import myexception.numberexception; public class calculatenumber /* * param num1 * param num2 * return 返回两个数相加后的结果 * throws exception * 如果 num1 或 num2 中出现非数字， 则抛出 numberexception 异常 */ private byte b1array = null; private boolean canget = false; private integer b2len; public string add(string num1, string num2) throws numberexception if (!num1.startswith(“-“) byte b2; if (num1.length() = num2.length() b1 = stringtobytearray(num1); b2 = stringtobytearray(num2); else b1 = stringtobytearray(num2); b2 = stringtobytearray(num1); / 保证 b1 数组=b2 数组 for (int i = 0; i = 10) / 进位 b1i -= 10; b1i + 1+; else / 没有进位 if (i b2.length) break; stringbuilder sb = new stringbuilder(); 24 for (int i = b1.length - 1; i = 0; i-) sb.append(b1i); if (sb.length() = 0) sb.append(0); return sb.tostring(); else if (num1.startswith(“-“) else if (!num1.startswith(“-“) else if (num1.startswith(“-“) else throw new numberexception(“unexcepted here“); /* * param num1 * param num2 * return 返回 num1-num2 的结果 * throws exception * 如果 num1 或 num2 中出现非数字， 则抛出 numberexception 异常 */ public string del(string num1, string num2) throws numberexception if (!num1.startswith(“-“) byte b2; int result = num1biggerthannum2(num1, num2); if (result = 1) b1 = stringtobytearray(num1); b2 = stringtobytearray(num2); else if (result = -1) b1 = stringtobytearray(num2); b2 = stringtobytearray(num1); else return “0“; / 保证 b1 数组 b2 数组 for (int i = 0; i b2 数组, 最高位不可能再借位，因此不会数组越界 stringbuilder sb = new stringbuilder(); for (int i = b1.length - 1; i = 0; i-) if (b1i != 0) / 从第一个不为 0 的数字开始记录进字符串 for (; i = 0; i-) sb.append(b1i); if (sb.length() = 0) return “0“; if (result = 1) return sb.tostring(); else return “-“ + sb.tostring(); else if (num1.startswith(“-“) else if (!num1.startswith(“-“) else if (num1.startswith(“-“) else throw new numberexception(“unexcepted here“); /* * param num1 * param num2 * return 返回两个数相乘后的结果 * throws exception * 如果 num1 或 num2 中出现非数字， 则抛出 numberexception 异常 */ public string mul(string num1, string num2) throws numberexception int res; if (!num1.startswith(“-“) else if (num1.startswith(“-“) res = -1; 26 else if (!num1.startswith(“-“) res = -1; else if (num1.startswith(“-“) num2 = num2.substring(1); res = 1; else throw new numberexception(“unexcepted here“); byte b1; byte b2; int result = num1biggerthannum2(num1, num2); if (result = 1) b1 = stringtobytearray(num1); b2 = stringtobytearray(num2); else b1 = stringtobytearray(num2); b2 = stringtobytearray(num1); byte b3 = new byteb1.length; for (int i = 0; i = 10) / b4 数组被影响的部分进位 b4k + i -= 10; b4k + i + 1+; stringbuilder sb = new stringbuilder(); for (int i = b4.length - 1; i = 0; i-) if (b4i != 0) / 从第一个不为 0 的数字开始记录进字符串 for (; i = 0; i-) sb.append(b4i); 27 if (sb.length() = 0) return “0“; if (res = 1) return sb.tostring(); else return “-“ + sb.tostring(); private byte stringtobytearray(string str) throws numberexception int len = str.length(); byte bs = new bytelen; for (int i = 0; i 57 | c = 0; i-) while (del(b1, b2, i) /