На нашем сайте мы используем cookie для сбора информации технического характера и обрабатываем IP-адрес вашего местоположения. Продолжая использовать этот сайт, вы даете согласие на использование файлов cookies. Здесь вы можете узнать, как мы пользуемся файлами cookies.
Я согласен
логотип upread.ru

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



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



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

В одной из своих предыдущих статей я показал версию евклидова алгоритма для 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);


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


Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.



тегистатьи IT, си шарп, алгоритмы, нод





Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.




Урок 17. Конвертация чисел в строки (Number в String) C#
Задача с массой на Java


© upread.ru 2013-2022
При перепечатке активная ссылка на сайт обязательна.
Задать вопрос
письмо
Здравствуйте! Вы можете задать мне любой вопрос. Если не получается отправить сообщение через эту форму, то пишите на почу up777up@yandex.ru
Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.