《大整数运算C语言实现C语言大作业报告+源码.doc》由会员分享，可在线阅读，更多相关《大整数运算C语言实现C语言大作业报告+源码.doc（33页珍藏版）》请在三一办公上搜索。
1、一、设计高精度无符号大整数计算（以1为存储单位）1.1需求陈述对数值很大、精度很高的数进行高精度大整数计算是一类十分常见的问题。但由于C语言中数据类型受数据长度和范围限制，普通数学计算很难实现此类问题，为尝试解决这个问题，专门设计一个C语言程序用于无符号大整数的计算，实现无符号大整数的一般计算和比较功能。1.2需求分析1.2.1功能分析表1 程序功能分析项目功能 分析BigN数据接收以字符串形式接受反转字符串函数Invert()用Translate()将字符串翻译为整形数组数据运算分别用BigN_cmp_low()和BigN_cmp_High()对数据进行比较/从a1对数组进行比较，传入两个数
2、组及其大小以及需要从第几位开始比较int BigN_cmp_High(int *, int *, int , int );/从an对数组进行比较，传入两个数组及其大小加法BigN_Add()减法BigN_Min()低位减法BigN_Min_low()，在未反转的情况下计算乘法BigN_Mul()除法BigN_Div()运算辅助函数反转整形数组InvertInt()从前面删减多余的零Del_zero_low()从末尾删减多余的零Del_zero_High()获取两个数的最大值Get_MAX()1.2.2数据分析该程序可用于计算无符号大整形数据计算，最多可计算长度为200位（即10的200次方大小
3、）的数据，但在原代码中可以随数据需求改变最大长度。该程序中所有运算和比较均考虑到了输入前导0（例0001）的情况。由于数据类型限制，该程序未加入小数计算和负数计算，除法结果中只分别计算商和余数。1.2.3技术约束本程序已在code blocks下编译通过。1.3总体设计1.3.1全局数据结构 本程序中数据采取以个位数字为单位存入整形数组，在数据计算和比较中对单个数组单元进行操作。采用整形数组存储，主要优点为可以在该程序的基础上进行改进，使字符串中每四个数字或更多存入一个数组单元中（如程序二）。1.3.2函数设计A数据的接收1反转字符串函数 Invert()函数原型：void Invert (c
4、har * , int );功能： 反转字符串，传入字符串首地址和长度 在加法、减法、乘法计算中必须先对字符串进行反转，是字符串整体逆转，但不改变字符串长度。 2. 翻译字符串函数 Translate()函数原型：void Translate (char *, int *, int *);功能：将字符串翻译为数组，传入字符串和数组及数组大小的地址B. 数据运算 1. 比较函数 BigN_cmp_low()和BigN_cmp_High()函数原型：int BigN_cmp_low (int *, int *, int , int , int ); 和int BigN_cmp_High(int *
5、, int *, int , int );功能：对整形数组分别进行地位和高位比较，即从开头和结尾开始进行比较。实现步骤：先将数组中不必要的零去掉，然后记下位数，对位数进行比较，最后从原始数据最高位进行比较，逐步往下比较，若前面小于后面，则返回值为1,；若后面小于前面，则返回-1；若相等，则返回值为0.2. 加法BigN_Add()函数原型：void BigN_Add (int *, int *, int , int *);功能：高精度加法，传入反转后的数组及其大小的最大值，和结果数组的首地址。实现步骤：依次将所需计算的两个数组及其位数的最大值传入函数，对两个函数每一位进行加法存入结果中，对满十
6、的结果进行进位，然后对该位进行对十取余存入结果。实现代码：for(i = 1; i = max; i+) resi += num1i + num2i; resi+1 += resi / 10; resi %= 10; 3. 减法BigN_Min()和低位减法BigN_Min_low()函数原型：void BigN_Min (int *, int *, int , int *); void BigN_Min_low(int *, int *, int , int , int *);功能: 高精度减法，传入反转后的数组及其大小的最大值，和结果数组的首地址。 高精度低位减法，传入未反转的数组及其大小
7、的最大值，和结果数组的首地址。实现步骤：依次将所需计算的两个数组及其位数的最大值传入函数，对两个函数每一位进行减法存入结果中，对减不着的进行借位，然后对该为进行对十取余存入结果。实现代码：for(i = 1; i = num2i) resi += num1i - num2i; else resi += num1i + 10 - num2i; num1i+1 -= 1; 4. 乘法BigN_Mul()函数原型：void BigN_Mul (int *, int *, int , int , int *);功能：高精度乘法，传入反转后的数组及其大小，和结果数组的首地址。实现步骤：对两个函数的每一位
8、进行乘法，然后对于大于10的结果进行进位操作。由于该程序中所有数组均从1开始存，故运算结果从2开始存。实现代码：for(i = 1;i = bit1; i+) for(j = 1;j = bit2; j+) resi+j += num1i * num2j; resi+j+1 += resi+j / 10; resi+j %= 10; 5. 除法BigN_Div()函数原型：void BigN_Div (int *, int *, int , int , int *, int *, int *, int *);功能：高精度除法，传入未反转的数组及其大小、商的首地址、余数的首地址、商的位数、余数的
9、位数.实现步骤：将未经反转的数组传入，从0开始做个操作，循环利用比较和减法，若余数大于除数，则进行减法调用，此处用到的减法为低位减法.实现代码：*res_bit = 1; for(i = 1;i 0)/modnum2时,为真 (*bit_mod)+; mod*bit_mod = num1i;/将num1逐个复制给mod while(BigN_cmp_low(mod,num2,*bit_mod,bit2,1) num2 for(j = 1;j = (*bit_mod); j+) tempj = 0;/每次将余数的结果置为 0 BigN_Min_low(mod,num2,(*bit_mod),bi
10、t2,temp); (res*res_bit)+; for(j = 1;j = (*bit_mod);j+) modj = 0;/mod 置零 Del_zero_low(temp,bit_mod);/对 mod 低位去零，防止如“001”的结果 for(j = 1; jb?a:b;1.4设计思想说明该程序中所有大整型无符号数据的运算均采用模拟手算的方法，对单个数字进行操作，以实现大整型运算。为程序运行更加高效，调用函数过程中传输多个参数，若将该程序作为模板，则可省略其中某些参数，使调用更方便。1.5测试结果说明主界面： 测试加法： 图一 图二测试减法： 图一 图二测试乘法： 图一 图二 图三测
11、试除法： 图一 图二 图三 图四测试比较:(可采用程序二中的Del_zero_Str ()函数进行对多余0的删减)图一 图二注：以上数据均为程序在Code Blocks 的写入文本的运行结果，且该结果都通过了验证。1.6 完整代码详见程序文件BigN.c。 二、设计高精度无符号大整数计算（以10000为存储单位） 注：由于本程序在前一程序基础上建立，故本程序主要介绍与前一程序的不同。2.1需求陈述对数值更大、精度更高的数进行高精度大整数计算是基于上一程序的又一问题。但由于C语言中数据类型受数据长度和范围限制，前一程序很难实现更高位的运算，为尝试解决这个问题，在前一程序的基础上对无符号大整数的计
12、算进行了改进实现无符号大整数的一般计算和比较功能。而且改进后的程序运行更为高效。2.2需求分析2.2.1功能分析表1 程序功能分析项目功能 分析WanBigN数据接收用Wan_TransGT ()将字符串翻译为整形数组运算辅助函数传入整形n，计算10的n次方 IntPow_ten ()从前面删减对字符串多余的0Del_zero_Str ()不再使用从末尾删减多余的零Del_zero_High()注：由于以万为存储单位的程序对除法的计算效率过低，故不采用除法。2.2.2数据分析该程序可用于计算无符号大整形数据计算，最多可计算长度为200位（即10000的200次方大小）的数据，但在原代码中可以随
13、数据需求改变最大长度。该程序中所有运算和比较均考虑到了输入前导0（例0001）的情况。由于数据类型限制，该程序未加入小数计算和负数计算。2.2.3技术约束本程序已在code blocks下编译通过。2.3总体设计2.3.1全局数据结构 本程序中数据采取以10000为单位存入整形数组，在数据计算和比较中对单个数组单元进行操作。2.3.2函数设计A数据的接收1反转字符串函数 Invert()同上。 2. 翻译字符串函数 Wan_TransGT ()函数原型：void Wan_TransGT(char *str,int *num, int *bit)功能：将字符串翻译为数组，传入字符串和数组及数组大
14、小的地址实现代码：if(strlen(str)%4 != 0) for(i = 0; i (strlen(str)/4+1)*4; i+) if(i%4=0) (*bit)+; if(stri != 0) num*bit += (stri-0) * IntPow_ten(i%4); else for(i = 0; i strlen(str); i+) if(i%4=0) (*bit)+; if(stri != 0) num*bit += (stri-0) * IntPow_ten(i%4); B. 数据运算 1. 比较函数 BigN_cmp_low()和BigN_cmp_High()同上.2.
15、 加法BigN_Add()函数原型：void BigN_Add (int *, int *, int , int *);功能：高精度加法，传入反转后的数组及其大小的最大值，和结果数组的首地址。实现步骤：依次将所需计算的两个数组及其位数的最大值传入函数，对两个函数每一位进行加法存入结果中，对满10000的结果进行进位，然后对该位进行对10000取余存入结果。实现代码：for(i = 1; i = max; i+) resi += num1i + num2i; resi+1 += resi / 10000; resi %= 10000; 3. 减法BigN_Min()和低位减法BigN_Min_l
16、ow()函数原型：void BigN_Min (int *, int *, int , int *);功能: 高精度减法，传入反转后的数组及其大小的最大值，和结果数组的首地址。实现步骤：依次将所需计算的两个数组及其位数的最大值传入函数，对两个函数每一位进行减法存入结果中，对减不着的进行借位，然后对该为进行对十取余存入结果。实现代码：for(i = 1; i = num2i) resi += num1i - num2i; else resi += num1i + 10000 - num2i; num1i+1 -= 1; 4. 乘法BigN_Mul()函数原型：void BigN_Mul (int
17、 *, int *, int , int , int *);功能：高精度乘法，传入反转后的数组及其大小，和结果数组的首地址。实现步骤：对两个函数的每一位进行乘法，然后对于大于10000的结果进行进位操作。由于该程序中所有数组均从1开始存，故运算结果从2开始存。实现代码：for(i = 1;i = bit1; i+) for(j = 1;j = bit2; j+) resi+j += num1i * num2j; resi+j+1 += resi+j / 10000; resi+j %= 10000; 5. 除法BigN_Div()函数原型：void BigN_Div (int *, int *
18、, int , int , int *, int *, int *, int *);功能：高精度除法，传入未反转的数组及其大小、商的首地址、余数的首地址、商的位数、余数的位数.实现步骤：将未经反转的数组传入，从0开始做个操作，循环利用比较和减法，若余数大于除数，则进行减法调用，此处用到的减法为低位减法.C. 运算辅助函数1.反转整形数组InvertInt()同上。2.删减多余的零Del_zero_str()函数原型：void Del_zero_str (char *);功能：从str1开始去零，结果为去零后的字符串；用于比较两个数的大小时被调用。3.获取两个数的最大值Get_MAX()同上。2
19、.4设计思想说明该程序中所有大整型无符号数据的运算均采用模拟手算的方法，对单个四位数字进行操作，以实现大整型运算。为程序运行更加高效，调用函数过程中传输多个参数，若将该程序作为模板，则可省略其中某些参数，使调用更方便。2.5测试结果说明 主界面截图测试加法： 图一 图二测试减法： 图一 图二测试乘法： 图一 图二测试除法：测试比较:注：以上数据均为程序在Code Blocks 环境下的运行结果，且该结果都通过了验证。2.6完整代码详见程序文件WanBigN.c。 三、性能比较 说明：该部分主要通过及时函数对两个程序的性能进行了比较，其中的计算时间为在纯计算时间（不包含输入用时）的基础上，空循环
20、10 的 8 次方次所测时间。只比较了加法和除法。下面截图为多次测试后选取的截图。加法：程序一：程序二：除法:程序一：程序二：结论： 通过多次比较，程序二优于程序一，运行时间上略短，且运算支持数据更大。源码：/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Name： 无符号大整型数据运算和比较（1） * * Introduct: C语言程序设计基础大作业 * * Thought： 用模拟手算的算法对大整形无符号数据进行基本计算和比较（
21、+，-，*，/）， * * 采用整形数组存储，以 1 为单位进行运算。 * * Date： 2010/12/29 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */#include#include#include#define MAX 200#define MAX_Res 50000int Get_MAX (int , int );/获取两个数的最大值，返回值为大的那个数void Invert (char *, int );/反转字符串，
22、传入字符串首地址和长度void InvertInt (int *, int );/反转数组，传入数组首地址和大小void Del_zero_low (int *, int *);/从a1开始去零，结果为去零后的数组及其大小void Del_zero_High(int *, int *);/从an开始去零，结果为去零后的数组及其大小void Translate (char *, int *, int *);/将字符串翻译为数组，传入字符串和数组及数组大小的地址int BigN_cmp_low (int *, int *, int , int , int );/从a1对数组进行比较，传入两个数组及
23、其大小以及需要从第几位开始比较int BigN_cmp_High(int *, int *, int , int );/从an对数组进行比较，传入两个数组及其大小void BigN_Add (int *, int *, int , int *);/高精度加法，传入反转后的数组及其大小的最大值，和结果数组的首地址void BigN_Min (int *, int *, int , int *);/高精度减法，传入反转后的数组及其大小的最大值，和结果数组的首地址void BigN_Min_low (int *, int *, int , int , int *);/高精度减法，传入未反转的数组及其
24、大小，和结果数组的首地址void BigN_Mul (int *, int *, int , int , int *);/高精度乘法，传入反转后的数组及其大小，和结果数组的首地址void BigN_Div (int *, int *, int , int , int *, int *, int *, int *);/高精度除法，传入未反转的数组及其大小、商的首地址、余数的首地址、商的位数、余数的位数int main() char str1MAX = 0, str2MAX = 0, ch;/用字符串接收输入 while(1) int num1MAX = 0, num2MAX = 0, resMA
25、X_Res = 0, modMAX = 0;/num以数组的形势存数，res存结果,mod存余数 int i = 0, bit1 = 0, bit2 = 0, res_bit = 0, max = 0, bit_min = 0, res_cmp = 0,div_bit_mod = 0; /bit_min控制输出时的最低位，因为num从1开始存，乘法中结果从2开始存 printf(nWhich operation do you want to do ?n 1 A+Bn 2 A-Bn 3 A*Bn 4 A/Bn 5 A?Bn 0 exitnPlease choose.); scanf( %c,&c
26、h); if(ch = 1|ch = 2|ch = 3|ch = 4|ch = 5) system(cls); printf(Please input number A:n); scanf(%s,str1); /连续输入 printf(Please input number B:n); scanf(%s,str2); if(ch = 1|ch = 2|ch = 3) Invert(str1,strlen(str1);/将字符串反转 Invert(str2,strlen(str2); Translate(str1,num1,&bit1); Translate(str2,num2,&bit2);
27、max = Get_MAX(bit1,bit2); switch(ch) case1: BigN_Add(num1,num2,max,res); break; case2: Del_zero_High(num1, &bit1); Del_zero_High(num2, &bit2); if(BigN_cmp_High(num1,num2,bit1,bit2) 0)/判断两个数的大小,NUM1NUM2时BigN_cmp_High返回值为真 BigN_Min(num2,num1,max,res); break; else BigN_Min(num1,num2,max,res); break; ca
28、se3: BigN_Mul(num1,num2,bit1,bit2,res); bit_min=1;/经过乘法，则结果从res2输出 break; case4: Translate(str1,num1,&bit1); Translate(str2,num2,&bit2); Del_zero_low(num1, &bit1); Del_zero_low(num2, &bit2); if(bit2 = 0) printf(Input error !n); system(pause); system(cls); continue; if(res_cmp = BigN_cmp_low(num1,num
29、2,bit1,bit2,1) num2则调用函数 BigN_Div(num1,num2,bit1,bit2,res,mod,&res_bit,&div_bit_mod); break; case5: Translate(str1,num1,&bit1); Translate(str2,num2,&bit2); res_cmp = BigN_cmp_low(num1,num2,bit1,bit2,1); break; case0: printf(Thanks to use!n); return 0; default: printf(Input error !n); system(pause);
30、system(cls); continue; /下面是控制输出 printf(nnThe result is:nnt=nt); if(ch = 4) if(res_cmp 0) printf(The quotient is:nt 0ntThe mod is:nt ); if(bit1 = 0) putchar(0); else for(i = 1; i = bit1; i+) printf(%d,num1i); if(res_cmp = 0) printf(The quotient is:n t1ntThe mod is:n t0); if(res_cmp 0) printf(The quotient is:nt ); for(i = 1; i res_bit; printf(%d,resi+) ; Del_zero_low(mod,&div_bit_mod); printf(ntThe mod is:nt ); if(div_bit_mod = 0) putchar(0); for(i = 1; i 0)
