由于大数字导致的 Java CombinatoricsUtils.binomialCoefficient（）算术错误-解网

问：

当我尝试使用 Java Apache Math3 方法计算大数的组合时，例如 334 选择 179，我收到一个CombinatoricsUtils.binomialCoefficient()Exception in thread "main" org.apache.commons.math3.exception.MathArithmeticException: arithmetic exception

我知道这是由于大量（很可能是）造成的，所以我检查了几个 StackOverflow 帖子来修复它，但没有成功。

我的原始代码：

public static void testCombinations(){
    long test = CombinatoricsUtils.binomialCoefficient(334, 179);
    System.out.println(test);
}

我修改了它以适应大数字：

public static void testCombinations(){
    BigInteger test = BigInteger.valueOf(CombinatoricsUtils.binomialCoefficient(334, 179));
    System.out.println(test);
}

但是，这并不能解决问题。我使用标准计算器检查了这个例子的值^{，n C}_r（334,179），它是 6.45769855268175x10^98。我不需要这么长的数字，也许是数字的开头，也许前 5 或 10 个字符就足够了。但可能是计算过程中产生的误差。我应该如何处理这个问题？

更新：

我进一步修改了我的代码：

public static void testCombinations(){
    int n = 344;
    int k = 179;
    double test;
    test = (long) CombinatoricsUtils.binomialCoefficientDouble(n, k);
    System.out.println(test);
}

但是，这只能不抛出异常。结果值（9.223372036854776E18）始终相同，即使数字同样大，例如 358 选择 179。我假设这个值是 long 的最大值。所以，还没有解决方案。

java 算法异常 math bigint

您无法仅通过更改类型来从不存在的现有值中获得精度。如果计算，结果将溢出一个 32 位整数，并且无法对结果进行计算，从而获得正确的结果，原因很简单，因为还有许多其他值会溢出到相同的结果。你不能把一堆汉堡包变成一头牛。int x = 1000000000 * 1000000000int

0赞 Thend 3/21/2023

@KarlKnechtel是的，我知道并同意你的看法。最好的方法是用一些数学方法来保持数量级的值。我特别想知道其他人在这种情况下会怎么做。也许他们以某种方式转换输入数字以获得数量级的类似结果。很高兴知道。

0赞 Karl Knechtel 3/21/2023

你在寻找实际的数学算法吗？您需要确切的结果吗？如果是这样，这究竟是编程问题，而不是数学问题？

1赞 Robert Dodier 3/22/2023

听起来你不需要确切的结果。如果是这样，您可以将二项式写成阶乘的比率，并使用斯特林近似来近似阶乘。另一种方法是使用二项式系数的对数 - 寻找一个对数伽玛函数并据此计算对数（二项式），或者仅根据对数项和与对数项的差值计算对数（二项式）。

1赞 Robert Dodier 3/22/2023

@KarlKnechtel 我不知道你是否意识到这一点，但你的评论有一种对抗的语气，并没有将讨论推向建设性的结论。

答：

0赞 Dave 3/21/2023 #1

由于您所需要的只是大小，这可能会有所帮助。

ceiling（log（n））是 n > 1 中的位数

所以 n 中的位数！是关于天花板（log（n） + log（n-1） + ...）

因此，对于 choose（n，k）中的位数：

我让 r = n-k 并假设 k >= r。

选择中的数字（n， k） ~ ceiling（log（n） + log（n-1） + ... + log（k+1） - log（r） - log（r-1） - ... - log（2））

^^ 从 n 到 k+1，我们得到的数字只在 choose（n， k）的分子中。从 k 到 r+1，我们有分母中的数字一次（所以用分子取消），从 r 向下，我们在分母中有两次数字（所以净除法）。

下面是 Ruby 的实现：

def choose_est(n, k)
  r = n - k
  coefficient = 1.0
  logsum = 0.0
  n.downto(k+1) do |val|
    logsum += Math.log(val, 10)
    coefficient *= val
    coefficient /= 10**(Math.log(coefficient,10).floor)
  end
  r.downto(2) do |val|
    logsum -= Math.log(val, 10)
    coefficient /= val
    coefficient /= 10**(Math.log(coefficient,10).floor)
  end
  coefficient /= 10**(Math.log(coefficient, 10).floor)
  puts "coefficient = #{coefficient}, digits = #{logsum.ceil}, exact = #{choose(n, k)}"
end

一些示例结果：

> choose_est(25, 10)
coefficient = 3.2687599999999963, digits = 7, exact = 3268760

> choose_est(334, 179)
coefficient = 6.457698552681728, digits = 99, exact = 645769855268174723155002700285292878609673825371233277541117250760336409272009018138269061870226976

>choose_est(10000, 444)
coefficient = 2.1387299915901736, digits = 788

相同的 Java 代码：

import java.lang.Math;

public class ChooseEstimator {
    public static void chooseEst(int n, int k) {
        int r = n - k;
        double coefficient = 1.0;
        double logsum = 0.0;
        for (int val = n; val > k; val--) {
            logsum += Math.log10(val);
            coefficient *= val;
            coefficient /= Math.pow(10, Math.floor(Math.log10(coefficient)));
        }
        for (int val = r; val >= 2; val--) {
            logsum -= Math.log10(val);
            coefficient /= val;
            coefficient /= Math.pow(10, Math.floor(Math.log10(coefficient)));
        }
        coefficient /= Math.pow(10, Math.floor(Math.log10(coefficient)));
        System.out.println("coefficient = " + coefficient + ", digits = " + (int)Math.ceil(logsum));
    }

    
    public static void main(String[] args) {
        chooseEst(25, 10);
    }
}

感觉更自然了！不好意思;原谅我。我使用 log10 来计算数字（logsum），因为我们想要以 10 为基数的数字。即，这个语句：“ceiling（log（n）） is the number of number in n > 1” 对于以 10 为底的对数，而不是自然对数，这句话是正确的。

0赞 Thend 3/23/2023

我只是好奇，:)非常感谢您的帮助！

1赞 btilly 3/22/2023 #2

这是一种简单的方法，在进行计算的同时不断乘法和除法以保持（希望）在 .double

public static double binomialApproximation(int n, int m) {
    double k = m;
    if (n - m < m) {
        k = n - m;
    }
    
    double answer = 1.0;
    while (0 < k) {
        answer *= n / k;
        n--;
        k--;
    }
    return answer;
}

请注意，最大值为。如果你最终需要比这更大的数字，那么你需要使用类似 or 的东西，并注意精度等。double1.79769313486231570e+308dBigDoubleBigDecimal

上一个：Barplot - 堆叠 ggplot 百分比 barplot 起始值不是 0%

下一个：JFXtras CalendarPicker MouseEvent 行为不正常

由于大数字导致的 Java CombinatoricsUtils.binomialCoefficient（） 算术错误

Java CombinatoricsUtils.binomialCoefficient() arithmetic error due to large numbers

评论

评论

由于大数字导致的 Java CombinatoricsUtils.binomialCoefficient（）算术错误