Алгоритм Евклида: не больше пяти кругов на цифру

Если ты объяснишь, почему общие делители пары (a, b) и пары (b, a mod b) совпадают, назовёшь худший вход для алгоритма Евклида и знаешь, чем плоха версия на вычитании, - листай до «Теперь сам».

Как думаешь, сколько кругов на пятнадцати цифрах

Наибольший общий делитель, НОД, - самое большое число, на которое делятся оба. В первом разделе курса алгоритм Евклида служил примером цикла, который обязан остановиться:

while b != 0:
    r = a % b
    a = b
    b = r

Там же получена оценка: за два круга первое число уменьшается хотя бы вдвое. Теперь вопрос про цену. Возьмём два случайных числа по пятнадцать цифр - порядка квадриллиона каждое. Прежде чем читать дальше, попробуй угадать, сколько кругов сделает цикл: тысячи? миллионы? И существует ли пара, на которой он работает заметно дольше, чем на случайной?

На что это похоже

Представь, что прямоугольный пол 1989 на 867 надо выложить одинаковыми квадратными плитками без подрезки, и плитку хочется взять как можно крупнее.

Отрежем от пола квадраты со стороной 867: их поместится два, останется полоса 255 на 867. Плитка, которая укладывает весь пол, обязана укладывать и квадраты 867 на 867, и остаток - значит задача свелась к полу 867 на 255. От него отрезаются три квадрата по 255, остаётся 102 на 255. Потом два по 102, остаётся 51 на 102. Последний остаток делится на два квадрата по 51 без полосы. Плитка 51 укладывает всё, и крупнее не бывает.

Механизм: общие делители переживают замену

Раздели a на b с остатком: a = q · b + r. Утверждение одно: у пары (a, b) и у пары (b, r) одни и те же общие делители.

В одну сторону. Пусть d делит и a, и b. Тогда d делит q · b, а значит и разность a − q · b = r. То есть d - общий делитель b и r.

В другую. Пусть d делит и b, и r. Тогда он делит q · b + r = a. То есть d - общий делитель a и b.

Множества общих делителей совпадают - совпадает и наибольший. Каждый круг заменяет пару на меньшую с тем же НОД. Когда второе число стало нулём, ответ - первое: ноль делится на что угодно, и наибольший делитель пары (a, 0) - само a.

круг    a       b      частное q    остаток r
 1     1989    867        2           255
 2      867    255        3           102
 3      255    102        2            51
 4      102     51        2             0
        51      0                              НОД = 51

Столбец частных - число квадратов, отрезанных на каждом шаге из истории про пол.

Два числа называют взаимно простыми, если их НОД равен единице: общих делителей, кроме единицы, у них нет. Сами числа при этом простыми быть не обязаны: 8 и 15 взаимно просты.

Правило

НОД(a, b) = НОД(b, a mod b), и НОД(a, 0) = a. Если первое число не меньше второго и цикл Евклида сделал k кругов, то меньшее из чисел не меньше числа Фибоначчи с номером k + 1 - это теорема Ламе. Числа Фибоначчи растут как степень числа 1,618, и пять шагов по ним увеличивают число больше чем вдесятеро (1,618⁵ ≈ 11), поэтому кругов не больше пяти на каждую десятичную цифру меньшего числа. В действиях над разрядами алгоритм Евклида для чисел из n разрядов стоит в худшем случае Θ(n²) - столько же, сколько одно умножение столбиком: круг с коротким частным дёшев, а сумма длин всех частных не больше длины исходного числа.

Разбор: замер на случайных числах

def nod(a, b):
    krugov = 0
    while b != 0:
        r = a % b
        a = b
        b = r
        krugov = krugov + 1
    return [a, krugov]

nod(1989, 867) возвращает [51, 4]. Если аргументы поменять местами, кругов станет пять: первый круг делит меньшее на большее, получает частное ноль и просто переставляет числа.

Тысяча случайных пар каждой длины (пары строит генератор псевдослучайных чисел с постоянным начальным значением, так что замер повторяется точно):

цифр в числах    кругов в среднем    самое большее    граница 5 · цифр
      3                5,8                 11                15
      6               11,6                 19                30
      9               17,4                 31                45
     12               23,4                 36                60
     15               29,3                 44                75

Ответ на вопрос из начала: двадцать девять кругов. На каждые три цифры длины - шесть кругов сверху, около 1,94 круга на цифру. Рост линейный по числу цифр, как и обещает правило, и до границы далеко.

Ещё один замер: среди десяти тысяч случайных пар чисел до миллиона взаимно простыми оказались 6046. Шесть пар из десяти: в теории чисел доказано, что доля близка к 6/π² ≈ 0,61 при любом размере чисел. Она ещё пригодится: когда алгоритму нужно число, взаимно простое с данным, случайная попытка удаётся чаще, чем нет.

Разбор: худший вход и версия, которая ломается

Круг тем бесполезнее, чем меньше частное: при q = 1 от большего числа отнимается меньшее всего один раз. Пара, у которой все частные равны единице, строится с конца: (1, 0), перед ней (2, 1), потом (3, 2), (5, 3), (8, 5) - каждое новое число равно сумме двух предыдущих. Это числа Фибоначчи.

пара соседних чисел Фибоначчи                     цифр в меньшем    кругов
55, 34                                                  2              8
6 765, 4 181                                            4             18
102 334 155, 63 245 986                                 8             38
1 548 008 755 920, 956 722 026 041                     12             58
8 944 394 323 791 464, 5 527 939 700 884 757           16             76

Кругов почти пять на цифру: 76 / 16 = 4,75. Это и есть граница из правила: чтобы получить столько же кругов, меньшее число пары обязано быть не меньше, чем здесь.

Теперь версия, с которой алгоритм начинался у самого Евклида, - вычитание вместо остатка:

while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a

На паре (1989, 867) она делает 8 кругов вместо 4 - терпимо. На паре (1 000 000, 1) - 999 999 кругов: единица вычитается из миллиона по одной. Остаток делает то же за один круг. Вычитание отрезает от пола по одному квадрату, остаток - все сразу, и когда квадрат маленький, а пол длинный, разница - это величина числа против длины его записи. Версия на вычитании экспоненциальна, версия на остатке полиномиальна - ровно та граница, о которой был последний урок прошлой главы.

Что ломается без этого

Первое: НОК через произведение. Наименьшее общее кратное - a · b / НОД(a, b). Если сначала перемножить, произведение может не поместиться в тип, хотя ответ помещается. Сначала делят: a // НОД(a, b) * b.

Второе: ноль и знак. НОД(a, 0) = a, а НОД(0, 0) по соглашению 0. Версия на вычитании на нуле зацикливается. С отрицательными числами остаток в разных языках имеет разный знак; проще взять абсолютные величины до начала.

Третье: разложение вместо Евклида. Найти НОД, разложив оба числа на простые множители, - школьный способ, и он экспоненциален: разложение трудно само по себе. Евклиду множители не нужны.

Четвёртое: рекурсия на длинных числах. Рекурсивная запись nod(b, a % b) красива, но для чисел в тысячи цифр глубина доходит до тысяч вызовов. Цикл не имеет глубины.

Зачем это в работе

Сокращение дробей: числитель и знаменатель делят на их НОД. Разрешение 1920 на 1080 - это 16 к 9, потому что НОД равен 120. Точные дроби в библиотеках сокращаются так после каждого действия.

Расписания: задача раз в 4 минуты и задача раз в 6 минут совпадают раз в НОК(4, 6) = 12 минут. Если периоды взаимно просты, совпадение редкое - раз в произведение периодов.

Хеш-таблицы: в двойном хешировании из раздела про хеширование шаг пробы задаёт вторая хеш-функция. Шаг должен быть взаимно прост с размером таблицы: при шаге 4 и таблице на 12 ячеек обход посещает три ячейки из двенадцати и возвращается в начало. Поэтому размер таблицы берут простым или степенью двойки при нечётном шаге.

Ключи: в 2012 году исследователи собрали миллионы открытых ключей RSA из интернета и посчитали НОД для пар. У тысяч ключей нашлись общие множители - устройства генерировали их при плохой случайности. Общий множитель двух ключей раскрывает оба, и находит его алгоритм, которому две с лишним тысячи лет.

Теперь сам

1. Найди НОД(252, 198) алгоритмом Евклида. Сколько кругов?
2. Числа по девять цифр. Сколько кругов самое большее сделает алгоритм по правилу «пять на цифру»? А сколько примерно в среднем, если судить по замеру?
3. Какая пара из чисел до ста заставит алгоритм работать дольше всего?
4. Чему равно НОК(4, 6) и как его посчитать, не перемножая 4 и 6 до деления?