Способы (кратко, с оценками) и когда Евклид уступает:
1) Классический алгоритм Евклида (деление с остатком)
- Шаг: $a,b\mapsto b,a\mathrm{mod}b$ пока $b=0$.
- Число итераций: в среднем $O(\log n)$ (по длине в битах $n$), в худшем случае $\Theta (n)$ (пары Фибоначчи).
- Стоимость одной многоразрядной операции деления ~ $D(n)$ (обычно $D(n)=O(M(n))$, где $M(n)$ — стоимость умножения n-битных чисел).
- Общая сложность: в худшем случае $O(n\cdot D(n))$. При школьном умножении $M(n)=O(n^2)$ даёт до $O(n^3)$; с быстрым умножением и быстрым делением можно писать $O(n\cdot M(n))$.
2) Бинарный алгоритм (Stein)
- Использует сдвиги и вычитания: пока числа чётны/нечётны, делит на 2 или вычитает.
- Не требует деления с остатком, хорошо на целочисленной архитектуре.
- Сложность примерно сопоставима с классическим: в худшем случае $O(n^2)$ битовых операций при школьной арифметике; практическая эффективность хороша для малых/средних длин и на платформах, где деление дорогая операция.
3) Алгоритм Лемера (Lehmer)
- Идея: использовать старшие слова (приблизительные частные) для предугадывания нескольких шагов Евклида и выполнять их без дорогостоящих многословных делений (применяя вместо этого операции на машинных словах).
- Сильно сокращает число дорогих операций деления на больших многословных числах.
- Практически используется в GMP; даёт заметный выигрыш при большой длине слов (многословные числа) и когда стандартный Евклид делает много шагов с малыми частными.
4) Полу‑Евклидовский / рекурсивный (half‑GCD) и субквадратичные алгоритмы (Schonhage, Lehmer–Schönhage)
- Используют деление области (divide‑and‑conquer), вычисляют несколько шагов Евклида рекурсивно на старших разрядах, затем восстанавливают результат.
- Теоретическая сложность: $O(M(n)\log n)$ (где $M(n)$ — время умножения). При самом быстром известном $M(n)$ это почти субквадратично.
- Лучшие для очень больших чисел; на практике экономят число многословных делений и приобретают преимущество при больших $n$.
5) Модульные/континуированные подходы и гибриды
- Используют CRT/модульные инверсии или комбинируют методы (Lehmer + half‑GCD + бинарный).
- Полезны в специализированных задачах (много больших gcd подряд, параллельные реализации).
Когда классический Евклид уступает модификациям по производительности
- Числа очень большие (многотысячные/миллионные биты): тогда стоимость многословной делимости высока и выигрывают алгоритмы с меньшим числом таких делений (Lehmer, half‑GCD), дающие $O(M(n)\log n)$ вместо $O(n\cdot M(n))$.
- Случаи с большим числом итераций (пары типа Фибоначчи или близкие к ним): обычный Евклид делает $\Theta (n)$ шагов, тогда Lehmer/half‑GCD сокращают число дорогих шагов.
- Когда на платформе деление дорогая операция по сравнению с умножением/сдвигом: бинарный алгоритм или методы, сводящиеся к сдвигам/вычитаниям/умножению, могут быть выгоднее.
Практический совет (кратко)
- Для небольших/средних целых: классический Евклид или бинарный — проще и достаточно быстры.
- Для больших (многословных) целых: использовать Lehmer + half‑GCD (как в GMP) или полностью субквадратичные реализации; это даёт существенный выигрыш по времени.