BigInteger 扩展欧几里得算法递归错误

Question

我正在尝试使用 BigInteger 制作一个扩展的欧几里得算法。但我一直收到

的错误

线程“main”中的异常java.lang.ArithmeticException：BigInteger 除以零

我在 google 上搜索，它说我可能会因为非整数除法而出错

我该如何解决这个问题？

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 };
       }
}

Answer 1

这是工作变体，由 Github Copilot 制作（由我验证）：

// 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;
}

注：当p=0时returnsq反之

与您的代码的不同之处在于，它检查 q != 0（在某些时候必然会变为 0），而不是 p != 0。

测试：

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

BigInteger 扩展欧几里得算法递归错误

BigInteger Extended Euclidean Algorithm recursion error

java

biginteger

modulo

euclidean-algorithm