用C/C++实现基本高精度计算 |
您所在的位置：网站首页 › 计算精度是什么 › 用C/C++实现基本高精度计算 |
|
高精度计算
什么是高精度高精度算法高精度数的读写高精度加法高精度减法高精度乘法高精度除法及求余
（前置技能：小学数学知识，C语言基础） 什么是高精度我们知道，C/C++在64位编译器中支持的环境下，其各种整型数据类型表示是有范围的。 类型名 取值范围 signed char -128~127 unsiged char 0~255 short int -32768~32767 int -2147483648~2147483647 unsigned int 0~4294967295 long -2147483648~2141483647 unsigned long 0~4294967295 long long -9223372036854775808~9223372036854775807 unsigned long long 0~18446744073709551615尽管long long类型（或者在有些编译器中表示为__int64.注意int64前面有2个下划线）能表示的数已经相当大了，但和一些天文数字比起来，它连屏幕的一行都占不到。很多实际数学问题其实是long long也无法解决的。 例如，围棋的走法有3的361次方，这个数字怎么显示出来？宇宙中原子的总和是10的80次方，怎么显示出来？这些都是语言本身的数据类型无法表示的。实际上，这些数字如果用二进制去储存的话，需要的空间也是特别大的。为了节约空间，同时让我们能够算出这些大数据，我们需要一种应用数组进行模拟计算的方法——高精度计算。 高精度算法提醒：本博文该部分的所有代码均只用于展示计算原理，如果要整合在一起并进行更加复杂的符合操作，会产生诸多bug（其实直接复制粘贴任何一段都可能会有问题）总之就是，在这里找不到板子啦 高精度数的读写 读入高精度数 直观地输入一个高精度数时，我们需要存储一个有很多很多位的数字. 如何存储？最直接的方法就是将它存入一个字符串. 例如，我们可以这样： char str[100] = {""};//100表示数据可能的最大位数. scanf("%s, &str);这种输入方式再简单不过了，我们输入“43983926969436339448266492\n” 则数据“43983926969436339448266492”就被存入其中了 （提示：彩蛋数据） 2. 存储高精度数 现在，数据的读取完成了，我们应该如何处理这个数，让他变得方便于计算呢？ 我们不妨再设置一个数组，然后将输入的数逆序存入，也就是将str的最后一位存入数组a的第0位、将str的倒数第二位存入数组a的第1位…… #include int a[100] = {0};//100应该为这个数据可能的最大位数. for(int i = 0; i for(int i = 0; i int len = 0; if(strlen(x.str) > strlen(y.str)) len = strlen(x.str); else len = strlen(y.str); for(int i = 0; i ans->a[i] -= 10; ans->a[i + 1]++; } } }加法计算器完整代码： #include #include #include #define LEN 1001//假定该程序处理的数据都是小于1000位的. /*最长位数1001是为了安全.*/ struct hp{ char str[LEN]; int a[LEN]; };//创建结构体hp（high-precision） //注意使用指针，这样来通过指针形参修改传入的实参. void init(struct hp *x)//hp初始化函数 { for(int i = 0; i scanf("%s", &x->str); int len = strlen(x->str); for(int i = 0; i a[i] = x->str[len - i - 1] - '0'; } void add(struct hp x, struct hp y, struct hp* ans)//加法函数 { int len = 0; if(strlen(x.str) > strlen(y.str)) len = strlen(x.str); else len = strlen(y.str); for(int i = 0; i ans->a[i] -= 10; ans->a[i + 1]++; } } } void show(struct hp ans)//输出函数 { int j = LEN - 1;//数组有LEN位，其最后一个下标是LEN-1. while(ans.a[j] == 0 && j >= 1) --j;//跳过所有前导0. /*注：为了确保能输出结果0，前导0最多跳到第一位， 不检查第0位是否为0，因此加了条件j >= 1.*/ //现在，j的值是我们要输出的这个结果的最大位的下标. while(j >= 0) { printf("%d", ans.a[j]); --j; } printf("\n"); } int main() { struct hp x, y, ans; init(&x); init(&y); init(&ans); in(&x); in(&y); add(x, y, &ans); show(ans); return 0; }以上就是进行高精度加法的过程了. 高精度减法实现高精度减法，我们同样可以用三个结构体. 原理与加法相似，仍然是竖式原理： 先获取被减数的位数len，则本次减法计算需要进行len次操作. 从第0位开始，每次将对应位相减，得到和在该位的数值. 如果和在该位的数值小于0，那么将其加上10，并让高一位减1. void minus(struct hp x, struct hp y, struct hp* ans) { int len = strlen(x.str); for(int i = 0; i ans->a[i] += 10; ans->a[i + 1]--; } } }但是这样的减法是无法计算结果为负数的情况. 例如1 - 10.为了解决减法出现负数的问题，我们需要往结构体中添加一个表示正负的符号. 例如，添加一个bool值，并定义一个比较函数，利用其比较被减数和减数的大小（此处比较函数就交给你们啦）. 当减数大于被减数，让设置的bool值为0，反之为1. 当bool值为1时直接进行减法运算. 如果bool值为0，就返回用减数减去被减数的结果. 同样地，利用这个表示符号位的布尔值，我们还可以定义含有负数的加法，等等…… 高精度乘法要进行高精度乘法，我们会如何去操作？ 竖式乘法？我们很容易想到这样的方式： 计算123 * 52， 首先列竖式，让123乘以2，也就是让每一位乘以2，得到246. 然后让123每一位乘以5，得到615（这里隐含了进位操作）. 最后，因为5是十位，它的位权是10，所以615修正为6150. 让6150+246，得到结果6396. 这个算法是可行的，让我们来看它的步骤应该如何设计： 首先获取被乘数和乘数的长度len1，len2；定义len2个高精度数 a[len2]，它们作为被乘数与乘数每一位分别相乘的结果；每个 a[i] 拥有一个位权 j ，j 决定在后续处理中将所有 a[i] 相加时每个a[i] 要乘以10的幂数； （说白了就是为了模拟竖式乘法最后相加的过程）取出乘数的第 i 位，让被乘数的每一位乘以这个数 ，并把乘得的结果存入a[i] 对应的位. （例如上方例子，123乘以5的时候，位权j为1，我们应当将结果15、 10、 5分别存入 a[1] 的第1（j + 0）位，第2（j + 1）位，第3(j + 2)位. 这里的a[1] 就是 {0，5，10，15} 了. 同理，我们知道 a[0] 为 {2，4，6}.）最后一步和自然的竖式乘法的最后一步一致，让所有的 a[i] 相加. 因为我们在之前的讨论中已经封装了高精度的加法，并且进位判定都是用的while语句，因此无论 a[i] 的第几位有多大，最后相加的过程中也能利用进位得到正确结果了.代码实现： void multi(struct hp x, struct hp y, struct hp* ans) { int len1 = strlen(x.str); int len2 = strlen(y.str); struct hp A[len2];//乘数有len2位. /*这里应该还有一个使所有A.a[i]初始化为0的操作. 这里只展示乘法原理，略去.*/ for(int i = 0; i struct hp tmp; ans = add(ans, A[i], tmp); } return ans; } 高精度除法及求余高精度除法的原理仍然是基于竖式除法……只不过，为了方便代码更加容易理解，我们不妨换一种方式解释. 譬如，我们现在要计算1234除以9. 首先，获取最大位是4.将其减1得到3.9乘以10的3次幂，得到9000.用1234减去9000，结果小于0，有效的减法为0次. 在结果的千位放置0.将9000降幂变为900，用1234减去900，得到334. 再减一个900，小于0. 有效的减法为1次，在结果的百位放置1.将900降幂得到90，用334减去90，可以减3次，得到64. 有效的减法为3次，在结果的十位放置3.将90降幂得到9，用64减去9，可以减7次，得到1.在结果的个位放置7.9已经是9乘以10的零次幂了，最后这个1小于除数，那么我们除法得到的余数是1.故：1234除以9等于137，余1.那么，我们将其转化为可以被机器执行的描述： 如果被除数的位数（len1）小于除数的位数（len2），直接返回0. (余数为被除数.)否则的话，获取除数位数，让其乘以10的（被除数位数-除数位数）次方，得到一个数b.定义一个长度最长为被除数位数数组cnt[len1].将被除数减去b. 每减去一次b，cnt[位数]++.当被除数即将在减去后小于0时，不执行该步减法，让b缩小为原来的十分之一.继续减，直到b和原来的除数相等.该算法的实现依赖于高精度乘法和高精度减法，只有这两种计算方法已经封装了才可以实现除法. 另外，同样需要一个比较函数. 利用这个算法，我们就可以求出两个数的商和余数了. 感受：ACM的日子，每周还是要学点东西的~ |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |