Кратко — алгоритмы, их асимптотика и оценка для двух 100‑значных чисел (100 десятичных цифр).
1) Размер входа
- 100 десятичных цифр ≈ 100·log2(10) ≈ $332$ бит. Обозначим битовую длину $n\approx 332$.
2) Алгоритм Евклида (деление с остатком)
- Идея: рекурсивно заменяем $(a,b)$ на $(b,a\mathrm{mod}b)$ пока остаток ≠ 0.
- Число итераций (делений) растёт примерно логарифмически в характерном размере чисел (в худшем случае линейно по числу цифр для «плохих» пар, например близких к числам Фибоначчи).
- Битовая сложность зависит от реализации деления/умножения. Обобщённо, если $M(n)$ — стоимость умножения $n$-бит чисел, то при использовании оптимизаций (Лемера, быстрых умножений) общий асимптотический расход можно дать как
$$O(M(n)\log n).$$ При наивной реализации (schoolbook, $M(n)=O(n^2)$) в теории худший случай классического Евклида даёт большие константы и может вести к сложностям порядка до $O(n^3)$ битовых операций без оптимизаций.
- На практике для 100‑значных случайных чисел число делений обычно невелико (порядка десятков — сотен), и каждая операция деления на современных больших‑числовых библиотеках очень быстрая.
3) Бинарный алгоритм (Stein)
- Идея: использовать только сдвиги (деление на 2), сравнения и вычитания; факториализуем общие степени двойки отдельно.
- Избегает дорогих операций общего деления, поэтому на машинах с дорогой операцией деления или при реализации на битовой арифметике часто быстрее.
- Асимптотика: при использовании тех же быстрых операций и реализаций также достигается
$$O(M(n)\log n)$$ в хороших реализациях; при наивных операциях (школьные вычитания/сдвиги) — обычно около $O(n^2)$ битовых операций.
- Практически бинарный алгоритм делает больше «итераций» (много сдвигов/вычитаний), но каждая итерация дешевле, особенно если аппаратно нет оптимальной многоразрядной делимости.
4) Оценка для двух 100‑значных чисел (приближённо)
- Размер: $n\approx 332$ бит.
- Ожидаемое число делений (Евклид, случайные числа): порядка $O(\log N)$, где $\log N\approx \ln (10^{100})\approx 230$ (натуральный логарифм) — это даёт ориентир «сотни» операций деления в худшем/среднем поведении без точных констант; на практике часто заметно меньше (десятки—сотни).
- Бинарный алгоритм может выполнять несколько сотен — несколько тысяч сдвигов/вычитаний (каждое действие — операция над $n$ битами).
- В реальных единицах времени на современном CPU или в библиотеке типа GMP обе процедуры для 100‑значных чисел выполнятся за доли миллисекунды—миллисекунды; разница несущественна, но:
- Если библиотека использует оптимизированный Евклид (Лемер + быстрые деления), то Евклид обычно быстрее.
- Если деление дорого или реализуется простыми операциями, бинарный gcd может быть быстрее из‑за отсутствия долгой операции деления.
5) Вывод (сравнение)
- Теоретически при использовании быстрых мультипликативных примочек оба алгоритма достигают примерно одной асимптотики $O(M(n)\log n)$.
- Практически для 100‑значных чисел:
- Оба алгоритма очень быстры; разница — в константах и в том, какие примитивы (деление vs сдвиг/вычитание) аппарат/библиотека выполняет быстрее.
- Для «производственных» реализаций (GMP и пр.) оптимизированный Евклид (с Лемером/быстрой арифметикой) чаще даёт лучший результат; бинарный gcd хорош как простая, портируемая и иногда более эффективная альтернатива на простом аппаратном обеспечении.
Если нужно, приведу пример конкретного случайного пару 100‑значных чисел и оценю число шагов каждого алгоритма (оценочно).