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

40

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

Канддат физико-mатематических наук
Г. А. ГАЛЬПЕРИН,
канддат физико-mатематических наук
А. В. КОРЛЮКОВ

Алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух чисел изложен в следующей книге его «Начал» (около 300 г. до н. э.). Многие учены предполагают, что он является интерпретацией алгоритма, предложенного Евdkocom (около 375 г. до н. э.). Так или иначе алгоритм Евклида можно назвать «дедушкой» всех алгоритмов, поскольку это самый первый нетривиальный алгоритм, должен до наших дней *. Эту часть могли бы, пожалуй, описывать вычисление методы решения некоторых систем квадратных уравнений с двумя неизвестными, появившиеся за полтора тысячелетия до Евклида. Однако они не выделяются сравнения с алгоритмом Евклида, поскольку в них не содержитсятерация и поскольку они были вытеcenны современными алгебраическими методами.

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

Примерно в 1962 г. Роланд Силвер и Джон Терзан открыли совсеминой алгоритм для нахождения НОД, который прежде всего годится для двойной арифметики. Этот новому «бинарному» алгоритму совершено не нужны команды, требующие (как в алгоритме Евклида) выполнения действия, а тем более действия с остатком. Основанный на операциях вычитания, бинарный алгоритм еще проверяет, является число четным или нет, и сдигает вправо двойное представление четного числа (тем самым выполняя деление пополам).

Бинарный алгоритм очень просто реализуется на микрокалькуляторах и этим выгодно отличаться от алгоритма Евклида. Отметим, что реализация алгоритма Евклида на микрокалькуляторах затруднительна: основная трудность состоит в отсутствии операций деления с остатком двух целых чисел. Например, среди 300 приведенных в справочнике В. П. Дьяконова*) программ отсутствует алгоритм Евклида. Отметим еще, что нет в школе общепризнанного обозначения для остатка от деления; возможно, по этой причине в учебнике по информацией для 9-го класса при записи алгоритма Евклида предлагается деление с остатком заменять на последовательные вычитания.

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

1. НОД (2m, 2n)=2·НОД (m, n).
2. НОД (2m, 2n+1)=НОД (m, 2n+1).
3. НОД (m, n)=НОД (m−n, n). По определению НОД, НОД (m, n)=НОД (n, m), НОД (−m, n)=НОД (m, n), НОД (0, 0)=0, НОД (m, 0)=|m|. Из свойств 1 — 3 сразу получается алгоритм, который мы опишем словесно, поясняя его на примере нахождения НОД чисел 40 902 и 24 140.

Пусть надо найти НОД (m₀, n₀); обозначим его d. По свойству 1 выделим сначала наибольшую степень двойки 2ᵉ, на котором делятся как m₀ и n₀, так и число d (для чисел 40 902 и 24 140, k=1 и 2ᵉ=2). Уменьшим m₀ и n₀ в 2ᵉ раз, а число 2ᵉ запомним. Получим два числа (20 451 и 12 070), одно из которых (или оба) нечетно (у нас нечетно число 20 451), а НОД этих чисел равен d₁=d/2ᵉ. Затем, если одно из этих чисел четно (12 070), то подelim его на максимальное возможную степень двойки, оставив второе число изменения, и в результате получим два нечетных числа m и n

*) Подробно об алгоритме Евклида см. статью С. А. Абрамова в «Кванте», 1985, № 11, с. 44.

41

(20 451 и 6 035) с НОД (m, n) = d₁. После этих операций мы пришли к задаче нахождения НОД только для нечетных чисел. При ее решения воспользовемся свойством 3. Вычитем из большого числа меньше (20451—6035=14 416), не изменив при этом НОД = d₁, а поскольку разность нечетных чисел всегда четна, применим свойство 2: сократим эту разность на максимальную степень двойки (в примере на 2²), получив опять нечетное число (901). Затем снова воспользовемся свойством 3 (6035—901=5134) и один или несколько раз свойством 2 (5134:2=2567), поэтому опять свойствми 3 и 2, и так далее (2567—901=1666→833→901—833=68→17→833—17=816→51→51—17=34→17). После выполнения каждого операции НОД не меняется, а хотя бы одно число пары уменьшается. Поэтому в некоторых моментах оба числа станут равными друг другу; очевидно, что оба они в этот момент будут равны d₁. Искомый НОД (m₀, n₀) вычисляется после этого как произведение чисел 2ᵏ и d₁. (Для наших чисел НОД (40902, 24140)=2·17=34.)

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

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

алг бинар (цел m, n, k, r, s, d)
apr m, n
рез d
нач r:=0, s:=0
пока m≠n
ни пока m четное
ни m:=m/2
r:=r+1
кц
пока n четное
ни n:=n/2
s:=s+1
кц
k:=min {r, s, k}
пока m>n
ни m:=m-n
кц
пока n>m
ни n:=n-m
кц
d:=2ᵏ·m

кон

*) Если k не определено, при нахождения min {r, s, k} мы считаем, что min {r, s, k} = min (r, s). Эта маленькая хитросъ позволяет раз насегда определить k: при дальнейшем увеличении r и s не меняется.

Эту программу нетрудно оттранслровать на языки Робик или Бэйсик или перевести в коды программируемого микрокалькулятора типа БЗ—34 (см. «Квант», 1986, № 2, 3).

Посмотрим, как следует организовать вычисления по бинарному алгоритму на общим (не программируемом) калькуляторе. Пусть данные положительные целые числа m и n; вычисление d=НОД (m, n) тогда распадается на следующие шаги.

1. Засылаем число m на индикатор и делим его пополам k₁ раз (k₁≥0), пока не получаем нечетное число m₁.
2. Засылаем число n на индикатор (при этом m₁ сдигается в ячейку памяти) и делим его пополам k₂ раз (k₂≥0), пока не получим нечетное число.
3. Если числа в памяти и на индикатор равны, то k раз удваивается число на индикатор, где k=min {k₁, k₂}; полученное число и есть d.
4. Если число на индикатор меньше числа в памяти, то меняем их местами.
5. Выполняем вычитание.
6. Дelimит число на индикаторе пополам, пока не получится нечетное число и возвращается к шагу 3.

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

Алгоритм Евклида
НОД (40902, 24140)=34