几何精度_超大数字超高精度的几何运算

　　【摘 要】针对计算机精度位数的限制，按照位运算原理，创意设计加、减、乘、除和乘方的大数五则运算新算法。给出具体的C语言程序实现代码，可以精确计算加数、乘数、被减数、减数、被除数、除数、底数在十进制位数(含小数、负数)1000位以内，指数在十进制位数(正整数)8位以内，和数、积数、差数、商数、乘方等结果(含小数、负数)在十进制位数10000位以内的运算。
　　【关键词】大数 算法原理 编程
　　
　　1 研究背景
　　
　　华罗庚说:“宇宙之大，粒子之微，火箭之速，化工之巧，地球之变，生物之谜，日用之繁，无处不用数学。”
　　在生活中，计算是一件很常见的事。在大多数时间，我们可以利用手中的计算器或者用计算机操作系统自带的计算器进行一些十分精确的计算，但这些计算器计算的数字却不能够超过32位。实际上，“宇宙之大，粒子之微”，有许许多多的方面，需要我们使用非常巨大或者极其微小的数据进行计算，像天文学、物理学、地理学、生物学、力学等。此外，在有限元、流体力学计算、天气和气候预报、基因工程、蛋白质和分子分析模拟、石油储量分析等应用领域，高精度计算也是很常用的。当然，在科学和数学方面，则更加会频繁地使用高精度的、大数字的高速加减乘除和乘方运算。在历届的数学竞赛里，也总会出现一些较大数字的运算，如2��1000�-2��999�2��998�。虽然通过一些很巧妙的方法，可以计算出这道题目的答案应该是2，但这无法用直接计算的方法去验证结果。想用家用电脑验证，却因为数字太大超出计算范围而无法计算，或者只能得到一些近似的结果。
　　本程序按照位运算原理，创意设计加、减、乘、除和乘方的大数五则运算新算法。可以精确计算加数、乘数、被减数、减数、被除数、除数、底数在十进制位数(含小数、负数)1000位以内，指数在十进制位数(正整数)8位以内，和数、积数、差数、商数、乘方等结果(含小数、负数)在十进制位数10000位以内的运算。使用了C语言中的malloc函数，与普通数组进行对比，可改动答案和操作数的最大位数，且可避免因某个位数较大而出现的“未知错误”。因此，这种方法使得程序更具通用性、稳定性与可扩充性，保证程序正常运行。
　　2 算法原理
　　根据四则运算的原理和位运算原理设计了加减乘除和乘方的新算法，这些运算的算法介绍如下。
　　2.1 乘法算法原理
　　将两个乘数的每一位转换为单个的数字，存放于数组中。两数从左边第一位开始编号分别是:b(0)，b(1)，b(2)，b(3)……b(S1-1)；c(0)，c(1)，c(2)，c(3)……c(S2-1)，若b(I1)位(从左到右)与c(I2)位(从左到右)相乘的数将增加到答案的a(I3)位(从右到左，与正常思路相反)，则可以得到I3=(S1-I1)+(S2-I2)-2，只要再通过进位就可以很轻松得到结果。(见图1)
　　乘法示例：16*32
　　（1）分解到数组1 6 * 3 2(S1=2,S2=2),将答案数组初值赋零；
　　（2）I1 = 0 TO S1-1 ,I2 = 0 TO S2-1分别计算I3 = (S1-I1)+(S2-I2)-2，可以得到:
　　I1 = 0,I2 = 0 I3 = 2第二位(从右到左，与正常思路相反)增加1*3=3；第二位为3
　　I1 = 0,I2 = 1 I3 = 1第一位(从右到左，与正常思路相反)增加1*2=2；第一位为2
　　I1 = 1,I2 = 0 I3 = 1第一位(从右到左，与正常思路相反)增加6*3=18；第一位为20
　　I1 = 1,I2 = 1 I3 = 0第零位(从右到左，与正常思路相反)增加6*2=12；第零位为12
　　（3）进位 K=0 I = 0 TO R(R为答案的最大个数，下同)分别计算第I位(从右到左,与正常思路相反)上一位进的数和应该进下一位的数:
　　I=0第零位(从右到左，与正常思路相反)为12+K=12应进的位为K=FLOOR(12/10)=1第零位进位后为12MOD10=2
　　I=1第一位(从右到左，与正常思路相反)为20+K=21应进的位为K=FLOOR(21/10)=2第一位进位后为21MOD10=1
　　I=2第二位(从右到左，与正常思路相反)为3+K=5应进的位为K=FLOOR(5/10)=0第二位进位后为5MOD10=5
　　I=3第三位(从右到左，与正常思路相反)为0+K=0应进的位为K=FLOOR(0/10)=0第三位进位后为0MOD10=0
　　……
　　I=R第R位(从右到左,与正常思路相反)为0+K=0应进的位为K=FLOOR(0/10)=0第R位进位后为0MOD10=0
　　最后得到的结果为:2 1 5 0 0 0…… 0
　　（4）打印，从结果的最后一位开始寻找不为0的数,输出这之后的所有数，本题为512。如有小数，小数位数为两数小数位数的总和。（见图2)
　　2.2 乘方算法原理
　　和乘法的思想一样，x^y=x*x*x*……*x(y个x相乘)，运用乘法原理加以实现。
　　乘方示例：16^3
　　（1）分解到数组1 6和数字3,将答案数组初值赋零，计数器K = 0
　　（2）将1 6存入答案数组,K + 1
　　（3）计算1 6 * 1 6并将结果存入答案数组，答案数组为：2 5 6,K + 1
　　（4）计算2 5 6 * 1 6并将结果存入答案数组，答案数组为：4 0 9 6,K + 1
　　（5）K = 3，结束。
　　（6）打印，从最后一位开始寻找不为0的数，输出这之后的所有数，本题为4096。小数位数为底数小数位数乘指数。
　　2.3 加法算法原理
　　首先，需要将b、c两个加数的小数点对齐(先计算两数的位数S1,S2，然后计算两数的小数位数L1,L2)，然后，就可以通过每一位相加，并进位的方法得出答案。不失一般性，设l1≤l2,i=s1-l1-s2+l2,i≥0:
　　加法示例：156.78+78.156
　　（1）分解到数组 1 5 6 7 8 + 7 8 1 5 6(S1 = 5,S2 = 5,L1 = 2,L2 = 3)，将答案数组初值赋零；
　　（2）适当增加其中小数位数少的数的小数位数(增加0)，使两数小数位数相等，并移至数组的末尾；
　　（3）新的两个数：0 0 0…… 1 5 6 7 8 0 + 0 0 0…… 0 7 8 1 5 6；
　　（4）将每一位都相加，I = 0 TO D(D为加数的最大位数，下同)第I位相加，得到的答案数组为：0 0 0…… 1 12 14 8 13 6；
　　（5）进位，K=0,I = D TO 0 分别计算第I位(从左到右)上一位进的数和应该进下一位的数
　　I = D第D位(从左到右)为 6+K = 6应进的位为 K = FLOOD(6/10) = 0第D位进位后为6MOD10 = 6
　　I = D-1第D-1位(从左到右)为 13+K = 13应进的位为 K = FLOOD(13/10) = 1第D-1位进位后为13MOD10 = 3
　　I = D-2第D-2位(从左到右)为 8+K = 9应进的位为 K = FLOOD(9/10) = 0第D-2位进位后为9MOD10 = 9
　　I = D-3第D-3位(从左到右)为 14+K = 14应进的位为 K = FLOOD(14/10) = 1第D-3位进位后为14MOD10 = 4
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　I = D-4第D-4位(从左到右)为 12+K = 13应进的位为 K = FLOOD(13/10) = 1第D-4位进位后为13MOD10 = 3
　　I = D-5第D-5位(从左到右)为 1+K = 2应进的位为 K = FLOOD(2/10) = 0第D-5位进位后为2MOD10 = 2
　　I = D-6第D-6位(从左到右)为 0+K = 0应进的位为 K = FLOOD(0/10) = 0第D-6位进位后为0MOD10 = 0
　　……
　　I = 0第零位(从左到右)为 0+K = 0应进的位为 K = FLOOR(0/10) = 0第零位进位后为最后得到的结果为：0 0 0…… 2 3 4 9 3 6
　　（6）打印，从第零位(从左到右)开始寻找不为0的数，输出这之后的所有数，小数位数为两个数的小数位数中大的数，本题为234.936。(见图4)
　　2.4 减法算法原理
　　当被减数b每一位都比减数c的这一位大时，可以当作加法的逆运算(将+改为-)，但是很多时候数据都不会这么凑巧，其实可以先测定答案为正数还是负数。若为正数，则将每个数都控制在0～9之内，若为负数，则将每个数都控制在(-9)～0之内，大则进位，小则退位。不失一般性，设l1≤l2,i=s1-l1-s2+l2,i≥0:
　　b(0) ……b(i) ……b(s1-l1-1) (.) b(s1-l1) ……b(s1-1)
　　
　　
　　减法示例：19-91.1
　　（1）分解到数组1 9 - 9 1 1，将答案数组初值赋零；
　　（2）增加小数位数，参照加法示例；
　　新的两个数为：0 0 0…… 1 9 0 - 0 0 0…… 9 1 1
　　（3）将每一位相减，答案数组为:0 0 0…… -8 8-1(共D位)；
　　（4）从第零位(从左到右)开始寻找不为0的数，若为正数，说明答案为正数，否则答案为负数；
　　（5）发现这个数是负数，则将所有数补偿在(-9)～0之内；
　　I = R TO 0将第I位(从左到右)上的数补偿在(-9)～0之内
　　I = R第R位(从左到右)上的数为-1，进(退)0，第I位上的数为-1-(+)0=-1
　　I = R-1 第R-1位(从左到右)上的数为8，过大，进１，第I位上的数为8-10=-2
　　I = R-2第R-2位(从左到右)上的数为-8+1=-7，进(退)0，第I位上的数为-7-(+)0=-7
　　……
　　I = 0第零位(从左到右)上的数为0，进(退)0，第零位上的数为0-(+)0=0
　　最后得到的结果为：0 0 0…… -7 -2-1，小数位数为两个数的小数位数中大的数，本题为-7.21。(见图6)
　　2.5 除法算法原理
　　为使算法易于描述，首先，放大被除数或者放大除数，使被除数在除数和除数的10倍之间。然后，使用二分法以5为初值，逐位试算每一个数字，用此数与除数相乘，再与被除数进行比较。太大了，则将此位按二分法缩小为3，再以此类推进行比较,若太小了，则将此位按二分法放大为7后进行比较。
　　
　　
　　除法示例：0.11/3
　　（1）分解到数组0 1 1 / 3，检测除数是否为零，并计算答案的整数位数Z3 =[S1(第一个数的总位数) - L1(第一个数的小数位数)]- [S2(第二个数的总位数)- L2(第二个数的小数位数)]，Z3 = (2 - 2) -(1 -0) = -1。将除数和被除数从左到右相比较，寻找被除数与除数不同的第一个位数，发现被除数的这一位(第一位)不比除数大(若大或全部相同，则还得将上式Z3加一)，则说明答案的整数位数不用变(此步中，若Z3R(答案所有位数都有数字)，则跳到第（9）步，否则跳到第（4）步；
　　（9）打印，按第（1）步处理后输出所有数(R个数)，本题结果为0.036666……。(见图8)
　　3 流程示意
　　根据上述算法，我们使用VC++6.0编写了程序并绘制了流程图。
　　3.1主程序流程图
　　从in.txt中以字符形式读入第一个数b(全局变量)、操作符ch和第二个数c(全局变量)后，如果操作符是+，则转到子程序ases()；如果是-，则转到子程序sses()；如果是/，则转到子程序dses()；如果是*，则转到子程序mses()；如果是^，则转到子程序powses()。从子程序退出后，按照从左到右或从右到左的方式将结果a(全局变量)输出到out.txt中，在输出时需要对正负数和小数位进行判断，并作相应的处理，最后结束。(见图9)
　　3.2加法子程序流程图
　　全局变量a为结果，全局变量b、c为加数，将b、c各位移至数组末尾(最右端)，将b、c各位相加并存入a中，再将a从右到左进位，最后退回主程序。(见图10)
　　3.3减法子程序流程图
　　全局变量a为结果，全局变量b为被减数，c为减数，将b、c各位移至数组末尾(最右端)，将b、c各位相减并存入a中，再检测a是否大于0，若是，从右到左退位，否则，从右到左进位，最后退回主程序。(见图11)
　　a为结果，b为被除数，c为除数，s1和s2分别为b和c的长度，l1和l2分别为b和c的小数位数。l3为a的整数位数，先求出l3＝s1-l1+l2-s2，再放大b或c使c*10>b≥c，再逐位试算a的每一位，每次求出一位数后使b=10*(b-c*a[i])。当所有位数都算完或b=0时，根据l3调整结果a，当l312位数字。还可以对数组的每一个数做充分的利用，使每个空间保存9位数。另外，我们还希望计算π值和e值，同时，将用MFC对程序作移植以改善窗口显示风格。
　　
　　参考文献：
　　 [1]华罗庚.大哉数学之为用[J].科技文萃,1995,(6).
　　 [2]华罗庚.聪明在于勤奋天才在于积累[M].北京:中国少年儿童出版社,2006.
　　 [3]陈善义.双倍字长浮点数四则运算的一种算法[J].计算机工程与科学,1984,(1):45-55.
　　 [4]余龙生.785机双倍字长浮点算术运算的算法[J].计算机工程与科学,1981,(1):146-154.
　　 [5]朱玉田,徐君.高效浮点FFT的汇编语言程序编制[J].计算机应用研究,1996,(5):97-98.
　　 [6]杜丽娟,鞠宏军.用C语言实现超长整数的加减乘除四则运算[J].电脑开发与应用,2003,16(5):36-38.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文