Например, можно вычислить gcd(40902,24140) следующим образом:

gcd(40902,24140) = gcd(24140,16762) = gcd(16762,7378)

= gcd(7378,2006) = gcd(2006,1360) = gcd(1360,646) = gcd(646,68) = gcd(68,34) = gcd(34,0) = 34.

Справедливость алгоритма A легко доказать из соотношения (4) и уравнения

gcd(u, v) = gcd{v, и - qv) (13)

для любого целого числа q. Уравнение (13) вьшолняется потому, что любой общий делитель чисел и и v является делителем как и, так и и - qv, и наоборот, любой общий делитель чисел v и и - qv должен делить оба числа и и v.

В следующей MIX-программе показано, что алгоритм А может быть легко реализован на компьютере.

Программа А {Алгоритм Евклида). Положим, что и и v - неотрицательные целые числа однократной точности, помещенные в ячейки U и V соответственно; эта программа помещает gcd(u,t;) в ячейку гА.

Время выполнения программы составляет 191"-1- 6 циклов, где Т - число выполненных операций деления. Рассуждения, приведенные в разделе 4.5.3, показывают, что в случае, когда и и г; независимо и равномерно распределены в интервале 1 < и, и < 7V, среднее значение Г можно приблизительно представить в виде Г = 0.8427661n7V-1-0.06.

Бинарный метод. После стольких столетий применения почтенного алгоритма Евклида несколько неожиданным оказалось то, что он не всегда является лучшим способом определения наибольшего общего делителя. В 1961 году Джозеф Стейн (Josef Stein) предложил совершенно другой алгоритм нахождения наибольшего общего делителя, ориентированный, прежде всего, на двоичную арифметику [см. J. Сотр. Phys. 1 (1967), 397-405]. Этому новому алгоритму совершенно не нужны команды, выполняющие операции деления. Основанный исключительно на операциях вычитания, он проверяет, четно ли число, и делит пополам четные числа (что соответствует в двоичной арифметике сдвигу вправо).

Бинарный алгоритм нахождения наибольшего общего делителя основан на четырех простых фактах относительно положительных целых чисел и и и.

a) Если UVIV оба четны, то gcd(u,t;) = 2gcd(u/2,t;/2) [см. уравнение (8)].

b) Если и четно, а v нечетно, то gcd(u,t;) = gcd(u/2,t;) [см. уравнение (6)].

c) Как и в алгоритме Евклида, gcd(u,t;) = gcd(u - v, v) [см. уравнения (13) и (2)].

d) Если uviv оба нечетны, то и - и четно и и - t; < max(u,t;).

Алгоритм В {Бинарный алгоритм нахождения наибольшего обш,его делителя). По данным целым числам и и и этот алгоритм (рис. 9) находит наибольший общий делитель.

81. [Найти степень 2.] Присвоить О, затем повторно присваивать fc fc -I- 1, и u/2, V *r- и/2 нуль или более раз до тех пор, пока оба числа и к v станут нечетными.

82. [Начальная установка.] (Исходные значения чисел и и и уже разделены на 2*, и по крайней мере одно из текущих значений нечетно.) Если нечетно и, то присвоить t <--и и перейти к шагу В4. В противном случае присвоить i <- и.

83. [Уменьшить t наполовину.] (Здесь t четно и не нуль.) Присвоить t t/2.

84. [t четно?] Если t четно, то вернуться к шагу ВЗ.

85. [Установить max(u,t;) заново.] Если i > О, то присвоить и i, в противном случае присвоить v <г- -t. (Большее из чисел и и и заменяется на \t\ за исключением, возможно, первого выполнения этого шага.)

86. [Вычесть.] Присвоить t <г- u-v. Если i 7 О, то вернуться к шагу ВЗ. В противном случае алгоритм останавливает выполнение, а на выходе будет и • 2*.

В качестве примера работы алгоритма В рассмотрим случай с числами и = 40902,

V - 24140, т. е. с теми же числами, которые использовались при проверке работы алгоритма Евклида. На шаге В1 выполняются присвоения fc 1, и 20451,

V 12070. Затем t присваивается значение -12070, которое заменяется значением -6035; после этого значение v заменяется числом 6035 и вычисления продолжаются следующим образом.

Результат равен 17 • 2 = 34. Здесь нам пришлось выполнить немного больше итераций, чем при работе с алгоритмом А, но каждая из них вьшолнялась проще, так как совершенно отсутствовали операции деления.

Для разработки MIX-программы, реализующей алгоритм В, потребовалось немного больше команд, чем для реализации алгоритма А. Чтобы получить программу, типичную для двоичного компьютерного представления алгоритма В, предположим, что компьютер MIX расширен путем включения следующих операторов.

• SLB (сдвинуть влево как двоичный код в АХ). С = 6; F = 6.

Содержимое регистров А и X "сдвигается влево" на М двоичных разрядов, т. е. гАХ <г- 2•rAX modB°, где В - размер байта. (Как и во всех других командах сдвига в MIX, знаки регистров гА и гХ не изменяются.)

Найти степень 2

В2. Начальная установка

Уменьшить t наполовину

t четно? у

Нет.

В5. Установить max(u, v) заново

Рис. 9. Бинарный алгоритм нахождения наибольшего общего делителя.

• SRB (сдвинуть вправо двоичный код в АХ). С = 6; F = 7.

Содержимое регистров А и X "сдвигается вправо" на М двоичных разрядов, т. е. гАХ [rAX/2J.

• JAE, JAO (переход, если в регистре А находится четное число; переход, если в регистре А находится нечетное число). С = 40; F = 6, 7 соответственно. Переход выполняется, если в регистре гА находится четное или нечетное число соответственно.

• JXE, JXO (переход, если в регистре X находится четное число; переход, если в регистре X находится нечетное число). С = 47; F = 6, 7 соответственно.

Эти операции аналогичны JAE, JAO.

Программа В {Бинарный алгоритм нахождения наибольшего общего делителя). Пусть U и г; - положительные целые числа с однократной точностью, помещенные соответственно в ячейки памяти U и V. Эта программа, используя алгоритм В, помещает gcd(m, v) в гА. Содержимое регистров таково: гА = t, гП = к.