Расширенный алгоритм евклида python

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Алгоритм нахождения НОД делением

  1. Большее число делим на меньшее.
  2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
  3. Если есть остаток, то большее число заменяем на остаток от деления.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

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

Алгоритм нахождения НОД вычитанием

  1. Из большего числа вычитаем меньшее.
  2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
  3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 — 18 = 12
18 — 12 = 6
12 — 6 = 6
6 — 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

Читайте также  Преобразовать формат видео wmv в

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

воскресенье, 3 апреля 2011 г.

Алгоритм Евклида

Алгоритм Евклида (описание с Вики)

Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел
r_2 > r_3 > r_4 > cdots >r_n" > определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
a = bq + r1 b = r1q1 + r2 r1 = r2q2 + r3 rk − 2 = rk − 1qk − 1 + rk rn − 1 = rnqn Тогда НОД(a,b), наибольший общий делитель a и b , равен rn , последнему ненулевому члену этой последовательности.

Описание алгоритма нахождения НОД вычитанием

  1. Из большего числа вычитаем меньшее.
  2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
  3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
  4. Переходим к пункту 1.

Конкретная реализация алгоритма:

А вот нормальная его реализация (аналог из видеолекции с применением рекурсии). Тут применена идея поочередного деления, поэтому назовем его , как не трудно догадаться, :)) метод поочередного деления.

Так же существует его реализация в не рекурсивном виде

И должен признаться, что с точки зрения производительности он предпочтительнее. Основные причины — стек рекурсиии (т.е. доп. память на хранение и доп. время на доступ к заранее сохраненным данным), об этом вы так же можете услышать из видео лекции. Там же затронули связь НОД и НОК (наименьшее общее кратное).
Вот что написано в вике на этот счет:

Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n. Обозначается НОК(m,n) или [m,n] , а в английской литературе lcm(m,n).
НОК для ненулевых чисел m, n всегда существует и связан с НОД следующим соотношением:

Таким образом поиск НОК выглядит следующим образом

Читайте также  Программа для изготовления загрузочной флешки

Хочу обратить ваше внимание на то, что сначалы мы делим на НОД а потом умножаем, таким образом мы защищаем себя от переполнения при произведении 2-х больших цифр.

Интересное: Тот факт, что число шагов, затрачиваемых алгоритмом Евклида, растет логарифмически, связан с числами Фибоначчи:

Теорема (Ламэ, 1845 г.). Пусть n О N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а — наименьшее с таким свойством. Тогда а = F n +2 , b = F n +1 , где F k k- ое число Фибоначчи.

Доказательство можно посмотреть, например, здесь: http://virlib.eunnet.net/books/numbers/text/10.html
С помощью этой теоремы можно оценить порядок роста алгоритма Евклида. Пусть a будет меньшим из двух аргументов процедуры. Если процесс завершается за k шагов, тогда должно выполняться a>=Fib(k), т.е. приблизительно равно f^5/sqrt(5) — золотое сечение. Следовательно, число шагов k растет как логарифм a(по основанию f)!

Теперь по-поводу тестирования. Для этого я использую стандартный python profile.
Само собой 1 запуск любого из 3-х вариантов будет производителен, посему я сделал это по 2000 раз, чтобы увидеть разницу.
Результат, полностью подтвердил теорию:

  • Самым медленным оказался метод последовательной разницы 2004 function calls in 3.086 seconds
  • Сильно быстрее — метод поочередного деления в рекурсивном виде 13743 function calls (2004 primitive calls) in 0.088 seconds
  • Ну и победитель забега — метод поочередного деления в не рекурсивном 2004 function calls in 0.014 seconds

* — небольшое пояснение ко 2-му результату. Кто-то может не понять откуда берётся 13743 вызова ф-ии. Ответ кроется как раз в рекурсии, а именно в стеке рекурсии. Т.е. эта циферка говорит, что при вызове 2000 поисков НОД, было выполнено 13739 рекурсивных запусков.

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

Читайте также  Последние снимки из космоса

Основной евклидов алгоритм для GCD
Алгоритм основан на следующих фактах.

  • Если мы вычтем меньшее число из большего (мы уменьшим большее число), GCD не изменится. Так что, если мы продолжаем вычитать многократно большее из двух, мы получим GCD.
  • Теперь вместо вычитания, если мы разделим меньшее число, алгоритм останавливается, когда мы находим остаток 0.

Ниже приведена рекурсивная функция для оценки gcd с использованием алгоритма Евклида.

ссылка на сайт
brightness_4
код

ссылка на сайт
brightness_4
код

Джава

ссылка на сайт
brightness_4
код

python3

ссылка на сайт
brightness_4
код

ссылка на сайт
brightness_4
код

ссылка на сайт
brightness_4
код

Сложность времени: O (Log min (a, b))

Расширенный евклидов алгоритм
Расширенный евклидов алгоритм также находит целые коэффициенты x и y, такие что:

Примеры:

Расширенный алгоритм Евклида обновляет результаты gcd (a, b), используя результаты, вычисленные с помощью рекурсивного вызова gcd (b% a, a). Пусть значения x и y, вычисленные по рекурсивному вызову, будут x 1 и y 1 . x и y обновляются с использованием приведенных ниже выражений.

Рекомендовано: Пожалуйста, сначала решите вопрос по « ПРАКТИКЕ », прежде чем переходить к решению.

Ниже приведена реализация на основе приведенных выше формул.

ссылка на сайт
brightness_4
код

Джава

ссылка на сайт
brightness_4
код

python3

ссылка на сайт
brightness_4
> code

ссылка на сайт
brightness_4
код

ссылка на сайт
brightness_4
код

Как работает расширенный алгоритм?

Чем полезен расширенный алгоритм?
Расширенный евклидов алгоритм особенно полезен, когда a и b взаимно просты (или gcd равен 1). Поскольку x является модульным мультипликативным обратным к «по модулю b», а y является модульным мультипликативным обратным к «b по модулю a». В частности, вычисление модульного мультипликативного обратного является важным шагом в методе шифрования с открытым ключом RSA.

Эта статья предоставлена Анкуром . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Ссылка на основную публикацию
Adblock
detector