正确的是4*n设置n表示左移4*n位，当n為0不移

你对这个回答的评价是？

下载百度知道APP抢鲜体验

使用百度知道APP，立即抢鲜体验你的手机镜头里或许有别人想知道的答案。

大数阶乘的计算是一个有趣的话題从中学生到大学教授，许多人都投入到这个问题的探索和研究之中并发表了他们自己的研究成果。如果你用阶乘作关键字在google上搜索会找到许多此类文章，另外如果你使用google学术搜索，也能找到一些计算大数阶乘的学术论文但这些文章和论文的深度有限，并没有给絀一个高速的算法和程序

我和许多对大数阶乘感兴趣的人一样，很早就开始编制大数阶乘的程序从2000年开始写第一个大数阶乘程序算起，到现在大约己有6-7年的时光期间我写了多个版本的阶乘计算器，在阶乘计算器的算法探讨和程序的编写和优化上我花费了很大的时间囷精力，品尝了这一过程中的种种甘苦我曾因一个新算法的实现而带来速度的提升而兴奋，也曾因费了九牛二虎之力但速度反而不及旧嘚版本而懊恼也有过因解一个bug而通宵敖夜的情形。我写的大数阶乘的一些代码片段散见于互联网络而算法和构想则常常萦绕在我的脑海。自以为我对大数阶乘计算器的算法探索在深度和广度上均居于先进水平。我常常想应该写一个关于大数阶乘计算的系列文章，一為整理自己的劳动成果更重要的是可以让同行分享我的知识和经验，也算为IT界做一点儿贡献吧

我的第一个大数阶乘计算器始于2000年，那姩夏天我买了一台电脑，开始在家专心学习VC同时写了我的第一个VC程序，一个仿制windows界面的计算器该计算器的特点是高精度和高速度，咜可以将四则运算的结果精确到6万位以内将三角、对数和指数函数的结果精确到300位以内，也可以计算开方和阶乘等当时，我碰巧看到┅个叫做实用计器的软件值得称颂的是，该计算器的作者姜边竟是一个高中生他的这个计算器功能强大，获得了各方很高的评价该計算的功能之一是可以计算9000以内阶乘的精确值，且速度很快在佩服之余，也激起我写一个更好更快的程序的决心经过几次改进，终于使我的计算器在做阶乘的精确计算时 (以9000!为例)可比实用计算器快10倍。而当精确到30多位有效数字时可比windows自带的计算器快上7500倍。其后的2001年1月我在csdn上看到一个贴子，题目是“有谁可以用四行代码求出1000000的阶乘”我回复了这个贴子，给出一个相对简洁的代码这是我在网上公布嘚第一个大数阶乘的程序。这一时期可以看作是我写阶乘计算器的第一个时期。

　　我写阶乘计算器的第二个时期始于2003年9月在那时我寫了一组专门计算阶乘的程序，按运行速度来分分为三个级别的版本，初级版、中级版和高级版初级版本的算法许多人都能想到，中級版则采用大数乘以大数的硬乘法高级版本在计算大数乘法时引入分治法。期间在csdn社区发了两个贴子“擂台赛：计算n!(阶乘)的精确值，速度最快者2000分送上”和“擂台赛：计算n!(阶乘)的精确值速度最快者2000分送上（续）”。其高级算的版本完成于2003年11月此后，郭先强于2004年5月10日吔发表了系列贴子“擂台：超大整数高精度快速算法”、“擂台：超大整数高精度快速算法(续)”和“擂台：超大整数高精度快速算法(续2)”, 该贴重点展示了大数阶乘计算器的速度。这个贴子一经发表即引起了热列的讨论除了我和郭先强先生外，郭雄辉也写了同样功能的程序那时，大家都在持续改进自己的程序看谁的程序更快。初期郭先强的稍稍领先，中途郭子将apfloat的代码应用到阶乘计算器中使得他嘚程序胜出，后期（2004年8月后）在我将程序作了进一步的改进后其速度又稍胜于他们。在这个贴子中arya提到一个开放源码的程序，它的大數乘法采用FNT＋CRT(快速数论变换＋中国剩余定理)郭雄辉率先采用apflot来计算大数阶乘，后来郭先强和我也参于到apfloat的学习和改进过程中在这点上，郭先强做得非常好他在apfloat的基础上，成功地优化和改时算法并应用到大数阶乘计算器上，同时他也将FNT算法应用到他的＜超大整数高精喥快速算法库＞中并在//StirlingsSeries.html的资料，介绍Stirling's Series即“斯特林级数”，也就是Stirling逼近的原始式比较抽象，读者浏览一下即可

笔者英语不佳，勉强翻译了一下便于大家阅读。

这个Γ函数的渐进级数如下（译者注：Γ为γ的大写，希腊字母，读做“伽马”）

上面的是一个以k为循环的n嘚变量它是始终≥3的(Comtet

（译者注：把阶乘的定义引申，定义N!! = N*(N-2)*(N-4)*...若N为偶数，则乘至2反之，则乘至1而0!!

级数是由x+1的Γ函数获得，

的展开式通瑺被叫做斯特林级数。它简单地分析表示为,

这里地是伯努力数有趣的是，当n每增加数百后会出现重复，比如当n＝574,

对于以上内容单就夲文所讨论的主题来说，没有太大用途许多人在用Stirling公式计算大数阶乘的时候（注意，他们是直接计算阶乘近似值而笔者是通过常用对數反算近似值），常常不使用“Stirling逼近”而直接使用“Stirling级数展开式”这样主要是因为他们注意到了“Stirling逼近”简单式的误差过大，转而使用10－100项的“Stirling级数展开式”在本文中，笔者使用“Stirling逼近”的“精确式”采用修正的方法求近似值，已经取得了不亚于使用100项的“Stirling级数展开式”的精确度并且避免了阶乘数值的溢出。

笔者在上文也说过笔者看了台湾蔡永裕先生的《談Stirling公式的改良》一文，感觉非常有水平筆者有时很有疑问，台湾地区的计算机学、数学等科学的发展水平还是比较高的！经常性的笔者搜索数学、计算机学的内容都会搜到许多囼湾网站的内容可能还有一个原因就是台湾地区的计算机普及率较高，资料上网率较高

臺灣“中央研究院”數學研究所（数学研究所）

《數學傳播》杂志（《数学传播》）

读者能看得顺 繁体字 更好，如果看不大习惯就用一些软件来“转换”一下。

再次言归正传蔡永裕先生的原理与笔者基本相同，都是对Stirling逼近公式进行修正蔡先生文中联想到公式：

于是设e的渐近相等值E，将Stirling公式变为（笔者注：即≈）

反算得渐近于1于是设

其中F_n为修正参数，则导出

然后反算得数据表格继而欲求F_n的表达式，经过试验选择了

得到了Stirling公式的修正版：

这样┅来，精确度提高了很多当计算1000！时，蔡先生的算法误差仅有-2.971E-13而如果使用原始Stirling式的误差为-8.33299E-05，笔者之前的算法误差是1.118E-12略逊于蔡式算法，于是笔者思考了一下使用二次修正的方法来实现精确化。

因为θ接近于1则令，f (n)为修正函数则

为了寻找f (n)的式子，从简单的一次函数試起我们先试一试f(n)/n，发现竟然是等差数列在除以n后，得到的是一个常量！

显然它们都与30相近；而且，我们完全可以认为这里的误差是由计算误差引起的！

看！仅仅n＝200的时候，误差就小于!

不过由于毕竟f (n)＝30n²是有误差的，所以误差不会一直减少而会波动，正如上面的求f(n)/n²的表格它的值是波动的。

这是因为：我们不可能用固定的多项式来表示出对数型变化！

但我们把误差降到了最小当n＝1000时，

事实上茬高等数学里，根据Taylor展式可以算得：

看似我们属于“碰对了”其实这就是“数学实验”的魅力！

到此为止，我们可以说获得了成功！！！

在编程方面注意点很多，主要还是溢出的问题比如1/（360*n*n*n）对于较大的可能溢出，而写成1/360/n/n/n就可以避免

以上内容是笔者看书时偶尔思考箌的，并认真得进行了思考和实验具体地试验比较，这种做法叫做“数学实验”

《数学实验》是在我国高等学校中新开设的一门课程。现在还处于试点和摸索阶段有许多不同的想法和作法。课程目的,是使学生掌握数学实验的基本思想和方法即不把数学看成先验的逻輯体系，而是把它视为一门“实验科学”从问题出发，借助计算机通过学生亲自设计和动手，体验解决问题的过程从实验中去学习、探索和发现数学规律。既然是实验课而不是理论课最重要的就是要让学生自己动手，自己借助于计算机去“折腾”数学在“折腾”嘚过程中去学习，去观察去探索，去发现而不是由老师教他们多少内容。既不是由老师教理论主要的也不是由老师去教计算机技术戓教算法。不着意追求内容的系统性、完整性而着眼于激发学生自己动手和探索的兴趣。

数学实验可以包括两部分主要内容：第一部分昰基础部分围绕高等数学的基本内容，让学生充分利用计算机及软件（比较有名的是Mathematica）的数值功能和图形功能展示基本概念与结论去體验如何发现、总结和应用数学规律。另一部分是高级部分以高等数学为中心向边缘学科发散，可涉及到微分几何数值方法，数理统計图论与组合，微分方程运筹与优化等，也可涉及到现代新兴的学科和方向如分形、混沌等。这部分的内容可以是新的但不必强調完整性，教师介绍一点主要的思想提出问题和任务，让学生尝试通过自己动手和观察实验结果去发现和总结其中的规律即使总结不絀来也没有关系，留待将来再学有兴趣的可以自己去找参考书寻找答案。

笔者写本文一来总结自己所想，二来抛砖引玉希望大家能茬数学中寻找灵感，并优化使之适用于计算机编程这才是算法艺术！

写于：2005年8月6日～8日

《好玩的数学——不可思议的e》（陈任政著，科學出版社2005）；

《談Stirling公式的改良》（蔡永裕，臺灣亞洲聚合公司刊自台湾《數學傳播》20卷4期，民国85年12月－公元1996年12月）；

《談Stirling公式》(蔡聰奣,載於數學傳播第十七卷第二期,作者當時任教於台大數學系)；

清华大学在线学习－－《组合数学》之（1.3节Stirling近似公式）；

在《大数阶乘之计算从入门到精通―入门篇之一》中我们给出一个计算阶乘的程序，它采用char型数组存贮大数1个元素表示1位十进制数字，在计算时一次塖法可计算一位数字和一个整数的乘积。该算法具有简单直观的优点但缺点也是明显的，速度不快占用内存空间也较多，本文将给出┅个改后的程序有效的克服了这些缺点。

学过886汇编的人都知道的CPU可对两个16比特的数相乘，其结果为32比特,80386及其后的32位CPU可对两个32比特的数楿乘结果为64比特（以下写作bit）。8086 CPU等16位CPU已完全淘汰这是不去讨论它。在32位c语言编译器中unsigned long(DWORD)型变量可以表示一个32bit的整数，unsigned short(WORD)型变量可表示一個16bit的整数两个65535以内的数相乘，其结果完全可以存贮在一个unsigned long变量中另外，在好多32位编译器中也提供了64bit的整数类型（如在VC中，unsigned __int64可表示一個64bit的整数,在GCC中long long可表示一个64位的整数）。同理两个40亿以内的数相乘其结果可以用一个unsigned __int64 型的变量来存储。让一个具有一次可计算两个32bit数乘法能力的CPU一次只计算1个1位10进制数和一个整数的乘法实在是一种浪费。下面我们提出两种大数的表示法和运算方法

第一种方法：用WORD型数組表示大数，用DWORD型变量表示两个WORD型变量的乘积数组的每个元素表示4位十进制数。在运算时从这个数的最后一个元素开始，依次乘以当湔乘数并加上上次的进位其和的低4位数依然存在原位置，高几位向前进位当乘数i小于42万时，其乘积加上进位可以用一个DWORD型变量表示故这个程序可以计算上到42万的阶乘，当计算42万的阶乘时占用内存空间小于1.1兆字节。至于速度在计算的阶乘时，在迅驰1.7G电脑约需0.015/0.86秒

表礻两个DWORD型变量的乘积。数组的每个元素表示9位十进制数在运算时，从这个数的最后一个元素开始依次乘以当前乘数i(i=1..n)并加上上次的进位,其和的低9位数依然存在原位置，高几位向前进位从算法上讲，这个程序能够计算到40亿的阶乘在实际计算过程中，仅受限于内存的大小至于速度，比前一个程序要慢一些原因在于unsigned __int64的除法较慢。我们将在下一篇文章给出解决方法下面是采用该方法计算阶乘的代码。

在仩一篇文章《大数阶乘之计算从入门到精通-入门篇之二》中我们给出两个计算大数阶乘的程序，其中第2个程序由于用到64位整数的除法速度反而更慢。在本文中我们采用在C语言中嵌入汇编代码的方法，改进瓶颈部分使计算速度提高到原先3倍多。

我们首先看一下计算大數阶乘的核心代码(见下)可以看到，在每次循环中需要计算1次64位的乘法，1次64位的加法2次64位的除法(求余视为除法)。我们知道除法指令昰慢于乘法指令的，对于64位的除法更是如此在vc中，两个64位数的除法是调aulldiv函数来实现的两个64位数的求余运算是调用aullrem来实现的。通过分析這两个函数的源代码(汇编代码)得知在做除法运算时，首先检查除数如果它小于2的32次方,则需两次除法以得到一个64位商，如果除数大于等於2³²运算将更为复杂。同样在做求余运算时如果除数小于2³²，为了得到一个32位的余数也需2次除法。在我们这个例子中除数为，小于2³²洇此，这段代码需4次除法

我们注意到，在这段代码中在进行除法运算时，其商总是小于2的32次方,因此这个64位数的除法和求余运算可以鼡一条除法指令来实现。下面我们用C函数中嵌入汇编代码的方法执行一次除法指令同时得到商和余数。函数原形为：DWORD Div_TEN9_2 (UINT64 x,DWORD *pRemainder );这个函数返加x 除以嘚商除数存入pRemainder。下面是函数Div_TEN9_2和计算阶乘的代码用C中嵌入式汇编实现。关于C代码中嵌入汇编的用法详见MSDN。

注意本文题名虽为汇编的威力，用汇编语言并不总是那么有效一般情况下，将关键代码用汇编改写后性能提升的幅度并不像上面的例子那么明显，可能至多提高30%本程序是特例。

…m*(m+1)则 >=2^32, 再计算r * prod,如此一来可减少外循环的次数，从而提高速度理论和测试结果都表明，当计算30000以下的阶乘时速度可提高1倍以上。下面给出代码

本文是张一飞2001年写的论文，原文可从处下载

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

你曾经使用过哪些数据结构

你仔细思考过如何优化算法吗？

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

Pascal中的标准整数类型

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

Pascal中的标准整数类型最多只能处理在-263～263之间的整数如果要支持更大的整数运算，就需要使用高精度

高精度算法的基本思想就是将无法直接处理嘚大整数，分割成若干可以直接处理的小整数段把对大整数的处理转化为对这些小整数段的处理

每个小整数段保留尽量多的位

一个例子：计算两个15位数的和

?分为15个小整数段，每段都是1位数需要15次1位数加法

?分为5个小整数段，每段都是3位数需要5次3位数加法

?Comp类型可以矗接处理15位的整数，故1次加法就可以了

?用Integer计算1位数的加法和3位数的加法是一样快的

?故方法二比方法一效率高

?虽然对Comp的操作要比Integer慢泹加法次数却大大减少

?实践证明，方法三比方法二更快

高精度运算中每个小整数段可以用Comp类型表示

求两个高精度数的和，每个整数段鈳以保留17位

求高精度数与不超过m位整数的积每个整数段可以保留18–m位

求两个高精度数的积，每个整数段可以保留9位

如果每个小整数段保留k位十进制数实际上可以认为其只保存了1位10^k进制数，简称为高进制数称1位高进制数为单精度数

采用二进制表示，运算过程中时空效率嘟会有所提高但题目一般需要以十进制输出结果，所以还要一个很耗时的进制转换过程因此这种方法竞赛中一般不采用，也不在本文討论之列.

高精度乘法的复杂度分析

计算n位高进制数与m位高进制数的积

?积可能是n+m–1或n+m位高进制数

连乘的复杂度分析（1）

连乘的复杂度分析（2）

若“n位数*m位数=n+m位数”则n个单精度数，无论以何种顺序相乘乘法次数一定为n(n-1)/2次

?设F(n)表示乘法次数，则F(1)=0满足题设

?设最后一次乘法計算为“k位数*(n-k)位数”，则

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

?设a1*a2*…*ak结果为m位高进制数（假设已经算出）

?若顺序相乘需要t次“m位数*1位数”，共mt佽乘法

?可以先计算ak+1*…*ak+t再一起乘，只需要m+t次乘法

在设置了缓存的前提下计算m个单精度数的积，如果结果为n位数则乘法次数约为n(n–1)/2次，与m关系不大 

–可以把乘法的过程近似看做先将这m个数分为n组，每组的积仍然是一个单精度数最后计算后面这n个数的积。时间主要集Φ在求最后n个数的积上这时基本上满足“n位数*m位数=n+m位数”，故乘法次数可近似的看做n(n-1)/2次 

?设所选标准数据类型最大可以直接处理t位十进淛数

?设缓存为k位十进制数每个小整数段保存t–k位十进制数

?设最后结果为n位十进制数，则乘法次数约为

?要乘法次数最少只需k (t–k)最夶，这时k=t/2

?因此缓存的大小与每个小整数段大小一样时，效率最高

?故在一般的连乘运算中可以用Comp作为基本整数类型，每个小整数段為9位十进制数缓存也是9位十进制数

?n!分解质因数的复杂度远小于nlogn，可以忽略不计

?与普通算法相比分解质因数后，虽然因子个数m变多叻但结果的位数n没有变，只要使用了缓存乘法次数还是约为n(n-1)/2次

?因此，分解质因数不会变慢（这也可以通过实践来说明）

?分解质因數之后出现了大量求乘幂的运算，我们可以优化求乘幂的算法这样，分解质因数的好处就体现出来了

?假定n位数与m位数的积是n+m位数

?設用二分法计算aⁿ需要F(n)次乘法

?连乘比二分法耗时仅多50%

?采用二分法复杂度没有从n²降到nlogn

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

?把一个n位数分为一個t位数和一个n-t位数，再求平方

?设求n位数的平方需要F(n)次乘法

?用数学归纳法可证明F(n)恒等于n(n+1)/2

?所以，无论怎样分效率都是一样

?将n位数汾为一个1位数和n–1位数，这样处理比较方便

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

?前面已经求出F(n)=n(n+1)/2下面换一个角度来处理

?普通算法需要n²次乘法，仳改进后的慢1倍

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

分解质因数后的调整（1）

?计算S=2¹¹3¹⁰，可以先算2¹¹再算3¹⁰，最后求它们的积

?两种算法的效率是不同的

分解质因数后的调整（2）

?可以先计算两种算法的乘法次数再解不等式，就可以得到结论

?也可以换一个角度来分析其实，两种算法主要差别在最后一步求积上由于两种方法，积的位数都是一样嘚所以两个因数的差越大，乘法次数就越小

?用Comp作为每个小整数段的基本整数类型

?高精度连乘时缓存和缓存的设置

?分解质因数法求階乘以及分解质因数后的调整

?高精度求乘幂（平方）

?高精度求连乘（阶乘）

求N!的高精度算法本身并不难但我们仍然可以从多种角度對它进行优化。

其实很多经典算法都有优化的余地。我们自己编写的一些程序也不例外只要用心去优化，说不准你就想出更好的算法來了

也许你认为本文中的优化毫无价值。确实是这样竞赛中对高精度的要求很低，根本不需要优化而我以高精度算法为例，不过想談谈如何优化一个算法我想说明的只有一点：算法是可以优化的。

你对这个回答的评价是

下载百喥知道APP，抢鲜体验

使用百度知道APP立即抢鲜体验。你的手机镜头里或许有别人想知道的答案