Кратко опишу каждый метод, дам оценки сложности и практические рекомендации для двух 12‑значных целых чисел $A,B$ (т.е. величины порядка $10^{12}$, битовая длина примерно $\sim 40$).
1) Алгоритм Евклида (делением по модулю)
- Описание: повторять $r:=a\mathrm{mod}b$, затем $a:=b,b:=r$, пока $b=0$; результат — $a$.
- Количество итераций: составляет $O(\log \min (A,B))$. Формально число делений ограничено линейно по числу цифр (в битах) — т.е. $O(n)$ итераций при длине в битах $n$.
- Стоимость одной итерации: одна операция деления/остатка (на практике — аппаратная 64‑бит деление).
- Общая сложность (приблизительно): $O(\log \min (A,B))$ делений, в битовой модели с наивной арифметикой — полиномиально, но для 12‑значных чисел это константно малое время.
- Практика: крайне быстрая и простая в реализации; для $A,B$ порядка $10^{12}$ обычно выполняется за несколько делений на современной машине. Рекомендую как основной метод.
2) Алгоритм с вычитаниями (наивный вычитательный Евклид)
- Описание: пока $a\ne b$ выполнять либо $a:=a-b$ если $a>b$, либо $b:=b-a$ иначе; ответ — $a$ (или $b$).
- Сложность: в худшем случае число вычитаний пропорционально отношениям чисел — может быть порядка $\Theta (\max (A,B))$ (очень большое). Формально крайне неэффективен для больших чисел.
- Практика: допустим только если числа малы или почти равны; в системах без операции деления (только сложение/вычитание/сдвиги) можно рассмотреть, но для 12‑значных чисел это обычно непригодно (может потребоваться до $10^{12}$ вычитаний).
- Замечание: бинарный GCD (Stein) — улучшение на основе сдвигов и вычитаний: избегает деления, даёт сложность, сопоставимую с делением на практике, и может быть предпочтителен в реализации на машин без быстрых делений или при больших многословных числах.
3) Факторизация-по-простым (разложение и пересечение простых степеней)
- Описание: факторизовать $A$ и $B$ в простые множители, затем пересечь множества простых степеней: $\gcd (A,B)=\prod p^{\min ({\alpha }_p,{\beta }_p)}$.
- Сложность факторизации: зависит от метода. Тривиальное деление по простым до $\sqrt{N}$ требует $O(\sqrt{N})$ делений; для $N\sim 10^{12}$ это примерно до $\sqrt{10^{12}}=10^6$ делений — это выполнимо за доли секунды на современном CPU. Более быстрые практические методы (Pollard's Rho, ECM) обычно факторизуют такие числа очень быстро.
- Практика: факторизация дороже, чем просто найти НОД модульным Евклидом; но полезна если нужна сама факторизация или дополнительные сведения (напр., мультипликативные функции). Если числа «гладкие» (много малых простых), факторизация может быть сверхбыстрой.
- Риски: для значительно больших чисел факторизация становится вычислительно тяжёлой; для одноразового простого вычисления НОД факторизация — излишняя работа.
Сводка и рекомендации
- Для двух 12‑значных чисел лучший общий выбор — алгоритм Евклида с операцией остатка (или его оптимизация Lehmer/бинарный GCD при необходимости). Он простой, надёжен и чрезвычайно быстрый на 64‑бит целых.
- Алгоритм с вычитаниями применим только в учебных целях или в средах без деления и при маленьких/почти равных числах; в общем случае — плохо масштабируется ($O(\max (A,B))$ вычитаний в худшем случае).
- Факторизация целесообразна, когда требуется сами простые множители или когда числа малы/легко факторизуются; для чистого вычисления НОД обычно менее эффективна, но для $10^{12}$ её выполнение практично и может дать дополнительную информацию.
Коротко: для практики и эффективности — Euclid (mod) (или бинарный GCD при отсутствии быстрых делений). Факторизация — только если нужен факторный разбор; вычитания — только в исключительных ограниченных сценариях.