如何高效计算n!前15位（n≤1e9）？Stirling近似精度不足求助

原代码问题分析 #

1. 斯特林公式应用错误：混淆了自然对数与常用对数的转换逻辑，且未加入必要的修正项，一阶斯特林近似的误差直接导致仅前4位结果正确。
2. 冗余字符串转换：频繁将数值转为字符串再转Decimal，引入不必要的精度损失。
3. 幂运算逻辑混乱：直接对大指数执行幂运算，进一步放大了精度误差。

正确实现思路 #

要达到前15位的精度，需使用带修正项的斯特林公式计算log10(n!)，再通过拆分对数的整数与小数部分规避大指数运算：

1. 带修正项的斯特林公式常用对数形式：
   $$\log_{10}(n!) \approx \log_{10}(\sqrt{2\pi n}) + n \cdot \log_{10}(n/e) + \frac{1}{12n\ln10} - \frac{1}{360n^3\ln10}$$
2. 将log10(n!)拆分为整数部分k和小数部分f，则n! = 10^k * 10^f，其中10^f处于[1,10)区间。
3. 计算10^f * 10^14并取整，即可得到前15位数字。

代码实现 #

from decimal import Decimal, getcontext
import math

getcontext().prec = 50  # 精度足够覆盖前15位需求

n = int(input())
if n in (0, 1):
    print("1")
    exit()

ln10 = Decimal(math.log(10))
pi = Decimal(math.pi)
e = Decimal(math.e)

# 计算斯特林公式核心项
log_core = (Decimal(2 * pi * n).sqrt()).log10() + Decimal(n) * (Decimal(n).log10() - e.log10())
# 添加修正项抵消一阶斯特林的误差
correction = Decimal(1) / (Decimal(12) * Decimal(n) * ln10) - Decimal(1) / (Decimal(360) * Decimal(n)**3 * ln10)
log10_fact = log_core + correction

# 拆分对数的整数与小数部分
integer_part = int(log10_fact)
fractional_part = log10_fact - integer_part

# 计算前15位数字
leading_digits = Decimal(10) ** fractional_part
leading_digits *= Decimal(10)**14
print(f"{int(leading_digits):015d}")

说明 #

• 修正项的加入将log10(n!)的精度提升至1e-15以上，完全满足前15位的精度要求。
• 拆分对数部分避免了直接计算超大数阶乘，运算效率极高，n=1e9时计算耗时远小于1秒。
• 无需过度提升Decimal精度，prec=50已足够覆盖所有计算误差。

内容的提问来源于stack exchange，提问作者ishandutta2007