在计算阶乘之前可以知道阶乘有多大吗？

Question

我正在使用 GMP 来计算非常大的阶乘（例如 234234！）。 在进行计算之前，有什么方法可以知道结果将（或可能）有多少位数字？

Answer 1

您可以使用简单的对数数学转换斯特林近似公式来获得位数：

n!         ~ sqr(2*pi*n) * (n/e)^n
log10(n!)  ~ log10(2*pi*n)/2 + n*log10(n/e)

硬件浮点数学足以满足这一点，这使得它快如闪电。

Answer 2

阶乘的对数可用于计算阶乘数所需的位数：

这可以很容易地转换为算法形式：

//Pseudo-code
function factorialDigits (n) 
  var result = 0;

  for(i = 1; i<=n; i++)
    result += log10(n);

  return result;

Answer 3

斯特林近似给出了 n 大小的近似值！

请参阅 维基百科 推导页面。

Answer 4

它将

nlog(n) - n + log(n(1 + 4n(1 + 2n)))/6 + log(pi)/2

看到主题“增长率”@ http://en.wikipedia.org/wiki/Factorial
斯里尼瓦萨·拉马努金方法

Answer 5

是的，请参阅斯特林近似

它说n！ ~= sqrt(2*Pin)(n/e)^n。 要获得位数，请取 1+log(n!)/log(10)。

Answer 6

大约有四个人提到过斯特林，所以...另一种选择是使用 LUT 存储前 N 个阶乘中每个阶乘的位数。 假设整数有 4 个字节，位数有 4 个字节，则可以将前 1,000,000 个阶乘存储在大约 8MB 中。