你的位置：论文发表网 >> 论文库 >> 工学论文 >> 详细内容在线投稿

模拟人工手算的方法实现任意位大整数的四则运算

收藏打印发给朋友发布者：周清松

热度0票浏览67118次时间：2015年4月20日 17:16

周清松普洱学院理工学院云南普洱 665000

基金：云南省教育厅科学研究基金项目（2013Y107）

【文章摘要】

用模拟人工手算的方法，很好的解决了大整数运算的问题，从而实现大整数运算时不受长度的限制。通过分析比较，发现用整型数组作为存储结构虽简单易行，但这种存储方式浪费空间，而采用字符串来处理，对算法设计及空间利用率都是很好的选择。

【关键词】

大整数；算法模拟

0 引言

随着社会经济和高端科学的发展，超大数理级的处理也越来越多的应用的社会生活的各个领域。比如在国家经济生活中，决策者们需要通过收集，处理，统计和分析工农业中有关的数据。从而得到精确的结果。借以指导下一步的社会经济发展。在航空领域，科技工作者们更要处理大量的数据，其中不乏一些超大的数据或超高精度的数据，整个处理过程不能有丝毫的马虎。在密码领域，如果能采用超大的数据进行算法设计，对社会保密工作将会有一个极大的提升。因此，大整数的处理是研究计算机数字处理的重要问题之一，所谓的大整数，是指超过目前各编译器所定义的最高精度的整型数。目前计算机所标称的有效数值范围仍是依据计算机的字长规定的，像现在的pentium64 位超过了20 位的有效数字就不能完整表示了。

1 问题分析

如果要完成大整数的四则运算，首先要解决的问题是如何存储运算数的问题，其次是设计算法实现运算的过程。

1.1 超大数存储技术

1.1.1 整型数组存储

采用数组这种常用存储方式进行如下处理，将输入的数据拆成单个的字符，并将该字符存放在整型数组的一个单元中，然后进行相关的运算，如图1 所示：

采用这种方式存储，对存储数据的任何一位的数据的访问、修改都非常方便，但是，空间利用率非常低，存储0~9 之间的一个数最多占用4 个位，而在vc++ 中任一个整型占四个字节，即是32 个位，可见空间的利用率最多才到1/8。这样一来，虽然算法设计过程简单而可行，但是空间付出了大量的代价，况且数组的大小是一个静态值，对空间的支配没有自由。

1.1.2 链式存储

链表是可以动态使用存储空间的一种存储方式，为了有效利用空间，我们定义数据类型是char 型的链表结点，以字符单链表的形式存放要处理的大整数的各位上数值。但是我们都知道，单链表的操作中对于随机访问链表中的数据和寻找链表的前驱结点要花费大量的时间，而且链表中每个结点存放’0’~’9’之间的一个字符，则至少浪费了半个字节加上一个指针的空间，利用率小于25%。所以空间上虽然有节省，但是总体效率还是很不好。

1.1.3 字符串存储

将每个大整数看成一个字符串，采用字符数组的方式存储这些字符串，每个数组元素仍然存放一个数据字符，空间利用率比整型数组大得多，可以发现利用率在12.5%~50% 之间，而且由于是顺序存储，对于数据的访问、找前驱、后继等操作能够在短时间完成

综上所分析：字符串存储无论在算法设计还是在空间利用上都比较好，所以我们采用了第三种方式，即字符串方式实现存储。

1.2 运算方法设计

1.2.1 符号处理

(1) 本算法用字符串的长度带符号标识数据的正负性，比如－ 99999 ，在0 ～ 9 之间

的字符个数是5，则用Len ＝－ 5 同时标识数据－ 99999 的长度与正负性。

(2) 算法中先将符号处理，后调用函数对数据进行处理，下面是对符号进行处理的情况：

A、如果加法中两个数异号，则调用减法；如果两个数同号，调用加法函数，结果为负数则在结果前添上“－”。

B、如果减法中两个数异号，则调用加法，结果与被减数同号；如果两个数同号，则调用减法。当同为正时，如果被减数大，则用被减数减去减数，否则用减数减去被减数，结果前添上“－”；当同为负数时，当被减数绝对值比减数的大时，则则用被减数减去减数，结果前添上“－”，否则用减数减去被减数。

C、如果乘除法中两数异号，则结果为负；如果两数同号，则结果为正。除法中，余数符号和被除数保持一致。

1.2.2 数据处理

本算法主要涉及四则运算的加、减、乘、除。

加法：从个位开始（从右至左），将加数和被加数长度相同的部分，带进位（有进位为1，无进位为0）按位相加，并将结果按从左至右的顺序存放；如果被加数（加数）较长，则先用比加数（被加数）长的部分加上最后一次的进位，然后从右至左的顺序依次复制到开始时所得结果的后面。最后，调用翻转函数，使结果按从高位到低位的顺序输出。

减法：先将被减数和减数长度相同的部分进行带借位相减（有借位为1，无借位为0），并将结果按从左至右存放；然后，将被减数比减数长的部分减去借位，并将其从右至左的顺序依次复制到开始时所得结果的后面。最后，调用翻转函数和去零函数（去掉高位的0），使结果按从高位到低位的顺序输出。

乘法：A、将乘数进行按位分解；

B、调用一个多位数乘以一位数的函数。如果是乘的个位的话，就不用在乘积后面加0 ；否则，如果乘的是十位上的数，则在结果后添一个0 ；如果是百位上的数，则在结果后添两个0．．．．．．

C、将结果累加；

D、重复B 和C 的操作，直到乘数长度为0。

除法：如果除数为0，给出提示”除数不能为0 ！”并跳出程序，让用户再次输入；

如果被除数比除数小，则商为0，并将被除数作为余数；否则：

A、取数：即从被除数中取出长度与除数长度相同的数。

B、分析：如果被取出的数比除数大或等，则用除数与j （1<j<11）相乘，若被除数小于除数与j 的乘积且大于除数与j-1 的乘积，则商j-1。

如果被取出的数比除数小，则商0 且从被除数中再取一位，然后重复A 的操作。

C、重复A 和B 的操作，直到被除数长度为0。

图 1

2 算法分析

加法：在平时的计算机运算中，当数据超过一定长度，机器会自动进行取余，从而得不到想要的数，比如说，c 语言中的unsigned int 型，他的取值范围是0~65535，如果用65535+1，你将得不到65536，而是得到（65535+1）%65536=0。所以在此要另找新的途径。在加法中最难解决的是进位处理问题及如果进行加法运算，我们参照了归并排序的思想，先把长度为L1（加数与被加数中较短长度）对应位相加，然后对剩余位n-L1 位进行进位处理，在此过程中我们用到了2 个字符串，所以时间与空间复杂度均为O（n）级，可见此方法是可行的。

减法：减法与加法类似，时间与空间复杂度均为O（n）级。

乘法：假设被乘数的长度为n，乘数的长度为m。在算法中，我们将乘数分解为单个字符并与被乘数相乘，并进行m 和的累加，所以实现过程中用了两重循环，其时间复杂度为O（m*n）级，空间复杂度为O（m+n）级。

除法：每次取出与除数长度相等或比除数长度大1 的位数进行运算，其中调用了减法，在减法中又调用了乘法的子函数，所以时间复杂度为O（m*n2）

3 算法实现

由于实现大整数的四则运算是借助VC++ 软件设计平台，因此下面对四则运算的实现过程采用C++ 进行描述

3.1 加法实现过程

功能：将str1 和str2 相加，返回结果存在str 中。其中，for 循环用来对两个数长度相等的部分进行按位相加，表达式： str+=(str1[i]+str2[j]+c-96)%10+'0' 表示把str1[i] 与str2[i] 相加后所得的字符存放于str 中；c=(str1[i]+str2[j]+c-96)/10 表示取得这次的进位。while 循环用来带进位（没有进位则为0）处理较长数的剩余部分。最后，如果仍有进位，则用表达式str+= c + '0' 存放到str 中。因为以上所得的结果是逆序的，所以调用翻转函数reverseStr( ) 即可得正确的结果。

核心代码如下：

for(i=str1.size()-1,j=str2.size()- 1;i>=0&&j>=0;i--,j--)

{

s t r + = ( s t r 1 [ i ] + s t r 2 [ j ] +c-96)%10+'0';

c=(str1[i]+str2[j]+c-96)/10;

}

while(i>=0&&j<0)

{

str+=(str1[i]+c-48)%10+'0';

c=(str1[i]+c-48)/10;

i--;

}

while(j>=0&&i<0)

{

str+=(str2[j]+c-48)%10+'0';

c=(str2[j]+c-48)/10;

j--;

}

if ( c > 0 )

str+= c + '0';

reverseStr(str);

3.2 减法实现过程

功能：将较大数str1 与较小数str2 进行相减，结果存放在str 中。其中，For 循环用来对str1 与str2 长度相等的部分按低位到高位相减。若str1[i] 的相应位减去借位位以后仍然比str2[i] 大，则不需要进行借位。此时用表达式str+=(str1[i]- str2[j]-c)%10+'0' 把求得相减后的第i 位上的字符放在str 中，置c=0 表示没有借位；若str1[i] 减去借位位后比str2[i] 小，则需要借位，表达式str+=(str1[i]- str2[j]+10-c)%10+'0' 表示把借位后求得第i 位的字符存于str 中，置c=1 表示有借位，如此反复循环进行。while 循环的作用是减完str2 后，对str1 剩余部分进行带借位处理，其原理与for 循环相似。按照上面的算法我们得到的字符有两处需要处理：a、我们得到的字符串是逆序的，需要用翻转函数reverseStr( ) 进行处理。b、相减后可能高位存在0，这种情况需要调用deletezore（）进行处理。

核心代码如下：

f o r ( i = s t r 1 . s i z e ( ) - 1 , j = s t r 2 . s i z e ( ) - 1;j>=0;i--,j--)

{

if(str1[i]-c>=str2[j])

{

str+=(str1[i]-str2[j]-c)%10+'0';

c=0;

}

else

{

str+=(str1[i]-str2[j]+10-c)%10+'0';

c=1;

}

while(i>=0)

{

if(str1[i]-c>='0')

{

str+=str1[i]-c;

c=0;

}

else

{

str+=str1[i]+10-c;

c=1;

}

i--;

}

reverseStr(str);

str = deleteZero(str);

3.3 乘法实现过程

在乘法的实现过程中用到了v o i d c t o d ( s t r i n g &s t r , i n t a [ ] ) 、s t r i n g multiply1(string& str, int n) 函数，先介绍这两个函数。ctod(string &str,int a[]) ：其功能是将字符串转换成整型数组。str 存放被转换的字符串Int a[] 存放转换后的整型数组。string multiply1(string& str, int n) ：其功能是用str 种的字符转换成整型数，然后乘以n。rst 存放结果。

核心代码：

for (int i = str.size()-1; i >= 0; --i)// 从str 的右边第一位开始乘n

{

rst+=((str[i]-'0')*n +c)%10 + '0';// 取得乘积的个位数

c =((str[i]-'0')*n+c)/ 10;// 取得乘积的进位位

}

if ( c > 0 )// 如果最后有进位位，将其转换成字符型

rst += c + '0';

reverseStr(rst);// 将结果从高到低换位

功能：用str1 存放被乘数，str2 存放乘数，rst1 保存被乘数与乘数每一位的乘积，rst2 用于累加rst1 的累加和，调用ctod 函数将str2 字符串转换成整型数组放在int b[6000] 中，b[0] 用于存放数组b[6000] 的长度。在处理的时候是从b[6000] 的最后一个元素b[b[0]] 开始逆序处理。由于个位数与被乘数相乘不需要在后面补0，故单独处理， rst2=multiply1(str1,b[b[0]])。其他位上的数则调用rst1=multiply1(string& str, int n)，并做若干次rst1+=‘0’操作（如果n 是十位上的数则rst1 后加一个0，若是百位上的数则加两0….）。累加每次所得的乘积， rst2= add(rst1,rst2)。由于乘积最后结果的高位可能为0，所以调用deletezero（）函数去除高位的0。

核心代码：

　　ctod(str2,b);// 将字符串转换成整型数据

　　rst2=multiply1(str1,b[b[0]]);// 由于个位与str1 相乘不需乘10，所以就单独处理

　　for(i=b[0]-1;i>=1;i--)//str1 依次与b 中的每个数相乘

　　{

　rst1="";// 每次都清空

　 rst1=multiply1(str1,b[i]);

　for(j=1;j<=b[0]-i;j++)// 将高位乘10

　rst1+='0';

rst2=add(rst1,rst2); // 累加每次的结果

　}

　rst2=deleteZero(rst2);// 去除起始的0

3.4 除法实现过程

功能：用str1 除以str2, 商存放在rst 中，余数存放在str 中。当str1 比str2 小时，则商为0，余数等于被除数；否则，使用For 循环和while 循环来实现：For 循环用来从被除数中按高位到低位的顺序取出和除数长度相等的部分，同时将i 递增到除数的长度。while 循环是将取出的部分与除数相除，并再从被除数中取一位，同时将i 加上1，直到i 比被除数长度大时结束。其中，如果取出的数比被除数大，则通过让j 从10 递减到2，比较str 与multiply1(str2,j) 的大小和str 与multiply1(str2,j-1) 的大小，当str 在二者之间，则此次商j-1 ；否则，商0。对于rst 和str 分别调用deletezore（）处理高位上的0，即可得最终结果。