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

Question

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

score 12 · Accepted Answer

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

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

硬件浮点数学就足够了，这使它快如闪电。

score 7 · Accepted Answer

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

登录！

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

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

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

  return result;

score 3 · Accepted Answer

3

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

$替代文字$

有关推导，请参见Wikipedia页面。

于 2009-07-11T07:37:59.223 回答

score 2 · Accepted Answer

这将是

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

请参阅主题“增长率”@ http://en.wikipedia.org/wiki/Factorial Srinivasa Ramanujan 方法

score 1 · Accepted Answer

是的，请参见斯特林近似

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

score 1 · Accepted Answer

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

6 回答 6