Бинарный алгоритм

В статье [1] был описан так называемый “алгоритм Евклида” нахождения наибольшего общего делителя (НОД) двух целых чисел, разработанный более двух тысяч лет тому назад. Как сказано в статье, “большинство древних алгоритмов со временем вытеснялось из вычислительной практики более новыми алгоритмами. Алгоритм Евклида избежал этой участи прежде всего благодаря своей экономности”. Тем более удивительно, что хотя почтенный алгоритм Евклида и применяется в течение столь многих столетий, он (как будет показано ниже) не всегда является наилучшим способом для нахождения НОД!

В начале 60-х годов прошлого века Роланд Силвер и Джон Терзиан открыли совсем иной алгоритм для нахождения НОД, который прежде всего годится для двоичной арифметики (которая используется в компьютере). Этому “бинарному” алгоритму совершенно не нужны команды, требующие (как в алгоритме Евклида) выполнения действий деления, а тем более деления с остатком. Основанный на операциях вычитания бинарный алгоритм проверяет, является число четным или нет, и сдвигает вправо двоичное представление четного числа (тем самым выполняя деление пополам¹).

Перейдем к описанию бинарного алгоритма нахождения наибольшего общего делителя двух целых чисел. Он основан на следующих трех очевидных свойствах НОД.

1. НОД(2m, 2n) = 2 · НОД(m, n).

Общим делителем двух четных чисел является 2, а их НОД равен произведению числа 2 на НОД чисел, полученных при делении исходных чисел на 2.

2. НОД(2m, 2n + 1) = НОД(m, 2n + 1).

Если одно число четное, а второе — нечетное, то, поскольку 2 не является их общим делителем, четное число можно уменьшить в 2 раза — НОД полученного числа и исходного нечетного будет таким же, как и двух исходных чисел.

3. НОД(m, n) = НОД(m – n, n).

В качестве комментария к этому свойству приведем вариант алгоритма Евклида, в котором вместо определения остатка от деления большего из двух заданных чисел на меньшее используется вычитание (в общем случае — многократное):

НОД = m |или НОД = n

Возможность третьего свойства при m < n обусловлена тем, что по определению НОД(–m, n) = НОД(m, n).

Кроме того, по определению НОД: НОД(m, n) =
= НОД(n, m), НОД(0, 0) = 0, НОД(m, 0) = |m|.

Из свойств 1–3 сразу получается алгоритм, который мы опишем словесно, поясняя его на примере нахождения НОД чисел 40 902 и 24 140.

Пусть надо найти НОД(m₀, n₀); обозначим его d. По свойству 1 выделим сначала наибольшую степень двойки 2^k, на которую делятся как m₀ и n₀, так и число d (для чисел 40 902 и 24 140, k = 1 и 2^k = 2). Уменьшим m₀ и n₀ в 2^k раз, а число 2^k запомним. Получим два числа (20 451 и 12 070), одно из которых (или оба) нечетно (у нас нечетно число 20 451), а НОД этих чисел равен
d₁ = d/2^k. Затем, если одно из этих чисел четно (12 070), то, вспомнив свойство 2, поделим его на максимально возможную степень двойки, оставив при этом второе число без изменения, — в результате получим два нечетных числа т и п (20 451 и 6035) с НОД(m, n) = d₁. После этих операций мы пришли к задаче нахождения НОД только для нечетных чисел. При ее решении воспользуемся свойством 3. Вычтем из большего числа меньшее (20 451 – 6035 = 14 416), не изменив при этом
НОД = d₁, а поскольку разность двух нечетных чисел всегда четна, применим свойство 2: сократим эту разность на максимальную степень двойки (в примере на 2²), получив опять нечетное число (901). Затем снова воспользуемся свойством 3 (6035 – 901 = 5134) и один или несколько раз свойством 2 (5134 : 2 = 2567), потом опять свойствами 3 и 2, и так далее
(2567 – 901 = 1666 > 833 > 901 – 833 = 68 > 34 > 17 > 833 – 17 = 816 > 408 > 204 > … > 51 > 51 – 17 = 34 > 17). После выполнения каждой операции НОД не меняется, а хотя бы одно число пары уменьшается. Поэтому в некоторый момент оба числа станут равными друг другу; очевидно, что оба они в этот момент будут равны d₁. Искомый НОД (m₀ и n₀) вычисляется после этого как произведение чисел 2^k и d₁. (Для наших чисел НОД(40 902, 24 140) = 2 · 17 = 34.)

В приведенном бинарном алгоритме используются лишь операции вычитания и деления на 2. Последняя особенно проста, если т и п записаны в двоичной системе счисления.

На школьном алгоритмическом языке программа, реализующая этот алгоритм, может быть оформлена следующим образом:

кон

Удивительно, что и при “ручном” нахождении НОД двух многозначных чисел (например, четырехзначных) проявляется преимущество бинарного алгоритма перед алгоритмом Евклида. Приходится меньше писать, да и ошибки вычислений практически отсутствуют: ведь необходимо только уметь вычитать и делить на 2 (стирать правый ноль в двоичной записи). Правда, число итераций несколько возрастает по сравнению с количеством итераций в алгоритме Евклида, но зато каждая итерация выполняется гораздо проще — совершенно отсутствуют шаги деления. Эта простота позволяет существенно экономить время при нахождении НОД, что видно на примере.

Известный математик и программист Д.Кнут, автор многотомного сочинения “Искусство программирования для ЭВМ”, сравнивая эти два алгоритма, писал: “Таким образом, большая скорость выполнения итераций в программе, получаемая за счет простоты этих операций, компенсирует рост числа необходимых итераций. Мы обнаружили, что выполнение бинарного алгоритма нахождения НОД на машине MIX примерно на 16% быстрее, чем выполнение на той же машине алгоритма Евклида; при работе на других машинах ситуация, конечно, может быть иной, но, во всяком случае, обе программы вполне эффективны. Тем не менее оказывается, что даже такая освященная веками процедура, как алгоритм Евклида, не может противостоять прогрессу…”

Задания для самостоятельной работы

1. На языке программирования, который вы изучаете, разработайте программу нахождения НОД двух чисел, работающую по бинарному алгоритму.

2. Найдите (“вручную”) по алгоритму Евклида и бинарному алгоритму наибольший общий делитель следующих чисел: 1985 и 1986; 198 519 851 985 и 198 619 861 986; 689 168 916 891 и 589 158 915 891; 27 182 818 284 и 31 415 926 536.

Результаты, пожалуйста, присылайте в редакцию. Фамилии всех приславших будут опубликованы, а лучшие ответы мы поощрим.

Литература

1. “Прадедушка” всех алгоритмов. / “В мир информатики” № 115 (“Информатика” № 21/2008).

2. Гальперин Г.А., Корлюков А.В. Бинарный алгоритм. / “Квант” № 12/1986.