Search code examples
javastack-overflowbigintegergreatest-common-divisor

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

I implemented my own Class Fraction, where I have a BigInteger numerator object and BigInteger denominator object. Whenever I call the constructor of a Fraction object, it parses the numerator and denominator from the argument and simplifies the fraction. The problem I am having is that I am getting stack overflow exception when calling gcd(biginteger numerator, biginteger denominator) for really big numbers. I want to be able to get the gcd of really big BigInteger objects.

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

The error I'm getting is:

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)

And A lot more of the Fraction.Fraction.gcd(Fraction.java:71).

Solution

  • The problem is that you have coded Euclid's algorithm incorrectly. The algorithm is this:

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

    That's not what your code does.

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

    The comments above by @clemens and @EJP are apropos.

    The comment by @AlexF is only relevant for extremely large numbers. Euclid's algorithm converges rapidly. (See https://math2.uncc.edu/~frothe/Euclidextendpnew.pdf for the gory details.)