如何在不出现 stackoverflow 异常的情况下计算真正大的 BigInteger 数字的 GCD？

Question

我实现了自己的 Class 分数，其中我有一个 BigInteger 分子对象和 BigInteger 分母对象。每当我调用 Fraction 对象的构造函数时，它都会从参数中解析分子和分母并简化分数。我遇到的问题是，在为非常大的数字调用 gcd(biginteger numerator, biginteger denominator) 时出现堆栈溢出异常。我希望能够获得真正大的 BigInteger 对象的 gcd。

private BigInteger gcd(BigInteger a, BigInteger b)
{
        if(a.mod(b).toString().equals("0"))
            return b;
        return gcd(b, a.mod(b));
}

我得到的错误是：

Exception in thread "main" java.lang.WhosebugError
    at java.math.MutableBigInteger.divideKnuth(MutableBigInteger.java:1203)
    at java.math.MutableBigInteger.divideKnuth(MutableBigInteger.java:1163)
    at java.math.BigInteger.remainderKnuth(BigInteger.java:2167)
    at java.math.BigInteger.remainder(BigInteger.java:2155)
    at java.math.BigInteger.mod(BigInteger.java:2460)
    at Fraction.Fraction.gcd(Fraction.java:69)
    at Fraction.Fraction.gcd(Fraction.java:71)
    at Fraction.Fraction.gcd(Fraction.java:71)
    at Fraction.Fraction.gcd(Fraction.java:71)

还有很多 Fraction.Fraction.gcd(Fraction.java:71).

Answer 1

问题是您的编码 Euclid's algorithm 不正确。算法是这样的：

gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b)

这不是您的代码所做的。

// This is supposed to implement the first term ... but it doesn't
if (a.mod(b).toString().equals("0"))
        return b;

以上@clemens 和@EJP 的评论是恰当的。

@AlexF 的评论仅适用于非常大的数字。欧几里得算法收敛很快。（有关详细信息，请参阅 https://math2.uncc.edu/~frothe/Euclidextendpnew.pdf。）

如何在不出现 stackoverflow 异常的情况下计算真正大的 BigInteger 数字的 GCD？

How can I calculate GCD of really large BigInteger numbers without getting a stackoverflow exception?

java

stack-overflow

biginteger

greatest-common-divisor