在计算它之前,可以知道一个因子有多大吗？

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;