algorithm - 计算表达式长度而不计算表达式本身

Question

我需要在不计算表达式本身的情况下计算复杂表达式的十进制长度(包含阶乘)。 例如: ( 400!/( 100! * 300!) ) 的十进制长度 任何可以完成任务或数学公式的方法都可能有用。 谢谢。

Answer 1

如果近似值足够，我们可以使用斯特林近似值:

n! ~ sqrt(2×πn)×(n/e)ⁿ

这个结果直接对我们的目标来说不是很有趣，但是我们可以使用log10来获取位数:

log₁₀(n!) ~ log₁₀(sqrt(2×πn))+n×log₁₀(n/e )

现在我们可以计算a!/(b!×c!)的位数，使用:

log(a!/(b!×c!)) = log(a!)-log(b!)-log(c!)

等于:

log(a!/(b!×c!)) = log₁₀(sqrt(2×πa))+a×log₁₀(a/e )-log₁₀(sqrt(2×πb))-b×log₁₀(b/e)-log₁₀(sqrt(2 ×πc))-c×log₁₀(c/e)

而一个数n的位数大概是⌊log(n)⌋+1。

例如在 Python 中我们可以近似:

from math import log10, pi, e, sqrt, floor

def approx_fac_log10(n):
    return log10(sqrt(2.0*pi*n))+n*log10(n/e)

def approx_length(a,b,c):
    return 1+floor(approx_fac_log10(a)-approx_fac_log10(b)-approx_fac_log10(c))

对于你的公式，我们得到:

>>> approx_length(400,100,300)
97

如果我们计算结果，我们得到:

>>> factorial(400)//(factorial(100)*factorial(300))
2241854791554337561923210387201698554845411177476295990399942258896013007429693894018935107174320
>>> factorial(400)/(factorial(100)*factorial(300))
2.2418547915543375e+96

如果我们将结果转换为字符串，然后获取该字符串的长度，我们将得到:

>>> len(str(factorial(400)//(factorial(100)*factorial(300))))
97

所以近似值是正确的:结果确实有 97 位。

您可以通过在 Stirling 近似 中使用更多 项来提高近似的质量。最终，如果你采用无限数量的项，你确实会准确地计算出结果: