java BigInteger扩展欧氏算法递归错误
我正在尝试用大整数做一个扩展的欧几里德算法。 但我一直在犯这样的错误
线程“main”java中出现异常。算术异常:BigInteger除以零
我在谷歌上搜索,它说我可能会因为非整数部分而出错
我该如何解决这个问题
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 };
}
}
# 1 楼答案
以下是Github副驾驶(经我验证)生产的工作变体:
注意:当
p=0
时,它返回q
,反之亦然与您的代码不同的是,它检查
q != 0
(在某个点上必然变成0),而不是p != 0
测试: