大数运算实现的相关技术研究

余发高，胡 鸣

(武汉纺织大学 数学与计算机学院，湖北 武汉 430200)

大数运算目前在信息安全、数字图像、大数据挖掘等领域应用比较广泛，甚至在研究星体计算中需要精确到小数点指定位数，将误差降低到最小。目前JAVA在大数运算方面做了一些相关的研究，但在算法上还需要进一步的优化。本文针对C语言在大数运算方面提出了大数运算模型以及大数运算算法，与JAVA大数加减乘除相比较，大数加法和减法在计算效率上要更快；大数乘法速度是JAVA计算的2到3倍；大数除法能保留小数点9位数。

1 大数计算的设计

1.1 大数计算框架

提出了DLNC（Design of Large Number Computing）模型（见图1），通过此模型当输入数据存储超过了字长时，动态调整字长来存储；当存储没有操出字长就不需要调整。然后参与计算，计算结果存储过程中，如果检测出超出字长，再次调整字长，最后存储结果，然后进行输出结果。此模型主要为解决大数计算而提出，在输入过程中如果超出了存储的字长，就来动态的增加字长；在计算结果存储过程中如果超出了字长，用同样的方法来增加字长进行存储，从而突破了普通计算字长的限制，能够实现大数基本的计算。

图1 大数计算框架图

1.2 大数计算数表示的的几种方法

（1）存放大数可以采取用链表形式来存贮的，由于要在计算中会用到从高位开始计算以及从低位开始计算数值的两种情况，所以我们将链表定义为双向链表，其中一个指向后的数据，另一个指向一个单元来存储数据，一个指针指向前方的数据。

（2）在计算机中，数的表示可以分为两种，一种是用二进制来表示，一种是用十进制来表示。用长为len的short型数组或者long型数组甚至longlong数组来表示大数，可以采用权从大到小的顺序来存放，大数表示的形式如下：

也可以用十进制的方式来表示大数如下：

（3）大数的表示也可以用大尾序或者小尾序的方式。大尾序就是低位字节排放在内存的高端，高位字节排放在内存的低端；小尾序就是高位字节排放在内存的高端，低位字节排放在内存的低端。

（4）用不完全精度的方法来表示大数。有时计算的结果需要精确到有限的位数，没必要全部计算出来，这样可以节省计算的时间。不完全精度的方法来表示大数，除了用数组来存储有限数值外，还需要一个数来表示有效数字的权值。

（5）定义结构体成员部分来表示大数，包含以下几个部分：整数部分的位数以及浮点部分的位数，要定义字符数组表示为整数部分以及字符数组表示为浮点部分，幵且要定义表示整型和浮点数字符型数组大小，可以根据需要自行修改宏定义里面的内容，以修改数组大小。幵且要定义字符型数据的符号位，还要定义字符型表示无穷，对计算错误可以做一些函数内部处理。

（6）可以使用多个或者多维数组的方法以及字符串形式来表示大数。

（7）多精度利用固定精度数据类型创建和操纵能够表示大数的多精度整数。

1.3 大数计算处理溢出的方法

（1）在实际分配内存空间时，对数据的输入与输出可以动态的调整字符数组或者字符串的长度来突破字长的限制，从而可以解决大数数据溢出的问题。

（2）以字符串形式来存储大数，通过单个的字符得到对应的十进制数，从而可以进行计算。

（3）在java中一个类BigInteger表示大整数类，另一个类BigDecimal表示大浮点数类，理论上能够表示无限大的数，只要计算机内存足够大。

上面的方法都是用软件的方法来解决大数溢出的相关问题，但是如果我们从硬件的角度来考虑的话，也就是要提高硬件的设备，我们可以采用64位或者128位甚至更高位的字长的计算机来解决堆栈溢出和计数器溢出的相关问题，但是目前来说，生产的成本以及技术的成本过高，现阶段可能无法实现，但是随着计算机的发展，大数据的兴起，到那时这些问题都将迎刃而解，但这里还是从软件方面来考虑如何解决大数溢出的根本问题。

2 大数基本运算设计

2.1 大数加法和减法的运算设计

这里首先提出ADLNO（Algorithmic Design of Large Number Operation）大数运算算法设计模型，这个模型适用于大数加法、大数减法、大数除法、大数乘法的运算。大数加法运算是相对简单的一种算法，实质就是选择两个整数位数较长的那个数字作为加法运算的循环变量，从整数的最低位开始计算起，把两个操作数根据其相对应位置的数字进行加法操作，然后加上前一位的进位，判断此时是否会向前一位进位，如有进位，则把进位值赋予1（进位制不可能是1以上的数字，因为对应位置的数相加大小不会超过20），此时如果存在进位，将得到的对应位置的和除以10（因为是十进制的加法计算）进行取整，就会得到本位应该输出的和了。否则，没有进位的情况，则将得到的对应位置的和同样除以 10进行取余数，就会得到本位应该输出的和了。循环上面的操作直至最高位，即得到最后的结果。大数的减法，因为使用了结构体对操作数进行了数字存储，也会和之前一样分割大数的整数部分和小数部分。在处理整数部分的减法时，也是从两个操作数的低位开始计算起，判断两个操作数的关系，看看两个操作数的长度，如果两个操作数相等则直接返回结果 0，如果两个操作数不等，继续比较两个数的长度。如果被减数的位数长度大于减数的位数长度，则正常的用被减数减去减数得到差。如果减数的位数长度大于被减数的位数长度，则用减数减去被减数，最后得到的差加上负号。在每一项相减时，需要注意每一位的借位。如果前一位有借位，计算本位时应该减去结尾，没有借位则直接减，再去判段本位是否需要借位，如果需要借位，则将借位置于1，否则置为0。之后就是不断地重复循环以上步骤，直至见到最高位得到最后的差。在处理小数部分和整数部分基本相同，只需从低位减到高位，其他步骤与整数部分一致。

有关小数部分的加法减法运算，则与整数加法减法运算相类似。以小数位数较长的部分作为循环变量，从低位向高位不断地一位一位循环向前加，得到最终结果。由于加法和减法算法类似，下面是加法伪代码部分：

2.2 大数乘法的运算设计

关于大数乘法的思路，首先大数乘法同样是从操作数的低位开始计算起，用一个数的所有位去乘上另一个数的最低位，得到结果再继续向前进一位，进行计算另外一个数的前一位与第一个操作数的所有位相乘。通过这样反复循环，重复计算到至高位，把它们加起来就是最后乘法的积了。这里因为每一次的乘法都会用到一个结构体变量对这个临时的积进行存储，如果位数比较多，就需要大量的结构体变量用了进行存储这些临时的变量。为了减少开销，我们先将一个临时变量存在一个结构体变量中，把这个临时变量与下个临时变量相加存在另外一个结构体变量中，后面的临时变量再与这个相加时，再存到第一个结构体中，这样反复存储计算实际上只使用了两个结构体变量进行存储数据，大大减少了对空间的开销。

2.3 大数除法的运算设计

当被除数除不了时候，需要被除数补零直至能除除数，也要除到规定的小数位数。从高位向低位减，做减时以被除数长度为单位，从高位取出大于被除数的字符串（被除数），然后将原除数乘以一个权值（小于10）得到一个不大于被除数的新的被除数，再用被除数减去新的除数，这个权值就是结果，余数从剩下的被除数高位再取出几位做补位，这样循环此步操作，直到对应小数返回为止。进行浮点数除法运算时，需要转化为整数除，得到结果后再回归小数点。

3 性能分析与实验

3.1 加法和减法运算的性能分析

图2 大数加法示意图

从图2可以看出，对于c大数加法从16位，32位，64位，128位，256位，512位与java大数加法从16位，32位，64位，128位，256位，512位相比较，c大数加法用的时间显然要少，但是从1024位开始，一直到8192位，相同的大数，c用的时间要比java用的时间多。可以看出1024位是c和java大数加法的速度快慢的一个转折点。从而可以得出，c在计算1024位大数的加法优势挺明显，但要计算1024位以上的大数加法却远不如java速度。由于大数减法算法和加法算法类似，通过实验得出和加法类似的结论。

3.2 乘法运算的性能分析

图3 大数乘法示意图

从图3可以看出，无论c从16一直取到1024位，再从1024位取到8192位，同样的数据所用的时间一直远小于java所用的时间，从上面的图表可以看出：从16位，32位，64位，c所用的时间是java所用的时间的二分之一；同样的128位大数，java用的时间大约是c用的时间的3倍，当256位大数时，java用的时间是c用的时间的5倍；当512位大数时，java用的时间是c用的时间的9倍多；当1024位大数时，java用的时间是c用的时间的9倍多；当2048位大数时，java用的时间是c用的时间的8倍多；当4096位大数时，java用的时间是c用的时间的6倍多；当8192位大数时，java用的时间是c用的时间的5倍多；从上面的数据分析可以看出，从16位大数，一直到1024位大数，java所用的时间在成倍数的增加，也就是c所用的时间成倍缩小；从1024位一直到8192位java所用的时间在成倍数减小，也就是c所用的时间成倍数增加。综上所述c大数乘法从16位一直到8192位所用的时间和java所用的时间相比较，一直很少，也就是说c在大数乘法上，速度一直比java要快的多。

3.3 除法运算的性能分析

本文基于C语言大数除法构造函数时，通过自己构造函数，以及设计除法的算法，通过计算可以获得除法的结果，幵且能保留小数点9位数值，但通过java计算除法时，发现java除法是取商的，也就是无法取到小数点，由于计算结果的不同，c语言大数除法无法和java大数除法在时间上进行比较。但通过实验我们发现，c语言构造的大数除法函数能够计算出结果，幵且能够保留小数点后面的9位数值，当然对于大数的运算能够根据实际需要设置小数点后面的数值也是今后的研究中需要改进的，但目前能够精确到小数点9位数值。

4 总结

本次所设计c语言大数运算加法、减法、乘法、除法的函数以及算法，总体就是通过模拟笔算的过程来实现的大数运算，同时通过设计时间函数与对应的java大数运算进行比较，C语言在大数加法和减法计算过程要比java大数加法和减法要慢，乘法计算的速度要比java快的很多，除法能够计算出结果幵且能保留小数点9位数字。