java - 计算第 n 个阶乘

Question

我正在编写一个实现以下表达式的函数 (1/n!)*(1!+2!+3!+...+n!)。

函数被传递参数 n 并且我必须将上面的语句作为 double 返回，截断到小数点后第 6 位。我遇到的问题是阶乘值变得太大以至于变成无穷大(对于较大的 n 值)。

这是我的代码:

public static double going(int n) {
   double factorial = 1.00;
   double result = 0.00, sum = 0.00;

   for(int i=1; i<n+1; i++){
     factorial *= i;
     sum += factorial;
   }
   //Truncate decimals to 6 places
   result = (1/factorial)*(sum);
   long truncate = (long)Math.pow(10,6);
   result = result * truncate;
   long value = (long) result;

   return (double) value / truncate;
}

现在，上面的代码在 n=5 或 n=113 时工作正常，但任何高于 n=170 和我的 factorial 和 sum 表达式都变成无穷大。由于数字呈指数增长，我的方法是否行不通？以及如何计算不会对性能产生太大影响的非常大的数字(我相信 BigInteger 在查看类似问题时速度非常慢)。

Answer 1

您无需评估单个阶乘即可解决此问题。

您的公式简化为更简单的计算方式

1!/n! + 2!/n! + 3!/n! + ... + 1

除了第一项和最后一项，很多因素实际上抵消了，这将有助于最终结果的精度，例如3!/n! 您只需将 1/4 乘以 1/n。您绝不能做的是评估阶乘并将它们相除。

如果 15 位十进制数字的精度是可以接受的(这似乎来自您的问题)，那么您可以用 float 对其进行评估，首先添加小项。当您开发算法时，您会注意到这些术语是相关的，但要非常小心地利用它，因为您可能会引入实质性的不精确性。 (如果我是你，我会将其视为第二步。)

---

这是一个原型(prototype)实现。请注意，我首先将所有单独的项累积在一个数组中，然后我先从较小的项开始对它们求和。我认为从最后一项 (1.0) 开始并向后计算在计算上更准确，但对于收敛速度如此之快的系列来说，这可能不是必需的。让我们彻底完成这项工作并分析结果。

private static double evaluate(int n){                        
    double terms[] = new double[n];
    double term = 1.0;
    terms[n - 1] = term;
    while (n > 1){            
        terms[n - 2] = term /= n;
        --n;
    }        
    double sum = 0.0;
    for (double t : terms){
        sum += t;
    }        
    return sum;        
}

您可以看到前几项很快变得无关紧要。我认为您只需要几项就可以计算出 float double 容差的结果。让我们设计一个算法，在达到该点时停止:

---

最终版本。看起来该系列收敛得如此之快，以至于您无需担心首先添加小项。所以你最终得到了绝对美丽

 private static double evaluate_fast(int n){        
    double sum = 1.0;
    double term = 1.0;
    while (n > 1){
        double old_sum = sum;
        sum += term /= n--;
        if (sum == old_sum){
            // precision exhausted for the type
            break;
        }
    }                
    return sum;        
}

如您所见，不需要 BigDecimal &c，当然也不需要计算任何阶乘。