国家集训队2001论文集 张一飞i

《国家集训队2001论文集 张一飞i》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求N!的高精度算法本文中的算法主要针对Pascal语言这篇文章的内容你了解高精度吗？你曾经使用过哪些数据结构？你仔细思考过如何优化算法吗？在这里，你将看到怎样成倍提速求N!的高精度算法关于高精度Pascal中的标准整数类型高精度算法的基本思想Pascal中的标准整数类型数据类型值域Shortint-128～127Byte0～255Integer-32768～32767Word0～65535Longint-2147483648～2147483647Comp-9.2e18～9.2e18Comp虽然属于实型，实际上是一个64位的

2、整数高精度算法的基本思想Pascal中的标准整数类型最多只能处理在-263～263之间的整数。如果要支持更大的整数运算，就需要使用高精度高精度算法的基本思想，就是将无法直接处理的大整数，分割成若干可以直接处理的小整数段，把对大整数的处理转化为对这些小整数段的处理Back数据结构的选择每个小整数段保留尽量多的位使用Comp类型采用二进制表示法每个小整数段保留尽量多的位一个例子：计算两个15位数的和方法一分为15个小整数段，每段都是1位数，需要15次1位数加法方法二分为5个小整数段，每段都是3位数，需要5次3位数加法方法三Co

3、mp类型可以直接处理15位的整数，故1次加法就可以了比较用Integer计算1位数的加法和3位数的加法是一样快的故方法二比方法一效率高虽然对Comp的操作要比Integer慢，但加法次数却大大减少实践证明，方法三比方法二更快使用Comp类型高精度运算中，每个小整数段可以用Comp类型表示Comp有效数位为19～20位求两个高精度数的和，每个整数段可以保留17位求高精度数与不超过m位整数的积，每个整数段可以保留18–m位求两个高精度数的积，每个整数段可以保留9位如果每个小整数段保留k位十进制数，实际上可以认为其只保存了1位1

4、0k进制数，简称为高进制数，称1位高进制数为单精度数采用二进制表示法采用二进制表示，运算过程中时空效率都会有所提高，但题目一般需要以十进制输出结果，所以还要一个很耗时的进制转换过程。因此这种方法竞赛中一般不采用，也不在本文讨论之列Back算法的优化高精度乘法的复杂度分析连乘的复杂度分析设置缓存分解质因数求阶乘二分法求乘幂分解质因数后的调整高精度乘法的复杂度分析计算n位高进制数与m位高进制数的积需要n*m次乘法积可能是n+m–1或n+m位高进制数Back连乘的复杂度分析（1）一个例子：计算5*6*7*8方法一：顺序连乘5*6

5、=30，1*1=1次乘法30*7=210，2*1=2次乘法210*8=1680，3*1=3次乘法方法二：非顺序连乘5*6=30，1*1=1次乘法7*8=56，1*1=1次乘法30*56=1680，2*2=4次乘法共6次乘法共6次乘法特点：n位数*m位数=n+m位数连乘的复杂度分析（2）若“n位数*m位数=n+m位数”，则n个单精度数，无论以何种顺序相乘，乘法次数一定为n(n-1)/2次证明：设F(n)表示乘法次数，则F(1)=0，满足题设设k

6、(n-k)位数”，则F(n)=F(k)+F(n-k)+k(n-k)=n(n-1)/2（与k的选择无关）Back设置缓存（1）一个例子：计算9*8*3*2方法一：顺序连乘9*8=72，1*1=1次乘法72*3=216，2*1=2次乘法216*2=432，3*1=3次乘法方法二：非顺序连乘9*8=72，1*1=1次乘法3*2=6，1*1=1次乘法72*6=432，2*1=2次乘法特点：n位数*m位数可能是n+m-1位数共6次乘法共4次乘法设置缓存（2）考虑k+t个单精度数相乘a1*a2*…*ak*ak+1*…*ak+t设a1*

7、a2*…*ak结果为m位高进制数（假设已经算出）ak+1*…*ak+t结果为1位高进制数若顺序相乘，需要t次“m位数*1位数”，共mt次乘法可以先计算ak+1*…*ak+t，再一起乘，只需要m+t次乘法在设置了缓存的前提下，计算m个单精度数的积，如果结果为n位数，则乘法次数约为n(n–1)/2次，与m关系不大设S=a1a2…am，S是n位高进制数可以把乘法的过程近似看做，先将这m个数分为n组，每组的积仍然是一个单精度数，最后计算后面这n个数的积。时间主要集中在求最后n个数的积上，这时基本上满足“n位数*m位数=n+m位数”

8、，故乘法次数可近似的看做n(n-1)/2次设置缓存（3）缓存的大小设所选标准数据类型最大可以直接处理t位十进制数设缓存为k位十进制数，每个小整数段保存t–k位十进制数设最后结果为n位十进制数，则乘法次数约为k/(n–k)∑(i=1..n/k)i=(n+k)n/(2k(t–k))，其中k远小于n要乘法次数