java - 如何计算非常大的 BigInteger 数字的 GCD 而不会出现 stackoverflow 异常？

Question

我实现了自己的分数类，其中有一个 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.StackOverflowError
    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。)