Ошибка рекурсии расширенного эвклидова алгоритма BigInteger

#java #biginteger #modulo #euclidean-algorithm

Вопрос:

Я пытаюсь создать расширенный евклидов алгоритм с помощью BigInteger. но я продолжаю получать ошибку, которая

Исключение в потоке «основной» java.lang.Исключение ArithmeticException: большой делитель на ноль

Я поискал в 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 };
       }
}

1. С помощью BigInteger невозможно выполнить «неинтегрированное» разделение, и, конечно же, в вашем коде нет неинтегрированного разделения. Ошибка возникает в строке BigInteger[] vals = gcd(q, p.remainder(q)); , потому q что в конечном итоге становится 0. Проверив идентификаторы gcd , вы можете убедиться, что gcd(0, a) = abs(a). Ваш код вычисляет gcd(0, a) как 0, что неверно.

2. q должно быть, было ноль, как remainder и divide может жаловаться. Это может произойти для более старых p и q с p.remainder(q) нулевым значением.

3. p.divide(q) почему вы уверены, что q это никогда не 0?

Ответ №1:

Вот рабочий вариант, созданный вторым пилотом Github (проверен мной):

 // 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 он возвращается q и наоборот.

Отличие от вашего кода в том, что он проверяет это 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