nbhkdz.com冰点文库

求N!的高精度算法-张一飞


求N!的高精度算法

本文中的算法主要针对Pascal语言

这篇文章的内容
? 你了解高精度吗?
? 你曾经使用过哪些数据结构? ? 你仔细思考过如何优化算法吗?

在这里,你将看到怎样成倍提速 求N!的高精度算法

关于高精度
? Pascal中的标准整数类型

r />? 高精度算法的基本思想

Pascal中的标准整数类型
数据类型 值域

Shortint Byte
Integer Word Longint Comp

-128~127 0~255
-32768~32767 0~65535 -2147483648~2147483647 -9.2e18~9.2e18

Comp虽然属于实型,实际上是一个64位的整数

Back

高精度算法的基本思想
? Pascal中的标准整数类型最多只能处理在-263~263之

间的整数。如果要支持更大的整数运算,就需要使 用高精度 ? 高精度算法的基本思想,就是将无法直接处理的大 整数,分割成若干可以直接处理的小整数段,把对 大整数的处理转化为对这些小整数段的处理

数据结构的选择
? 每个小整数段保留尽量多的位
? 使用Comp类型 ? 采用二进制表示法

每个小整数段保留尽量多的位
? 一个例子:计算两个15位数的和

? 方法一
?

分为15个小整数段,每段都是1位数,需要15次1位数加法 分为5个小整数段,每段都是3位数,需要5次3位数加法 Comp类型可以直接处理15位的整数,故1次加法就可以了 用Integer计算1位数的加法和3位数的加法是一样快的 故方法二比方法一效率高 虽然对Comp的操作要比Integer慢,但加法次数却大大减少 实践证明,方法三比方法二更快

? 方法二
?

? 方法三
?

? 比较
? ? ? ?

使用Comp类型
? 高精度运算中,每个小整数段可以用Comp类型表示
? Comp有效数位为19~20位 ? 求两个高精度数的和,每个整数段可以保留17位

? 求高精度数与不超过m位整数的积,每个整数段可以

保留18–m位 ? 求两个高精度数的积,每个整数段可以保留9位 ? 如果每个小整数段保留k位十进制数,实际上可以认 为其只保存了1位10k进制数,简称为高进制数 ,称1 位高进制数为单精度数

Back

采用二进制表示法
? 采用二进制表示,运算过程中时空效率都会有所提

高,但题目一般需要以十进制输出结果,所以还要 一个很耗时的进制转换过程。因此这种方法竞赛中 一般不采用,也不在本文讨论之列

算法的优化
? 高精度乘法的复杂度分析
? 连乘的复杂度分析 ? 设置缓存 ? 分解质因数求阶乘 ? 二分法求乘幂

? 分解质因数后的调整

Back

高精度乘法的复杂度分析
? 计算n位高进制数与m位高进制数的积

? 需要n*m次乘法 ? 积可能是n+m–1或n+m位高进制数

连乘的复杂度分析(1)
? 一个例子:计算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位数

Back

连乘的复杂度分析(2)
? 若“n位数*m位数=n+m位数”,则n个单精度数,

无论以何种顺序相乘,乘法次数一定为n(n-1)/2次 ? 证明:
? ? ? ?

设F(n)表示乘法次数,则F(1)=0,满足题设 设k<n时,F(k)=k(k-1)/2,现在计算F(n) 设最后一次乘法计算为“k位数*(n-k)位数”,则 F(n)=F(k)+F(n-k)+k (n-k)=n(n-1)/2(与k的选择无关)

设置缓存(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次乘法

共6次乘法

? 方法二:非顺序连乘
? ? ?

共4次乘法

特点:n位数*m位数可能是n+m-1位数

设置缓存(2)
? 考虑k+t个单精度数相乘a1*a2*…*ak*ak+1*…*ak+t ? 设a1*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位 数”,故乘法次数可近似的看做n(n-1)/2次

Back

设置缓存(3)
? 缓存的大小

? 设所选标准数据类型最大可以直接处理t位十进制数 ? 设缓存为k位十进制数,每个小整数段保存t–k位十进制数 ? 设最后结果为n位十进制数,则乘法次数约为 ? k/(n–k) ∑(i=1..n/k)i=(n+k)n/(2k(t–k)),其中k远小于n ? 要乘法次数最少,只需k (t–k)最大,这时k=t/2 ? 因此,缓存的大小与每个小整数段大小一样时,效率最高 ? 故在一般的连乘运算中,可以用 Comp 作为基本整数类型, 每个小整数段为9位十进制数,缓存也是9位十进制数

Back

分解质因数求阶乘
? 例:10!=28*34*52*7

? n!分解质因数的复杂度远小于nlogn,可以忽略不计 ? 与普通算法相比,分解质因数后,虽然因子个数m变多了, 但结果的位数n没有变,只要使用了缓存,乘法次数还是 约为n(n-1)/2次 ? 因此,分解质因数不会变慢(这也可以通过实践来说明) ? 分解质因数之后,出现了大量求乘幂的运算,我们可以优 化求乘幂的算法。这样,分解质因数的好处就体现出来了

二分法求乘幂
? 二分法求乘幂,即: ? a2n+1=a2n*a ? a2n=(an)2 ? 其中,a是单精度数 ? 复杂度分析 ? 假定n位数与m位数的积是n+m位数 ? 设用二分法计算an需要F(n)次乘法 ? F(2n)=F(n)+n2,F(1)=0 ? 设n=2k,则有F(n)=F(2k)=∑(i=0..k–1)4i=(4k–1)/3=(n2–1)/3
? 与连乘的比较 ? 用连乘需要n(n-1)/2次乘法,二分法需要(n2–1)/3 ? 连乘比二分法耗时仅多50% ? 采用二分法,复杂度没有从n2降到nlogn

二分法求乘幂之优化平方算法
? 怎样优化

? (a+b)2=a2+2ab+b2 ? 例:123452=1232*10000+452+2*123*45*100 ? 把一个n位数分为一个t位数和一个n-t位数,再求平方
? 怎样分

? 设求n位数的平方需要F(n)次乘法 ? F(n)=F(t)+F(n-t)+t(n-t),F(1)=1 ? 用数学归纳法,可证明F(n)恒等于n(n+1)/2 ? 所以,无论怎样分,效率都是一样 ? 将n位数分为一个1位数和n–1位数,这样处理比较方便

Back

二分法求乘幂之复杂度分析
? 复杂度分析

? 前面已经求出F(n)=n(n+1)/2,下面换一个角度来处理 ? S2=(∑(0≤i<n)ai10i)2=∑(0≤i<n)ai2102i+2∑(0≤i<j<n)aiaj10i+j ? 一共做了n+C(n,2)=n(n+1)/2次乘法运算 ? 普通算法需要n2次乘法,比改进后的慢1倍
? 改进求乘幂的算法

? 如果在用改进后的方法求平方,则用二分法求乘幂,需要 (n+4)(n–1)/6次乘法,约是连乘算法n(n–1)/2的三分之一

分解质因数后的调整(1)
? 为什么要调整

? 计算S=211310,可以先算211,再算310,最后求它们的积 ? 也可以根据S=211310=610*2,先算610,再乘以 2即可 ? 两种算法的效率是不同的

Back

分解质因数后的调整(2)
? 什么时候调整

? 计算S=ax+kbx=(ab)xak ? 当k<xlogab时,采用(ab)xak比较好,否则采用ax+kbx更快 ? 证明:
? ?

? ? ? ? ?

可以先计算两种算法的乘法次数,再解不等式,就可以得到结论 也可以换一个角度来分析。其实,两种算法主要差别在最后一步 求积上。由于两种方法,积的位数都是一样的,所以两个因数的 差越大,乘法次数就越小 ∴当axbx–ak>ax+k–bx时,选用(ab)xak,反之,则采用ax+kbx。 ∴axbx–ak>ax+k–bx ∴(bx–ak)(ax+1)>0 ∴bx>ak 这时k<xlogab

总结
? 内容小结

? 用Comp作为每个小整数段的基本整数类型 ? 采用二进制优化算法 ? 高精度连乘时缓存和缓存的设置 ? 改进的求平方算法 ? 二分法求乘幂 ? 分解质因数法求阶乘以及分解质因数后的调整
? 应用

? 高精度求乘幂(平方) ? 高精度求连乘(阶乘) ? 高精度求排列组合

结束语
求N!的高精度算法本身并不难,但我们仍然可以从 多种角度对它进行优化。 其实,很多经典算法都有优化的余地。我们自己编 写的一些程序也不例外。只要用心去优化,说不准你就 想出更好的算法来了。 也许你认为本文中的优化毫无价值。确实是这样, 竞赛中对高精度的要求很低,根本不需要优化。而我以 高精度算法为例,不过想谈谈如何优化一个算法。我想 说明的只有一点: 算法是可以优化的。


求N!的高精度算法

张一飞 求 N!的高精度算法 摘要:张一飞是 3 届(2000,2001,2002)IOI 国家集训队的成员,第 14 届(2002 年,韩国龙仁 市庆熙大学)国际信息学奥林匹克竞赛金牌...

阶乘算法

本文是张一飞 2001 年写的论文,原文可从 http://oibh.kuye.cn/download/thesis/thesis2001_zha ngyifei.zip 处下载 求 N!的高精度算法 本文中的算法主要针对 ...

张一飞论文

张一飞 【摘要】 在算法设计中,人们往往不自觉地...编程求出 N 个数依序排列时有多少种关系。 <1>...我们看一道数值计算题: 【高精度计算问题】(湖南 ...

历年国家集训队论文题目

- 动态规划算法的优化技巧 俞玮 - 基本动态规划问题的扩展 张一飞 - 求 N!的高精度算法 2002 年 戴德承 - 退一步海阔天空——“目标转化思想”的若干应用...

WC1999

《动态规划算法的优化技巧》 俞玮:《基本动态规划问题的扩展》 张一飞:《求 N!的高精度算法》 WC2002: 戴德承:《退一步海阔天空——“目标转化思想”的若干应用...

复赛技巧

算法,而基于长边的 O(N) 或者 O(N*N)的算法...19.在只涉及乘除的高精度运算中,按因数存储的效率...(也就是和 mod 2) 这类问题张一飞的论文有极为...