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

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位。

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

Answer 2

数字 x 的位数是 floor(log(x)) + 1： a proof on math.stackexchange

因此，根据您的效率需求，简单的加减对数方法可能就足够了。

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

Compute expression length without computing expression itself

algorithm

math

formula