// Обобщенный алгоритм Евклида для поиска наибольшего общего
// делителя gcd = НОД(u,v) целых положительных чисел u и v
// и коэффициентов a и b уравнения a*u + b*v = gcd
// Все числа полагаются типа long
// Подстановки упрощающие запись исходного текста
#define isEven(x) ((x & 0x01L) == 0) // x - четное?
#define isOdd(x) ((x & 0x01L)) // x - нечетное?
#define swap(x,y) (x ^= y, y ^= x, x ^= y) // обмен значений x и y
void GenEuclid(long *u, long *v, long *a, long *b, long *gcd)
{
int k; // Параметр циклов
long a1, b1, g1; // Вспомогательные переменные
// Алгоритм предполагает, что u > v, если u < v, то они переставляются
if (*u < *v) swap(*u, *v);
// Если u = n * 2^k1 или v = m * 2^k2, то перед поиском НОД
// производим сокращение u = u/(2^k), v = v/(2^k),
// где k - минимальное из k1, k2. Показатель k запоминаем.
for (k = 0; isEven(*u) && isEven(*v); ++k){
*u >>= 1; *v >>= 1;
}
// Задание начальных значений
*a = 1; *b = 0; *gcd = *u; a1 = *v; b1 = *u - 1; g1 = *v;
do {
do {
if (isEven(*gcd)){
if (isOdd(*a) || isOdd(*b)){
*a += *v; *b += *u;
}
*a >>= 1; *b >>= 1; *gcd >>= 1;
}
if (isEven(g1) || *gcd < g1){
swap(*a, a1); swap(*b, b1); swap(*gcd, g1);
}
} while (isEven(*gcd));
while(*a < a1 || *b < b1){
*a += *v; *b += *u;
}
*a -= a1; *b -= b1; *gcd -= g1;
} while (g1 > 0);
while (*a >= *v && *b >= *u){
*a -= *v; *b -= *u;
}
// производим умножение коэффициентов уравнения
// на сокращенный ранее множитель 2^k
*a <<= k; *b <<= k; *gcd <<= k;
}
*********** Комментарий к циклам do *****************
Обощенный алгоритм Евклида основан на рекуррентном
вычислении коэфициентов a, b, и gcd уравнения
a*u + b*v = gcd.
В качестве первого приближения в случае, когда u > v,
берем уравнение
(1) 1*u - 0*v = u,
то есть a = 1, b = 0, gcd = u.
В качестве второго уравнения берем очевидное равенство
(2) v*u - (u-1)*v = v,
то есть a1 = v, b1 = u - 1, g1 = v.
Третье уравнение - такое же очевидное равенство
(3) v*u - u*v = 0,
то есть a2 = v, b2 = u, g2 = 0.
Эти уравнения можно складывать, вычитать друг из друга и
и их промежуточных сумм, получая равносильные выражения.
Сложение (1) с (3) означает преобразование
коэффициентов
a = a + v, b = b + u, gcd = gcd.
Вычитание из (1) уравнения (2) означает преобразование
a = a - a1, b = b - b1, gcd = gcd - g1.
Если текущее значение gcd четно, а какой-то из коэффициентов
а или b нечетный, то прибавив (3) к (1), получим возможность
сократить все коэффициенты на 2. Если a и b нечетны, то при
четном gcd значения u и v должны быть также нечетным, так как
одно из них обязательно нечетно из-за предваритеьных делений
на степень 2. Если a нечетно, а b четно, то u обязано быть
четным, тогда v - нечетно.
Как только в результате сокращений правая часть (1) станет
меньше правой части (2) делаем первое уравнение вторым, а
второе - первым путем обмена значений: a c a1, b c b1 и gcd c g1.
Такой же обмен делаем, когда gcd нечетно и его дальнейшее
сокращение на 2 невозможно, а g1 - четно, и можно выполнить
сокращение в уравнении (2).
Если gcd > g1 и gcd нечетно, то дальше сокращать коэффициенты
нельзя - выходим из внутреннего цикла do.
Прибавлением (3) к (1) добиваемся соблюдения уловий a > a1 и
b > b1. Затем, вычитая (2) из (1), стремимся уменьшить
правую часть уравнения (1) приблизив ее к истинному значению
НОД. После каждого вычитания проверяем не равно ли g1 нулю.
В этом случае дальнейшее вычитание уже не приведет к изменению
правой части (1). При g1 = 0 выходим из внешнего цикла do.
В противоположном случае снова входим во внутренний цикл и проверяем
возможность дальнейших сокращений уравнений (1) и (2) на 2.
По окончании циклов, для того чтобы обеспечить a < v и b < u,
вычитаем (2) из (1) столько раз сколько потребуется.
************************************************************
Для того, чтобы проследить последовательность преобразований
для конкретных чисел u и v при запуске программы euclid.exe
установите флажок "Записать протокол вычислений в файл".
При этом все значения a, b, gcd, a1, b1, g1 после каждого
изменения будут записаны в файл logf.txt в текущей папке (каталоге).
Замечание 1. При установленном флажке брать числа u и v большими,
чем 10^7 не рекомендуется.
Замечание2. При просмотре файла logf.txt в Блокноте установите
в меню "Формат" шрифт "Courier New" или любой моноширинный.