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 };
}
}
CodePudding user response:
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