FreeBASIC高精度计算讲稿

1、高精度计算高精度计算高精度计算的由来与含义在FB中，整型/长长整型数的长度只有4字节/8字节。整型的取值范围分别为-2147483648 2147483647。Longint数的长度为19位。如果需要获得超过这个精度的运算结果（如大整数相加、相乘、实数运算要求有多位小数等），只有靠程序来实现了也称为“大整数运算”；在通过程序获得更高的精度的做法中，通常是利用数组，把每一位数字存放在一个元素中，然后，模仿笔算的方式，一位一位地计算，这就是计算机的高精度计算* 数组存储的优化：优化空间、计算量；高精度计算的主要步骤：高精度计算的主要步骤：高精度计算要分三个方面来处理：数据的输入与存储，估计结果的位

2、数（How？），定义存储数组的大小；运算：加法的进位、减法的借位，乘法的积，除法的商和余数的处理；1)结果的输出。原始数据的输入与存储原始数据的输入与存储数字分离，存入数组数字分离，存入数组输入一个正整数(以回车结束)，把各位数字从此数中分离出来，通常用 MOD 和整除两个操作来完成，每位数字都存入数组的一个元素中。问题：若输入的值超过了整型的范围？数字一个一个输入，存入数组一个正整数，把它的数字从最高位开始，一个一个输入，直至最后一个数字，再输入一个任意负数，表示输入结束。每输入一个数字，就存入数组的一个元素之中。具体操作如下：输入一个数字，如为负数，就结束输入；判断此数字是否合法，合法就存

3、入数组，不合法就显示出错的停息，结束；1)重复(1)、(2)操作。例如，输入一个四位数1234后，在数组a()中就存放了各位数字。 数组a()的各元素： a(1) a(2) a(3) a(4) 1 2 3 4这样，各数字的位权与下标的序号相反，因而，输入时无法预先确定数字的位数，就只好将数组定义得大一点，如 DIM A(100)或者：视题目中数据范围而定；能否正序存放？数字字符串分离转成数存入数组输入一个数字字符串，以回车结束，计算其长度，定义数组；用MID(A_STR,I,1)依次一一分离出字符；判断此字符是否是数字字符，是就转为数字存入数组，否就显示出错信息，结束；如没有分离完就重复(2)

4、、(3)的操作，若已分离完则结束。数字字符串分离转成数存入数组（续）例如，输入一个字符串“1234”后，在数组a()中就存放了各位数字： a(1) a(2) a(3) a(4) 1 2 3 4 在这样的存放方式下，数字的位权与下标序号反向存入数组反序存储便于后面的计算； 初赛中常见“正序存储”。数字以字符形式一个一个输入转成数存入数组把一个正整数的各位数字以字符的形式，从最高位开始，一个一个输入，最后输入一个“$”符号表示输入结束数字字符转为数字，分别存入数组，这种方法类似方法2，只是加上了字符转为数字的内容四种方法的比较第一种方法输入简单方便，但精度有限第二、四种方法数据输入太繁，但精度不限

5、；第三种数据输入简单方便，且精度比第一种方式高得多，能应付较高的需要，比较实用。下面的例子大多采用第三种方法。四种基本的高精度计算高精度加法高精度减法高精度乘法高精度除法高精度加法高精度加法 高精度加法运算的算法，需要从输入、处理和输出这三部分来分析数据的输入与存储，估计结果的位数，定义存储数组的大小设参与加法运算的两个数串为 a_str 和 b_str：输入 a_str 与 b_str，计算两者的长度 La = LEN(a_str) : Lb = LEN(b_str)比较 La 与 Lb 的大小，如 Lb 大，要交换 a_str 和b_str (同时交换La和Lb)，然后定义数组： DIM

6、as integer a(La+1), b(La+1)DIM as integer a(La+1), b(La+1)1)两数相加，其和存放在 a() 数组中，不再开辟新的存储单元；数据的输入与存储，估计结果的位数，定义存储数组的大小分离 a_str 和 b_str，分别存入数组 a()和 b() 。例如： a_str = “12345678” b_str = “123456”加法运算是从个位开始的，分离时下标序号与位权一致，这样运算起来就比较方便了 Why ? 此时，a(1)a(9)的值分别为8、7、6、5、4、3、2、1、0，b(1)b(9)的值分别为6、5、4、3、2、1、0、0、0。两数

7、从低位到高位，各位数字分别相加若某单元中的数值10的话，就要发生进位，即从本位中减去10，并将下一个单元的数值加1，具体操作如下： a(i)=a(i)+b(i) IF a(i)=10 THEN a(i) = a(i)-10 a(i+1) = a(i+1) + 1 END IF 这就是加法进位的算法，可以简化为： x = a(i) + b(i) a(i+1) = a(i+1) + x 10 a(i) = x mod 10 结果的输出注意：和的最后一位不一定进位，所以要判断最高位的值。如果是0，则这一位就不输出；1)因数据存放时，位权与下标序号是一致的，所以输出时用递减循环。高精度减法高精度减法运

8、算的算法，也需要从输入、处理和输出三部分来分析：数据的输入与存储，定义数组的大小两数从低位到高位，各位数字分别相减数据的输入与存储，定义数组的大小这一部分与加法不同的是：比较两个数的大小，如减数大，要用一个符号变量记下“-”，两数交换后，仍作大数减小数处理，只是在输出时，在前面加上“-”号；比较的方法，与加法也有区别，如只比较La与Lb，当然长的数大，但当La与Lb相等时，就无法处理了，这时，还要加上a_str与b_str的比较。以大数的大小来定义数组： DIM AS INTEGER A(LA), B(LA) 两数的差存储在A()数组中。两数从低位到高位，各位数字分别相减如某单元中的数值a(i

9、)b(i)时，就要借位，从下一个单元的数值中借1，本单元的数值加上10，然后再减，具体操作如下： IF A(I) B(I) THEN A(I+1) = A(I+1) - 1 A(I) = A(I) + 10 END IF A(I) = A(I) B(I)也可以先减，再判断是否需要借位： A(I) = A(I) B(I) IF A(I)1 N = N-1 WEND高精度乘法高精度乘法的算法，仍以输入、处理和输出三部分来分析：数据的输入与存储，定义存储数组的大小，这一部分与加法的不同点是： 增加一个存放乘积的数组c()，定义c(La+Lb) 问题：能否就把相乘的结果存放到A()中？1)两数相乘两数

10、相乘先从乘数的个位，分别与被乘数的由低位到高位的各位数字一一相乘；再以乘数的十位，分别与被乘数的由低位到高位的各位数字一一相乘； 直到乘数的最高位，分别与被乘数的由低位到高位的各位数字一一相乘。因此，乘法要用两重循环来实现，而循环体中的每次操作都要：乘法进位：x=a(i) * b(j)，x是 a( ) 数组中 i 位数与 b( )数组中的 j 位数的乘积： y = x 10 y是要进位的数 z = z mod 10 z是本位的数 乘积的位数是 w = i+j-1，在后面的加法进位时，再把y与z存入乘积数组c()中加法进位：把 z 加到乘积数组中c(w)=c(w)+z，这时的c(w)如果超过了1

11、0，还要进位。 把 y 与 c(w) 中的进位加到乘积数组中 c(w+1) = c(w+1) + y + c(w) 10 c(w)中去掉进位后的数值是 c(w) = c(w) MOD 10 弄清楚了乘法进位与加法进位，可以把它们合写成： X = A(I) * B(J) W = I + J 1 C(W) = C(W) + X MOD 10 C(W+1) = C(W+1) + X 10 + C(W) 10 C(W) = C(W) MOD 10结果的输出与减法相同。想一想：能否编写一个高精度求2n、n!的程序？高精度除法例8 被除数与除数是整型数，商是高精度的除法(指定保留e位小数)。算法分析算法分

12、析设a、b是两个系统允许的整型数，a/b的值有两种情况：a能被b整除，没有余数；a不能被b整除，有余数。可以看出，在做除法运算时，除数(b)是始终不变的，商数(d)和余数(a)是变的。下一次的被除数是“余数*10”，也是跟着变的。这三个变量之间的关系是： a = a * 10 : d=a b PRINT USING “#” ; d; d是一位商(小数)，一定要及时输出 a = a MOD b 把以上的三个语句放在一个循环里，一个除法运算就形成了。确定商的精度取几位小数的问题，可以输入一个正整数e来确定商的精度。例例9 被除数与除数是整型数，商是高精度的除法(指定保留e位小数)。如是循环小数输出

13、循环节，循环节用 表示。算法分析 在除法运算中，如不能整除，就有三种情况：有限小数，最后除尽；循环小数，由指定的精度，输出e位小数；1)循环小数，输出循环节。上例解决了前两种情况，现在来讨论如何处理循环小数的情况。判断循环小数，只要看余数是否重复出现。若余数重复出现，所得商就会重复出现，这就产生了循环小数处理的方法：可把每次出现的不同余数用数组记录下来，若以后的操作中产生了新的余数，与数组中的余数相同，就证明出现了循环。除法运算终止。这时，只要把循环的部分输出即可。建立两个数组：用A( )数组来存放余数，用D( )数组来存放商数。数组的大小由e确定在运算的过程中，可能出现三种情况：有限小数，最

14、后除尽，就中断循环，记下循环变量当时的值，用以判断不输出循环节；循环小数，由指定的精度终止，输出e位小数；1)循环小数，在e位小数前出现循环，记下循环变量当时的值，用以判断输出循环节。例例10 被除数用数组存放，除数是个整型数，商是高精度的除法，如除不尽留余数。 高精度数除以普通整数 算法分析算法分析数据的输入与存储，定义存储数组的大小，要定义存储被除数被除数和商数商数两个数组两个数组数据处理算法分析：算法分析：除法运算是从最高位开始的，所以分离被除数时，数据的位权与下标序号正好相反。 正序存放正序存放 用一个计数循环，从 1 到La： 一位一位取出被除数；一位一位取出被除数； 在除法运算中，

15、每次都要把上一次的余数在除法运算中，每次都要把上一次的余数* *1010，再加上取出的本位被除数再加上取出的本位被除数 ( ( 与与 例例9 9 不同不同 ) )，临时组成被除数。临时组成被除数。具体的算法是： Y = Y * 10 + A(K) A(K)：被除数 D(K) = Y B D(K)：商 Y = Y MOD B 余数循环结束时，如除不尽，余数保存在 y 中。第一次做除法运算前，先设 Y = 0。结果输出有时，商数组前面有许多单元中存的是0。前面的无用的0不输出： K = 1 DO WHILE A(K) = 0 K = K + 1 LOOPdim as string aainput a=,aadim as integer b, a(100), d(100)input b=, b