Математика / Арифметика и теория чисел

Бинарный алгоритм Евклида: НОД через деление пополам

Бинарный алгоритм Евклида, или алгоритм Стейна, находит наибольший общий делитель двух целых чисел с помощью чётности, деления пополам и вычитания. Он заменяет дорогие остатки последовательностью простых операций над битами.

Опубликовано: Обновлено:

Формула

$$\gcd(a,b)=2^s\gcd(u,v),\quad a=2^s u,\ b=2^s v,\quad u,v\text{ не оба чётные}$$
Схема Сокращение пары в алгоритме Стейна
Бинарное сокращение НОД(48,18)(24,9)(6,9)(3,3)общая 2: s=1разность → деление пополам

Общую двойку выносят в счётчик, затем разность нечётных чисел снова делят пополам.

Обозначения

$a,b$
неотрицательные целые входные числа, числа
$s$
минимальная из степеней двойки в a и b, разрядов
$u,v$
аргументы после удаления общей степени двойки, числа
$gcd$
наибольший общий делитель, число

Условия применения

Пусть a и b — неотрицательные целые, не равные одновременно нулю. Для отрицательных входов сначала берут модули. Общую степень двойки выносят только после проверки чётности обоих чисел; после этого хотя бы одно число нечётно. При a=b алгоритм завершает работу, а случай нулевого аргумента задаётся соглашением gcd(0,b)=b.

Ограничения

В учебной записи вычитания могут потребовать много шагов, если числа сильно различаются, поэтому реализация с остатком Евклида иногда проще и быстрее. Алгоритм не раскладывает число на простые множители и не решает НОД для многочленов без отдельного обобщения. Нужно избегать переполнения при вычислении 2^s и корректно обрабатывать нулевые входы.

Подробное объяснение

Алгоритм Стейна использует три инварианта. Если оба аргумента чётные, их общий делитель содержит множитель 2, поэтому gcd(2a,2b)=2gcd(a,b); общую степень двойки можно вынести и вернуть в конце. Если чётно только одно число, множитель 2 не влияет на НОД нечётного партнёра: gcd(2a,b)=gcd(a,b) при нечётном b. Эти равенства превращают деление пополам в безопасное сокращение задачи.

После удаления двоичных множителей оба числа не могут быть чётными. Пусть u≥v и v>0. Тогда gcd(u,v)=gcd(u−v,v): любой общий делитель делит разность, и обратно делит u=(u−v)+v. Разность двух нечётных чисел чётна, поэтому её снова можно делить пополам, пока она не станет нечётной. Так размер пары уменьшается, а НОД сохраняется на каждом шаге.

Смысл коэффициента 2^s не в приблизительном масштабе, а в точном восстановлении вынесенного общего множителя. Например, если a=48 и b=18, общая степень двойки равна 1: после деления получаем 24 и 9, затем 12 и 9, 3 и 9, 3 и 3; ответ 2·3=6. При одном нулевом аргументе НОД равен ненулевому числу.

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

Алгоритм отличается от обычного Евклида не результатом, а допустимыми элементарными операциями. Он сохраняет НОД, но не выдаёт коэффициенты Безу без дополнительного сопровождения линейной комбинации. Поэтому для обратного элемента по модулю удобнее расширенный алгоритм Евклида.

Как пользоваться формулой

  1. Замените отрицательные входы модулями; если один аргумент равен нулю, верните модуль второго и завершите вычисление.
  2. Пока оба числа чётные, разделите их пополам и увеличьте счётчик s на единицу, сохраняя общий множитель 2^s.
  3. Если чётно только одно число, разделите пополам именно его; НОД с нечётным партнёром от этого не изменится.
  4. Сделайте нечётным большее число, вычитая из него меньшее; затем повторяйте деление полученной разности пополам.
  5. Когда числа сравняются, это нечётное значение равно НОД сокращённых аргументов, поэтому умножьте его на 2^s.
  6. Проверьте результат делимостью: ответ должен делить оба исходных числа, а любой общий делитель не может быть больше него.

Историческая справка

Идея вычислять НОД без деления с остатком восходит к описаниям бинарной арифметики и получила современную алгоритмическую форму в работах Джозефа Стейна. В 1967 году Стейн предложил вариант, использующий только сравнения, вычитания и деление на два; публикация появилась в контексте анализа операций, удобных для двоичных вычислительных машин. Это был ответ на практическую проблему: аппаратное деление долгое время стоило заметно дороже сдвига и вычитания.

Классический алгоритм Евклида старше и использует остаток a mod b. Бинарный вариант не отменяет его теорию, а раскладывает тот же принцип на два тождества: общий множитель 2 можно вынести, а gcd(u,v) равен gcd(u−v,v). Позже анализ сложности и инженерные реализации уточнили, что на современных процессорах встроенное деление может быть достаточно быстрым, поэтому выбор метода зависит от размера слов, библиотеки больших чисел и профиля нагрузки.

В учебной истории алгоритм Стейна важен как пример адаптации математического инварианта к модели вычислений. Он показывает, что одна и та же задача может иметь разные эффективные формы при разных стоимостях операций. Современные библиотеки иногда объединяют идеи Стейна с ускоренным вычитанием или пакетной обработкой младших нулевых битов, сохраняя тот же НОД.

Историческая линия формулы

Бинарный алгоритм НОД обычно называют алгоритмом Стейна по работе Джозефа Стейна 1967 года. Это не новый НОД, а двоичная форма евклидовой идеи, приспособленная к дешёвым сдвигам и вычитаниям. Исторически корректно отделять авторство варианта от гораздо более ранней традиции алгоритма Евклида.

Пример

Найдём gcd(48,18). Оба числа чётны один раз: 48/2=24, 18/2=9, поэтому s=1. Теперь пара (24,9): чётное 24 делим пополам и получаем (12,9), затем (6,9), затем (3,9). Вычитаем меньшее из большего: 9−3=6; делим 6 пополам и получаем (3,3). Сокращённый НОД равен 3, возвращаем общий множитель: gcd(48,18)=2^1·3=6. Проверка: 48=8·6, 18=3·6, а общий делитель 12 невозможен, потому что 12 не делит 18. Все величины безразмерны; это арифметика целых чисел. Дополнительная проверка обычным Евклидом даёт 48 mod 18=12, 18 mod 12=6, 12 mod 6=0, то есть тот же результат 6. Сравнение двух независимых вычислений полезно при переносе алгоритма в код.

Частая ошибка

Нельзя забывать множитель 2^s после удаления общих двоичных множителей: иначе для 48 и 18 получится 3 вместо 6. Нельзя делить нечётный партнёр пополам — это изменит НОД. При вычитании нужно сначала упорядочить числа, иначе можно получить отрицательную разность и нарушить правила сокращения. Нулевой аргумент обрабатывают отдельно, а gcd(0,0) не определяют как обычный положительный НОД. Наконец, побитовый сдвиг отрицательного значения не заменяет предварительный переход к модулю.

Практика

Задачи с решением

НОД пары 84 и 30

Условие. Вычислите gcd(84,30) бинарным алгоритмом и восстановите вынесенную степень двойки.

Решение. Общая двойка одна: (84,30)→(42,15). Затем 42→21, получаем (21,15). Разность даёт (6,15), затем (3,15), (3,12), (3,6) и (3,3). Возвращаем 2·3=6.

Ответ. gcd(84,30)=6.

Нулевой аргумент

Условие. Найдите gcd(0,45) и объясните, почему цикл Стейна не нужен.

Решение. Каждый общий делитель 0 и 45 должен делить 45, а 45 делит оба числа. Наибольший такой положительный делитель равен 45.

Ответ. gcd(0,45)=45.

Дополнительные источники

  • https://doi.org/10.1016/0021-9991(67)90047-2
  • https://arxiv.org/abs/1004.4710
  • https://members.loria.fr/PZimmermann/mca/pub226.html

Связанные формулы

Математика

Наибольший общий делитель

$\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$

Наибольший общий делитель двух чисел равен произведению общих простых множителей, взятых в меньших степенях, и показывает самую большую общую меру чисел.

Математика

Обратный элемент по модулю через расширенный алгоритм Евклида

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

Математика

Линейное сравнение: решения через НОД коэффициента и модуля

$ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1$

Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.

Математика

Быстрое возведение в степень по модулю двоичным методом

$a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.