Алгоритм Евклида

Возьмите восемь долей такта и три удара. Расставьте удары как можно ровнее — так, чтобы промежутки между ними отличались как можно меньше. Получится x..x..x.: кубинский тресилло, ритм хабанеры и рокабилли. Пять ударов на восемь долей — синкильо, тоже с Кубы. Нажмите «Слушать» и подвигайте ползунки. Справа видно, как программа пришла к ответу. Это алгоритм Евклида, которому больше двух тысяч лет.

Посмотрите на шаги справа. Сначала три группы «x» и пять групп «.». К каждому «x» приклеиваем по точке — остаётся две точки. Потом к трём получившимся группам приклеиваем две оставшиеся — остаётся одна группа, и всё готово. Пять и три, три и два, два и один — это ровно последовательность остатков, которую строит Евклид, когда ищет наибольший общий делитель восьми и трёх. Связь заметил в 2005 году математик Годфрид Туссен. А сам алгоритм раскладывания импульсов за два года до него придумал физик Эрик Бьорклунд для системы синхронизации ускорителя нейтронов SNS. Ему нужно было как можно ровнее расставить импульсы пучка — та же задача, только без барабанов.

Идея

Любой общий делитель чисел a и b делит и остаток a mod b, и наоборот. Поэтому НОД(a, b) = НОД(b, a mod b). Остаток меньше делителя, числа быстро уменьшаются, и когда остаток станет нулём, последнее ненулевое число и будет ответом.

Это легко увидеть на прямоугольнике. Наибольший общий делитель сторон a и b — это сторона самого большого квадрата, которым прямоугольник можно замостить без зазоров. Отрежем от прямоугольника столько квадратов со стороной b, сколько влезет: останется полоска шириной a mod b. Любой квадрат, которым мостится весь прямоугольник, мостит и эту полоску. Значит, задача стала меньше, но ответ не изменился. Режем дальше, пока полоска не исчезнет.

Введите стороны 1071 и 462: три шага, и НОД равен 21. А теперь нажмите «Фибоначчи 89 × 55»: каждый шаг отрезает ровно один квадрат, шагов девять, и получается знаменитая спираль из квадратов. Это самый медленный случай, к нему мы вернёмся.

Почему это верно

Остатки строго убывают и неотрицательны, поэтому рано или поздно остаток равен нулю. На последнем шаге НОД(g, 0) = g, и по лемме это НОД исходной пары.

У Евклида в «Началах» (книга VII, предложение 2) вместо деления с остатком — вычитание: от большего отнимают меньшее, пока числа не сравняются. Результат тот же, но вычитаний может быть очень много: для пары (10¹⁸, 1) — миллиард миллиардов. Деление с остатком делает за один шаг всё, что вычитание делает за q шагов.

Расширенный алгоритм

Шаги Евклида можно прокрутить назад и выразить НОД через исходные числа. Из 1071 = 2·462 + 147 и 462 = 3·147 + 21 получаем 21 = 462 − 3·147 = 462 − 3·(1071 − 2·462) = 7·462 − 3·1071. В общем виде:

Расширенный алгоритм находит эти x и y на ходу, без обратного прохода. Он держит два равенства вида a·x + b·y = r и вычитает из одного другое, умноженное на частное, — ровно так, как обычный Евклид вычитает остатки. Главное применение — обратный элемент по модулю: если НОД(a, m) = 1, то a·x + m·y = 1, и по модулю m это значит a·x ≡ 1. Без этой операции нельзя вычислить секретный ключ RSA: он и есть обратный к открытой экспоненте.

Код

Обычный и расширенный алгоритм, наименьшее общее кратное и обратный элемент. Наименьшее общее кратное считаем как a / НОД · b, а не a·b / НОД: деление первым не даёт промежуточному произведению переполниться в Go.

В Python есть готовые math.gcd, math.lcm и pow(a, -1, m) для обратного по модулю. В стандартной библиотеке Go для обычных целых НОД нет, только для больших чисел — big.Int.GCD, и его обычно пишут сами: три строки.

А это алгоритм ритмов из первой сцены. Он печатает каждый шаг группировки, и видно, как числа групп повторяют остатки Евклида:

Сколько это стоит

Каждые два шага уменьшают большее число хотя бы вдвое: если r = a mod b, то r < a/2 (либо b ≤ a/2 и остаток меньше b, либо b > a/2 и остаток равен a − b < a/2). Значит, шагов O(log min(a, b)).

Точную границу в 1844 году нашёл Габриэль Ламе: число делений не больше чем в пять раз превосходит число десятичных цифр меньшего числа. Хуже всего — соседние числа Фибоначчи: у них каждое частное равно единице, и каждый шаг отнимает минимально возможное. Пара (89, 55) из второй сцены требует девяти делений, а для чисел до 10¹⁸ худший случай — 85 делений, и это снова соседние числа Фибоначчи, 679 891 637 638 612 258 и 420 196 140 727 489 673. Это одна из первых теорем о сложности алгоритма вообще — задолго до того, как появились слова «сложность алгоритма».

Где работает

• Дроби. Любая библиотека рациональных чисел — fractions.Fraction в Python, big.Rat в Go — сокращает дробь делением на НОД после каждой операции.
• Криптография. Секретная экспонента RSA — обратный элемент по модулю, а китайская теорема об остатках, которой ускоряют расшифровку, тоже строится на расширенном алгоритме.
• Шестерни. Если числа зубьев двух шестерён взаимно просты, каждый зуб одной шестерни со временем встречается с каждым зубом другой, и износ распределяется равномерно. Такую передачу называют передачей с «блуждающим зубом»; через сколько оборотов пара зубьев встретится снова, говорит НОД — об этом первая задача.
• Ритмы и расписания. Равномерно разложить k событий по n слотам: удары в такте, импульсы в ускорителе, рекламные показы в ленте. Это Евклид из первой сцены.

История

Алгоритм записан в «Началах» Евклида около 300 года до нашей эры и, по всей видимости, был известен и раньше. Дональд Кнут называл его прародителем всех алгоритмов: это самый старый нетривиальный алгоритм, который дожил до наших дней и до сих пор работает без изменений. Сам Евклид применял его не только к числам, но и к отрезкам — в десятой книге «Начал» той же процедурой проверяется, есть ли у двух отрезков общая мера. Если процесс никогда не кончается, отрезки несоизмеримы. По одной из версий, именно так греки и обнаружили, что диагональ квадрата не измеряется его стороной.

Задачи

В первой задаче — шестерни и проверка, что вы делите, а не вычитаете. Во второй понадобится расширенный алгоритм и немного размышлений о том, какое из бесконечно многих решений выбрать.