求n!的高精度算法_zhangyifei.ppt

求N!的高精度算法•本文中的算法主要针对Pascal语 言这篇文章的内容u你了解高精度吗？u你曾经使用过哪些数据结构？u你仔细思考过如何优化算法吗？在这里，你将看到怎样成倍提速 求N!的高精度算法关于高精度uPascal中的标准整数类型u高精度算法的基本思想Pascal中的标准整数类型数据类型值域Shortint-128～127Byte0～255Integer-32768～32767Word0～65535Longint-2147483648～2147483647Comp-9.2e18～9.2e18Comp虽然属于实型，实际上是一个64位的整数高精度算法的基本思想uPascal中的标准整数类型最多只能处理在-263～263 之间的整数如果要支持更大的整数运算，就需要使 用高精度u高精度算法的基本思想，就是将无法直接处理的 大整数，分割成若干可以直接处理的小整数段，把对 大整数的处理转化为对这些小整数段的处理Back数据结构的选择u每个小整数段保留尽量多的位u使用Comp类型u采用二进制表示法每个小整数段保留尽量多的位u一个例子：计算两个15位数的和 Ø方法一•分为15个小整数段，每段都是1位数，需要15次1 位数加法 Ø方法二•分为5个小整数段，每段都是3位数，需要5次3位 数加法 Ø方法三•Comp类型可以直接处理15位的整数，故1次加法 就可以了 Ø比较•用Integer计算1位数的加法和3位数的加法是一样快 的•故方法二比方法一效率高•虽然对Comp的操作要比Integer慢，但加法次数却 大大减少•实践证明，方法三比方法二更快使用Comp类型u高精度运算中，每个小整数段可以用Comp类型表 示uComp有效数位为19～20位u求两个高精度数的和，每个整数段可以保留17位u求高精度数与不超过m位整数的积，每个整数段可 以保留18–m位u求两个高精度数的积，每个整数段可以保留9位 u如果每个小整数段保留k位十进制数，实际上可以 认为其只保存了1位10k进制数，简称为高进制数 ，称1 位高进制数为单精度数采用二进制表示法u采用二进制表示，运算过程中时空效率都会有所 提高，但题目一般需要以十进制输出结果，所以还要 一个很耗时的进制转换过程。

因此这种方法竞赛中一 般不采用，也不在本文讨论之列Back算法的优化u高精度乘法的复杂度分析u连乘的复杂度分析u设置缓存u分解质因数求阶乘u二分法求乘幂u分解质因数后的调整高精度乘法的复杂度分析u计算n位高进制数与m位高进制数的积 Ø需要n*m次乘法 Ø积可能是n+m–1或n+m位高进制数 Back连乘的复杂度分析（1）u一个例子：计算5*6*7*8Ø方法一：顺序连乘•5*6=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）u若“n位数*m位数=n+m位数”，则n个单精度数 ，无论以何种顺序相乘，乘法次数一定为n(n-1)/2次 Ø证明：•设F(n)表示乘法次数，则F(1)=0，满 足题设•设kax+k–bx时，选用(ab)xak，反之，则采 用ax+kbx•∴axbx–akax+k–bx•∴(bx–ak)(ax+1)0•∴bxak•这时kxlogabBack总结u内容小结 Ø用Comp作为每个小整数段的基本整数类 型 Ø采用二进制优化算法 Ø高精度连乘时缓存和缓存的设置 Ø改进的求平方算法 Ø二分法求乘幂 Ø分解质因数法求阶乘以及分解质因数后的 调整u应用 Ø高精度求乘幂（平方） Ø高精度求连乘（阶乘） Ø高精度求排列组合结束语求N!的高精度算法本身并不难，但我们仍然可以从 多种角度对它进行优化。

其实，很多经典算法都有优化的余地我们自己编 写的一些程序也不例外只要用心去优化，说不准你就 想出更好的算法来了 也许你认为本文中的优化毫无价值确实是这样， 竞赛中对高精度的要求很低，根本不需要优化而我以 高精度算法为例，不过想谈谈如何优化一个算法我想 说明的只有一点： 算法是可以优化的。