BigInteger Extended Euclidean Algorithm recursion error

Question

I am trying to make an extended euclidean algorithm with the BigInteger. but I am keeping getting the error that

Exception in thread "main" java.lang.ArithmeticException: BigInteger divide by zero

I searched on google and it says that I might get an error because of the noninteger division

How should I solve this problem?

public static void main(String[] args) throws Exception{

    BigInteger ex1 = new BigInteger("9");
    BigInteger ex2 = new BigInteger("13");
    //if(eA.gcd(eB).equals(BigInteger.ONE))
//  {
        BigInteger[] val = gcd(ex1,ex2);
        
        System.out.println(val[1]);
        System.out.println(val[2]);
//  }
}

   // Returns a triple {d, a, b} such that d = a*p + b*q

   static BigInteger[] gcd(BigInteger p, BigInteger q) {
          if (p.equals(BigInteger.ZERO))
             return new BigInteger[] { p, BigInteger.valueOf(1), BigInteger.valueOf(0) };

          BigInteger[] vals = gcd(q, p.remainder(q));
          BigInteger d = vals[0];
          BigInteger a = vals[2];
          BigInteger b = vals[1].subtract((p.divide(q)).multiply(vals[2]));
          return new BigInteger[] { d, a, b };
       }
}

There is no way to do "noninteger" division with BigInteger, and certainly no noninteger division is present in your code. The error occurs in the line BigInteger[] vals = gcd(q, p.remainder(q)); because q eventually becomes 0. By checking the gcd identities you can verify that gcd(0, a) = abs(a). Your code computes the gcd(0, a) as 0, which is wrong. — President James K. Polk
– President James K. Polk, Commented Nov 1, 2021 at 20:13
q must have been zero, as remainder and divide may complain. That might happen for an older p and q with p.remainder(q) being zero. — Joop Eggen
– Joop Eggen, Commented Nov 1, 2021 at 20:21

Aivean · Accepted Answer · 2021-11-01 21:19:04Z

0

Here is the working variant, produced by Github Copilot (verified by me):

// Returns a triple {d, a, b} such that d = a*p + b*q
static BigInteger[] extendedEuclidean(BigInteger p, BigInteger q) {
    BigInteger[] val = new BigInteger[3];

    if (q.equals(BigInteger.ZERO)) {
        val[0] = p;
        val[1] = BigInteger.ONE;
        val[2] = BigInteger.ZERO;
    } else {
        BigInteger[] val2 = extendedEuclidean(q, p.mod(q));
        val[0] = val2[0];
        val[1] = val2[2];
        val[2] = val2[1].subtract(p.divide(q).multiply(val2[2]));
    }

    return val;
}

Note: when p=0 it returns q and vice versa.

The difference from your code, is that it checks that q != 0 (which is bound to become 0 at some point), instead of p != 0.

Tests:

input: 9, 13
d = 1, a = 3, b = -2

input: 2, 15
d = 1, a = -7, b = 1

input: 9, 12
d = 3, a = -1, b = 1

input: 0, 10
d = 10, a = 0, b = 1

input: 0, 0
d = 0, a = 1, b = 0

input: 1, 1
d = 1, a = 0, b = 1

input: 3, 0
d = 3, a = 1, b = 0

edited Nov 1, 2021 at 21:19

answered Nov 1, 2021 at 20:36

Aivean

10.9k28 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

njzk2 Over a year ago

seems to me that it would be more useful to simply point out that if (p.equals(BigInteger.ZERO)) should be testing q instead of p, rather than post a complete function

Collectives™ on Stack Overflow

BigInteger Extended Euclidean Algorithm recursion error

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related