Что именно происходит внутри рекурсии расширенного евклидового алгоритма в c ++?
Я знаю, что такое расширенный евклидов алгоритм и почему он используется в программировании. Это очень полезный алгоритм для нахождения обратного по модулю числа. Я знаю, как реализовать это в C ++, и это то, как я реализую это ниже в C ++.
typedef pair<int, int> pii;
#define x first
#define y second
pii extendedEuclidean(int a, int b)
{
if(b==0)
return {a,0};
else {
pii d = extendedEuclidean(b, a%b);
return {d.y, d.x - (d.y*(a/b))};
}
}
Теперь, если я хочу найти обратное по модулю число для примера 13, где mod, например, 1000007, то я просто вызываю эту функцию
pair<int, int> res = extendedEuclidean(13, 1000007);
Тогда результат
res.first
Мой вопрос: почему и что именно происходит внутри этой рекурсии? А также почему это дает правильный результат.
Н.Б .: здесь gcd (a, b) должно быть 1.
Решение
Евклидов алгоритм вычисляет наибольший общий делитель пары чисел (a, b) (при условии, что a>b). Он использует наблюдение, что любой общий делитель a а также b также является делителем a-b, Вот почему:
Позволять d быть делителем. Затем, a может быть выражено как a=d*k для целого числа k а также b=d*l для целого числа l, Затем, a-b=d*k-d*l=d*(k-l), k-l снова целое число Таким образом, d должен быть делителем a-b,
Алгоритм вычитает меньшее число из большего как можно чаще. Это часть a%b, Например. если a = 25 а также b = 7, a%b=4 это то, что вы получаете после вычитания b 3 раза от a, После этого новый a будет меньше чем b, Поэтому вы меняете оба числа. Это та часть, где вы называете рекурсию: extendedEuclidean(b, a%b);
Расширенный евклидов алгоритм дает немного больше. Кроме того, он рассчитывает два числа x а также yтакой, что gcd(a, b) = x * a + y * b, Вот как это делается:
На последней итерации вы получите a'=gcd а также b'=0, Таким образом, у вас есть gcd=a' * 1 + b' * 0, где 1 а также 0 являются x' а также y'соответственно. Предположим, что значения в предыдущей итерации были a'' а также b'', Тогда мы знаем, что a'=b'' а также b'=a'' % b'', С этим мы находим, что b'=a''-(a''/b'')*b'' (вычитайте как можно чаще). И мы можем изменить
gcd = a' * x' + b' * y'
gcd = b'' * x' + (a''-(a''/b'')*b'') * y'
= a'' * y' + b'' * (x' - y' * (a''/b''))
Следовательно, новый x''=y' а также y''=x' - y' * (a''/b''), Это ваше возвращение return {d.y, d.x - (d.y*(a/b))};,
Пример:
Позволять a=25, b=7, Первый проход вычисляет столбцы a а также b (сверху вниз). Это объясняет рекурсивные вызовы. Второй проход вычисляет столбцы x а также y (снизу вверх). Это составляет для отчетов о возврате:
a | b | x | y | means
----+--------------+------------------------------+---------------------
25 | 7 | 2 | -1 - 2 * (25/7) = -7 | 1 = 2 * 25 - 7 * 7
7 | 25 % 7 = 4 | -1 | 1 + 1 * (7/4) = 2 | 1 = (-1) * 7 + 2 * 4
4 | 7 % 4 = 3 | 1 | 0 - 1 * (4/3) = -1 | 1 = 1 * 3 - 1 * 3
3 | 4 % 3 = 1 | 0 | 1 - 0 * (3/1) = 1 | 1 = 0 * 3 + 1 * 1
1 | 3 % 1 = 0 | 1 | 0 | 1 = 1 * 1 + 0 * 0
Итак, вы получаете 1 = 2 * 25 - 7 * 7 где 2 является результатом .first а также -7 является результатом .second, Если мы в mod 25, это сводится к:
1 == 2 * 0 - 7 * 7
1 == -7 * 7
Следовательно, -7 == 18 (который result.second) является мультипликативным обратным к 7 (mod 25), Обратите внимание, что я поменял местами ввод, чтобы избежать ненужной первой итерации. В противном случае это result.first,
Другие решения
Других решений пока нет …