Алгоритм Стайна

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



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

В одной из своих предыдущих статей я показал версию евклидова алгоритма для C#, описанную греческим математиком Евклидом Александрийским. Этот алгоритм может быть использован для вычисления наибольшего общего делителя (НОД) двух целых чисел. GCD - это наибольшее целое число, в котором оба целых числа можно разделить без создания остатка. Например, GCD 210 и 124 составляет 42, так как оба значения можно разделить на 42 без остатка, давая результаты 5 и 3 соответственно. Самая базовая версия евклидова алгоритма работает путем многократного вычитания. Я не буду здесь описывать это подробно, лучше посмотрите предыдущую статью.

Алгоритм Стайна

Алгоритм Стайна, опубликованный в 1967 г. Джозеф Стайном, является еще одним алгоритмом для вычисления НОД двух значений. Он оптимизирован для использования в вычислениях, использует быстрые побитовые сдвиги, а не обычно более медленные операции повторного вычитания, деления или модуля . Компьютеры, использующие платформу .NET, как правило, имеют процессоры, которые изначально поддерживают разделение, поэтому разница в эффективности может быть не столь выраженной. Однако алгоритм по-прежнему интересен.

Алгоритм Стейна использует ряд правил:

1. Подобно евклидовому алгоритму, если одно из двух значений равно нулю, результатом алгоритма является другое значение. Результат – это число.
2. Если два целочисленных значения равны, НОД - это значение тоже.
3. Если оба значения являются четными числами, то мы знаем, что значение два является общим делителем. Мы можем разделить оба значения на два, используя операцию сдвига, и найти НОД двух новых значений. Умножая этот результат на два, используя операцию второго сдвига, выдает НОД исходных значений. То есть: НОД (a, b) = 2 · НОД (a / 2, b / 2).
4. Если только одно из значений четное, то мы знаем, что значение два не является общим делителем. Поэтому мы можем разделить четное значение на два и пересчитать НОД. То есть: НОД (четное, нечетное) = НОД (четное/ 2, нечетное).
5. Если оба значения нечетны, нам нужно использовать вычитание таким же образом, как и на одном шаге евклидова алгоритма. Меньшее значение вычитается из большего, и результат используется с меньшим значением для вычисления НОД. То есть: НОД (большее, меньшее) = НОД (большее - меньшее, меньшее). Мы можем сделать еще шаг дальше этого. Когда одно нечетное значение вычитается из другого, мы знаем, что результат будет четным. Это означает, что мы будем вычислять НОД нечетного и четного значения. Поэтому мы можем разделить четное число на два, как на шаге 4. Т.е. НОД (большее, меньшее) = НОД ((большее-меньшее) / 2, меньшее).

Создание метода Stein

Давайте создадим метод, реализующий алгоритм Стайна. Начните с создания сигнатуры, которая соответствует таковой в предыдущем методе Евклида.

public static uint Stein(uint value1, uint value2)
{
}

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

if (val1 == 0) return val2;
if (val2 == 0) return val1;
if (val1 == val2) return val1;

Наконец, мы можем определить, какие из значений являются нечетными и четными, чтобы мы могли применить остальные правила с рекурсивным вызовом. Первый оператор if идентифицирует, когда оба значения четные, и применяет правило 3. Вторые и третьи операторы if фиксируют одно четное и одно нечетное число, применяя правило 4. Последний оператор if и заключительный оператор else выполняются, когда оба значения являются нечетными. Они оба применяют правило 5.

bool val1IsEven = (val1 & 1u) == 0;
bool val2IsEven = (val2 & 1u) == 0;
 
if (val1IsEven && val2IsEven)
    return Stein(val1 >> 1, val2 >> 1) << 1;
else if (val1IsEven && !val2IsEven)
    return Stein(val1 >> 1, val2);
else if (val2IsEven)
    return Stein(val1, val2 >> 1);
else if (val1 > val2)
    return Stein((val1 - val2) >> 1, val2);
else
    return Stein(val1, (val2 - val1) >> 1);

Тестирование метода

Чтобы выполнить простой тест, добавьте следующую строку кода в метод Main и запустите программу. Она вычисляет НОД 116150 и 232704. Результат должен быть равен 202.

int nod = Stein(116150, 232704);

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