» 1000! 有几位数字 Zero Sound

1000! 有几位数字

十月 7, 2007 at 11:04 上午 | In Default |

据说是微软的面试题。我看到这个题目的第一个反应就是：写个程序计算一下。用python来写，非常简单：

1 def fac_digits(n):
2   fac = 1
3   for i in xrange(1, n + 1):
4     fac *= i
5   return len(str(fac))
6 
7 fac_digits(1000)

虽然python以缓慢著称，在快节奏的当代社会中堪称另类，但算1000!还是相当快的，结果是2568。要感谢python已经帮我们实现了高精度整数运算，如果要用C/C++来写，就必须自己编写高精度乘法了。

尽管已经算出来了，但方法略嫌暴力。如果大学数学还没全还给老师，肯定还记得一个鼎鼎有名的Stirling Approximation，专门求n!，在概率统计里用得很多：

$n!\sim \sqrt{2\pi }n^{n+\frac{1}{2}}e^{-n}$

算右边表达式的对数，得到2567.6046，说明实际上应该有2567+1=2568位。

可能有人会觉得Stirling公式毕竟只是个近似，所以我抄了下面这个包含更多的高阶项的展开式，可以让我们的结果更有说服力一些：

$n!=\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}\Big(1+\dfrac{1}{12n}+\dfrac{1}{288n^2}-\dfrac{139}{51840n^3}+\cdots\Big)$

顺带提一下Stirling公示的证明，是从Wikipedia上看得，用Euler-Maclaurin公式给出n!对数的渐近展开：

$\ln n!=\Big(n+\dfrac{1}{2}\Big)\ln n-n+\displaystyle\sum_{k=1}^{\infty}\dfrac{B_{k+1}(-1)^{k+1}}{k(k+1)n^k}$

如果只想要头两项，可以有简单一点的，或者说不需要Euler-Maclaurin公式的证明，虽然我不认为Euler-Maclaurin公式是多么高深的工具。

不知道除了暴力计算和Stirling公式之外，还有什么更简单或初等的方法来求出1000!的位数？

阅读(1052 次)

share this post These icons link to social bookmarking sites where readers can share and discover new web pages.