计算第 n 个阶乘

Question

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

函数通过参数 n 并且我必须 return 上面的语句作为双精度语句，截断到小数点后第 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 位十进制数字的精度（这似乎来自您的问题），那么您可以用浮点数对其进行评估，首先添加小项。在开发算法时，您会注意到这些术语是相关的，但要非常小心地利用它，因为您可能会引入 material 不精确。（如果我是你，我会将其视为第二步。）

这是一个原型实现。请注意，我首先将所有单独的项累积在一个数组中，然后我先从较小的项开始对它们求和。我认为从最后一项 (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;        
}

您可以看到前几项很快变得无关紧要。我认为您只需要几项就可以计算出浮点数容差的结果 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，当然也不需要计算任何阶乘。

Answer 2

您可以像这样使用 BigDecimal：

public static double going(int n) {
    BigDecimal factorial = BigDecimal.ONE;
    BigDecimal sum = BigDecimal.ZERO;

    BigDecimal result;

    for(int i=1; i<n+1; i++){
        factorial = factorial.multiply(new BigDecimal(i));
        sum = sum.add(factorial);
    }
    //Truncate decimals to 6 places
    result = sum.divide(factorial, 6, RoundingMode.HALF_EVEN);

    return result.doubleValue();
}

计算第 n 个阶乘

Calculating the nth factorial

java

double

factorial

truncation