正整数的阶乘(Factorial)是小于或等于该数的所有正整数的乘积,若正整数为 N,用 N! 来表示 N 的阶乘。至于 0! 是阶乘的特例,它被定义为 1。阶乘的运算具有递归(recursion)概念,常作为学习程序逻辑的材料,而这篇文章将会说明阶乘相关的程序计算。

阶乘(Factorial)函数

计算某数(正整数)的阶乘,是指计算所有小于及等于该数的正整数的积。方程式表示如下:

#{{{
\begin{alignedat}{2}
Factorial(n) &{}={}&& n! \\
&{}={}&& 1 \times 2 \times 3 \times \dotsb \times (n - 1) \times n \\
&{}={}&& [1 \times 2 \times 3 \times \dotsb \times (n - 1)] \times n \\
&{}={}&& n \times (n - 1)!
\end{alignedat}
}}}#

且定义

#{{{
0! = 1
}}}#

我们可以很直觉地写出如下的递归程序:

阶乘的数值大小成长得很快,以下分别列出不同比特的无号整数所能保存的最大阶乘值:

  • 32 比特:12!
  • 64 比特:20!
  • 128 比特:34!
  • 256 比特:57!
非递归的阶乘函数

以递归的方式调用函数,每次都需要创建新的堆栈框(Stack Frame),堆栈框的数量太多就会导致堆栈溢出(Stack Overflow),所以在实际应用上我们会比较偏好不去使用递归函数。上面的阶乘递归函数,可以参考以下文章来转成非递归的版本:

转换后的非递归阶乘函数如下:

阶乘的大数运算

要实作阶乘的大数运算,只要会乘法的大数运算即可。可以参考以下文章来了解加减乘除的大数运算:

N! 有几位数?

前面提到阶乘的数值大小成长得很快,那它到底会有几位数呢?

要求出数字 #{{N}}# 有几位数,我们可以用下面这个公式来直接算出:

#{{{
\lfloor {log_{10}N} \rfloor + 1
}}}#

所以,#{{N!}}# 有几位数,可以这样计算:

#{{{
\begin{alignedat}{2}
&&&\lfloor {logN!} \rfloor + 1 \\
&{}={}&& \lfloor {log(1 \times 2 \times 3 \times \dotsb \times N)} \rfloor + 1 \\
&{}={}&& \lfloor {log1 + log2 + log3 + \dotsb + logN} \rfloor + 1
\end{alignedat}
}}}#

程序实作如下:

由于 #{{log1 = 0}}#,所以计次循环从 2 开始。

上面程序的时间复杂度为 #{{O(N)}}#,其实还可以更快,快到 #{{O(1)}}#。

史特灵公式(Stirling's formula),是用来计算阶乘近似值的公式,如下:

#{{{
n! \approx {\sqrt{2 \pi n}}{({n \over e})}^n
}}}#

虽然史特灵公式只是近似公式,但要拿它来计算阶乘的位数已经足够准确了,只不过 #{{N}}# 小于 #{{2}}# 的时候要另外处理(#{{0!}}# 和 #{{1!}}# 都是 #{{1}}#,只有 1 位数)。位数的计算方式如下:

#{{{
\begin{alignedat}{2}
&&&\lfloor {logN!} \rfloor + 1 \\
&{}\approx{}&& \lfloor {log({\sqrt{2 \pi N}}{({N \over e})}^N)} \rfloor + 1 \\
&{}={}&& \lfloor { {1 \over 2}log(2 \pi N) + Nlog({N \over e}) } \rfloor + 1 \\
&{}={}&& \lfloor { {1 \over 2} \times [log(2 \pi) + logN] + N \times [logN - log(e)] } \rfloor + 1
\end{alignedat}
}}}#

程序实作如下:

N! 的尾端有几个 0?

阶乘是连续的正整数相乘所得的结果,什么情况下尾端会多出一个 0?那就是 #{{2 \times 5}}# 的时候啦!N! 的质因数中有几组 2 和 5,N! 的尾端就会有几个 0。由于 2 的数量肯定不会比 5 的数量少,所以我们只需要去计算 N! 在质因数分解后有几个 5,就是尾端的 0 的数量。

以下公式可以算出 N! 在质因数分解后有几个 5:

#{{{
\lfloor {N \over 5} \rfloor + \lfloor {N \over 25} \rfloor + \lfloor {N \over 125} \rfloor + \dotsb + \lfloor {N \over 5^i} \rfloor, 5^i \leq N
}}}#

例如,#{{4! = 24}}#,尾端有 0 个 0;#{{5! = 120}}#,尾端有 1 个 0;#{{9! = 362880}}#,尾端有 1 个 0;#{{10! = 3628800}}#,尾端有 2 个 0;#{{24! = 620448401733239439360000}}#,尾端有 4 个 0;#{{25! = 15511210043330985984000000}}#,尾端有 6 个 0。

在用程序实作之前,可以将上面的式子写成以下这样,会更容易实作:

#{{{
\lfloor {N \over 5} \rfloor + \lfloor {{N \over 5} \over 5} \rfloor + \lfloor {{{N \over 5} \over 5} \over 5} \rfloor + \dotsb
}}}#

当最外层的分子小于 5 时,就可以不用再加下去了,因为只会取整数部份来相加。

程序实作如下: