Алгоритм Евклида
Алгоритм А. (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий делитель.
A1. [v = 0?] Если v = 0, то выполнение алгоритма заканчивается, а в качестве результата возвращается число u.
A2. [Взять u mod v.] Присвоить r ¬ u mod v, u ¬ v, v ¬ r и вернуться к шагу A1. (В результате выполняемых на этом шаге операций значение v уменьшается, значение НОД(u, v) остается неизменным.)
Бинарный алгоритм НОД.
Алгоритм B. (Бинарный алгоритм нахождения наибольшего общего делителя). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий делитель. (Использует знаковое представление чисел).
B1. [Найти степень 2.] Присвоить k ¬ 0, затем повторно присваивать k ¬ k + 1, u ¬ u / 2, v ¬ v / 2 нуль или более раз до тех пор, пока одно или оба числа u и v станут нечетными.
B2. [Начальная установка.] (Исходные значения чисел u и v уже разделены на 2k, и по крайней мере одно из текущих значений нечетно.) Если нечетно u, то присвоить t ¬ - v и перейти к шагу B4. В противном случае присвоить t ¬ u.
B3. [Уменьшить t наполовину.] (Здесь t четно и не нуль.) Присвоить t ¬ t / 2.
B4. [t четно?] Если t четно, то вернуться к шагу B3.
В5. [Установить max(u, v) заново.] Если t > 0, то присвоить u ¬ t, в противном случае присвоить v ¬ - t. (Большее из чисел u и v заменяется на |t| за исключением, возможно, первого выполнения этого шага.)
B6. [Вычесть.] Присвоить t ¬ u – v. Если t ¹ 0, то вернуться к шагу B3. В противном случае алгоритм останавливает выполнение, а на выходе будет u · 2k.
Рис.33. Бинарный алгоритм НОД
Расширенный алгоритм Евклида.
Алгоритм X. (Обобщенный алгоритм Евклида). Для заданных целых чисел u и v этот алгоритм определяет вектор (u1, u2, u3), такой, что uu1 + vu2 = u3 = НОД(u, v). В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3); действия производятся таким образом, что в течение всего процесса вычисления выполняются соотношения
ut1 + vt2 = t3 uu1 + vu2 = u3 uv1 + vv2 = v3.
X1. [Начальная установка.] Присвоить (u1, u2, u3) ¬ (1, 0, u), (v1, v2, v3) ¬ (0, 1, v).
X2. [v3 = 0?] Если v3 = 0, то выполнение алгоритма заканчивается.
X3. [Разделить и вычесть.] Присвоить , затем присвоить
(t1, t2, t3) ¬ (u1, u2, u3) – (v1, v2, v3) · q,
(u1, u2, u3) ¬ (v1, v2, v3),
(v1, v2, v3) ¬ (t1, t2, t3).
Возвратиться к шагу X2.
Расширенный бинарный алгоритм НОД.
Алгоритм Y. Модификация алгоритма X с использованием принципов алгоритма B. Для заданных целых чисел u и v этот алгоритм определяет вектор (u1, u2, u3), такой, что uu1 + vu2 = u3 = НОД(u, v). В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3); в течение всего процесса вычисления так же, как и в X выполняются соотношения
ut1 + vt2 = t3 uu1 + vu2 = u3 uv1 + vv2 = v3.
(Использует знаковое представление чисел).
Y1. [Найти степень 2.] То же, что в шаге B1.
Y2. [Начальная установка.] Присвоить (u1, u2, u3) ¬ (1, 0, u), (v1, v2, v3) ¬ (v, 1 – u, v). Если число u нечетно, присвоить (t1, t2, t3) ¬ (0, –1, –v) и прейти к шагу Y4. В противном случае присвоить (t1, t2, t3) ¬ (1, 0, u).
Y3. [Выполнить половинное деление t3.] Если t1 и t2 четны, присвоить (t1, t2, t3) ¬ (t1, t2, t3)/2; иначе присвоить (t1, t2, t3) ¬ (t1 + v, t2 – u, t3)/2. (В последнем случае t1 + v и t2 – u будут оба четными.)
Y4. [t3 четно?] Если t3 четно, вернуться к шагу Y3.
Y5. [Переустановить max(u3 v3).] Если t3 положительно, присвоить (u1, u2, u3) ¬ (t1, t2, t3); иначе присвоить (v1, v2, v3) ¬ (v – t1, – u – t2, – t3).
Y6. [Вычесть.] Присвоить (t1, t2, t3) ¬ (u1, u2, u3) – (v1, v2, v3). Затем, если t1 £ 0, присвоить (t1, t2) ¬ (t1 + v –, t2 – u). Если t3 ¹ 0, вернуться к шагу Y3. В противном случае закончить выполнение алгоритма с результатом, равным (u1, u2, u3 · 2k).