Бинарный алгоритм НОД

Визуализация использования алгоритма двоичного НОД для поиска наибольшего общего делителя (НОД) чисел 36 и 24. Таким образом, НОД равен 2. ² × 3 = 12.

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

Хотя алгоритм в его современном виде был впервые опубликован израильским физиком и программистом Йозефом Штейном в 1967 году. возможно, он был известен во II веке до нашей эры в древнем Китае.

Алгоритм

Алгоритм находит НОД двух неотрицательных чисел. $u$ и $v$ неоднократно применяя эти тождества:

1. $\gcd(u,0)=u$: все делит ноль, и $u$ самое большое число, которое делит $u$.
2. $\gcd(2u,2v)=2\cdot \gcd(u,v)$: $2$ является общим делителем.
3. $\gcd(u,2v)=\gcd(u,v)$ если $u$ странно: $2$ тогда не является общим делителем.
4. $\gcd(u,v)=\gcd(u,v-u)$ если $u,v$ странный и $u\leq v$.

Поскольку НОД коммутативен ( $\gcd(u,v)=\gcd(v,u)$), эти идентификаторы по-прежнему применяются, если операнды поменяны местами: $\gcd(0,v)=v$, $\gcd(2u,v)=\gcd(u,v)$ если $v$ это странно и т. д.

Выполнение

Хотя приведенное выше описание алгоритма математически корректно, производительные программные реализации обычно отличаются от него по нескольким заметным признакам:

• избегая пробного деления на $2$ в пользу одного битового сдвига и примитива подсчета конечных нулей ; это функционально эквивалентно многократному применению тождества 3, но гораздо быстрее;
• выражение алгоритма итеративно, а не рекурсивно : результирующую реализацию можно спланировать так, чтобы избежать повторной работы, вызывая идентификатор 2 в начале и сохраняя инвариантом то, что оба числа нечетны при входе в цикл, который должен реализовать только идентификаторы 3 и 4;
• делая тело цикла свободным от ветвей, за исключением условия выхода ( $v=0$): в приведенном ниже примере обмен $u$ и $v$ (обеспечение $u\leq v$) компилируется в условные ходы ; труднопрогнозируемые ветки могут оказать большое негативное влияние на производительность.

Ниже приведена реализация алгоритма на Rust, иллюстрирующая эти различия, адаптированная из uutils :

use std::cmp::min;
use std::mem::swap;

pub fn gcd(mut u: u64, mut v: u64) -> u64 {
    // Base cases: gcd(n, 0) = gcd(0, n) = n
    if u == 0 {
        return v;
    } else if v == 0 {
        return u;
    }

    // Using identities 2 and 3:
    // gcd(2ⁱ u, 2ʲ v) = 2ᵏ gcd(u, v) with u, v odd and k = min(i, j)
    // 2ᵏ is the greatest power of two that divides both 2ⁱ u and 2ʲ v
    let i = u.trailing_zeros();  u >>= i;
    let j = v.trailing_zeros();  v >>= j;
    let k = min(i, j);

    loop {
        // u and v are odd at the start of the loop
        debug_assert!(u % 2 == 1, "u = {} should be odd", u);
        debug_assert!(v % 2 == 1, "v = {} should be odd", v);

        // Swap if necessary so u ≤ v
        if u > v {
            swap(&mut u, &mut v);
        }

        // Identity 4: gcd(u, v) = gcd(u, v-u) as u ≤ v and u, v are both odd 
        v -= u;
        // v is now even

        if v == 0 {
            // Identity 1: gcd(u, 0) = u
            // The shift by k is necessary to add back the 2ᵏ factor that was removed before the loop
            return u << k;
        }

        // Identity 3: gcd(u, 2ʲ v) = gcd(u, v) as u is odd
        v >>= v.trailing_zeros();
    }
}

Примечание. Приведенная выше реализация принимает беззнаковые (неотрицательные) целые числа; при условии $\gcd(u,v)=\gcd(\pm {}u,\pm {}v)$, подписанный случай можно обработать следующим образом:

/// Computes the GCD of two signed 64-bit integers
/// The result is unsigned and not always representable as i64: gcd(i64::MIN, i64::MIN) == 1 << 63
pub fn signed_gcd(u: i64, v: i64) -> u64 {
    gcd(u.unsigned_abs(), v.unsigned_abs())
}

Сложность

Асимптотически алгоритм требует $O(n)$ шаги, где $n$ - это количество битов в большем из двух чисел, поскольку каждые два шага уменьшают хотя бы один из операндов как минимум в раз. $2$. Каждый шаг включает в себя всего несколько арифметических операций ( $O(1)$ с небольшой константой); при работе с числами размером в слово каждая арифметическая операция преобразуется в одну машинную операцию, поэтому количество машинных операций порядка $n$, то есть $\log _{2}(\max(u,v))$.

Для сколь угодно больших чисел асимптотическая сложность этого алгоритма равна $O(n^{2})$, поскольку каждая арифметическая операция (вычитание и сдвиг) включает в себя линейное количество машинных операций (по одной на слово в двоичном представлении чисел). Если числа могут быть представлены в памяти машины, т. е. каждого числа размер может быть представлен одним машинным словом, эта граница сводится к: $$O\left({\frac {n^{2}}{\log _{2}n}}\right)$$

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

Расширения

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

Расширенный двоичный алгоритм НОД , аналог расширенного алгоритма Евклида , подходит для первого типа расширения, поскольку он предоставляет коэффициенты Безу : целые числа. в дополнение к НОД $a$ и $b$ такой, что $a\cdot {}u+b\cdot {}v=\gcd(u,v)$.

В случае больших целых чисел лучшая асимптотическая сложность равна $O(M(n)\log n)$, с $M(n)$ стоимость $n$-битовое умножение; это почти линейно и значительно меньше, чем алгоритм двоичного НОД. $O(n^{2})$, хотя конкретные реализации превосходят старые алгоритмы только для чисел размером более 64 килобит ( т. е. более 8×10 ¹⁹²⁶⁵ ). Это достигается за счет расширения двоичного алгоритма НОД с использованием идей алгоритма Шёнхаге – Штрассена для быстрого умножения целых чисел.

Алгоритм двоичного НОД также был распространен на области, отличные от натуральных чисел, такие как целые гауссовы числа . Целые числа Эйзенштейна , квадратичные кольца, и целочисленные кольца числовых полей .

Историческое описание

Алгоритм вычисления НОД двух чисел был известен в древнем Китае, при династии Хань , как метод сокращения дробей:

Если возможно, сократите его вдвое; в противном случае возьмите знаменатель и числитель, вычтите меньшее из большего и сделайте это поочередно, чтобы они стали одинаковыми. Уменьшите на такое же количество.

- Фангтянь - Землеустройство, Девять глав математического искусства

Фраза «если возможно, сократите вдвое» двусмысленна,

• если это применимо, когда любое из чисел становится четным, алгоритм представляет собой двоичный алгоритм НОД;
• если это применимо только тогда, когда оба числа четные, алгоритм аналогичен алгоритму Евклида .

См. также

• Евклидов алгоритм
• Расширенный алгоритм Евклида
• Наименьшее общее кратное

Дальнейшее чтение

• Кнут, Дональд (1998). «§4.5 Рациональная арифметика». Получисловые алгоритмы . Искусство компьютерного программирования . Том. 2 (3-е изд.). Аддисон-Уэсли. стр. 330–417. ISBN  978-0-201-89684-8 .

Охватывает расширенный двоичный НОД и вероятностный анализ алгоритма.

• Коэн, Анри (1993). «Глава 1: Фундаментальные теоретико-числовые алгоритмы». Курс вычислительной алгебраической теории чисел . Тексты для аспирантов по математике . Том. 138. Шпрингер-Верлаг . стр. 12–24. ISBN  0-387-55640-0 .

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

• Валле, Бриджит (сентябрь – октябрь 1998 г.). «Динамика бинарного алгоритма Евклида: функциональный анализ и операторы» . Алгоритмика . 22 (4): 660–685. дои : 10.1007/PL00009246 . S2CID   27441335 . Архивировано из оригинала (PS) 13 мая 2011 года.

Анализ алгоритма в среднем случае через призму функционального анализа : основные параметры алгоритмов представлены как динамическая система , а их среднее значение связано с инвариантной мерой системы передаточного оператора .

Внешние ссылки

• Словарь алгоритмов и структур данных NIST: двоичный алгоритм GCD
• Разрезание узла: двоичный алгоритм Евклида при разрезании узла
• Анализ двоичного евклидова алгоритма (1976), статья Ричарда П. Брента , включая вариант с использованием сдвигов влево