Для чего нужен алгоритм евклида

В очередной раз о НОД, алгоритме Евклида и немного об истории алгоритмов вообще. Конечно, с примерами на Swift

Алгоритмы – одна из центральных тем в программировании, они повсюду (особенно на собеседованиях, ха-ха).

(Разве можно обойтись в таком посте без «баяна»?)

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

А Дональд Кнут, небезызвестный автор трактата “Искусство программирования” (и не только), и вовсе считает алгоритм первым в истории (по крайней мере, относительно современных определений). Потому что, не смотря на то, что алгоритм был придуман и использовался еще до, собственно, Евклида, который жил в IV-III вв. до нашей эры (он упоминается уже у Аристотеля, жившего веком ранее), Евклид описывает процесс итеративно, что согласуется с современным значением слова.

Само слово “алгоритм” восходит к имени персидского математика Аль-Хорезми, жившего примерно в VIII-IX вв. уже нашей эры. А началом его использования в смысле, близком современному, считается уже лишь XX век, точнее – его первые десятилетия, восход информационных технологий.

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

Любопытства ради предлагаю ознакомиться с евклидовским описанием алгоритма в редактуре Кнута. Оно довольно длинное, поэтому спрятано под катом:

Предложение. Для данных двух положительных целых чисел найти их наибольший общий делитель.

Пусть A и C – два заданных положительных целых числа; требуется найти их НОД. Если число A делится на C, то число C есть общий делитель чисел C и A, поскольку оно делит самое себя. И очевидно, что оно будет и наибольшим делителем, поскольку нет числа большего, чем число C, которое бы делило C.

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

Теперь положим, что E – положительный остаток от деления числа A на C; пусть F – положительный остаток от деления числа C на число E и пусть F делит E. Так как F делит E, а E делит C — F, F также делит C — F. Но оно делит и самое себя, поэтому F делит C, а C делит A — E; поэтому F делит также A — E, но оно делит и E; поэтому F делит A. Следовательно F является общим делителем чисел A и C.

Теперь я утверждаю, что оно является и НОД. Действительно, если F – не наибольший общий делитель чисел A и C, то найдется большее число, которое будет делить оба этих числа. Пусть таким числом будет G.

Так как число G делит число C, а число C – делит A — E, то G также делит число A — E. Число G делит также все число A, поэтому оно делит и остаток E. Но E делит C — F, поэтому G также делит C — F. А число G также делит все число C, так как оно делит и остаток F; таким образом, большее число делит меньшее, а это невозможно.

Таким образом, нет такого числа, большего, чем F, которое бы делило A и C; значит, число F является НОД.

Следствие. Это рассуждение делает очевидным предположение, что всякое число, делящее два числа, делит и их НОД. Ч.т.д.

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

Вот пример функции, написанной на «Swift», реализации первого способа:

Здесь, переиспользования ради, я вынес в отдельную функцию случаи поиска НОД, когда он известен сразу, без необходимости следования какому-либо алгоритму:

(Если два числа равны, то, естественно, их НОД также равен им. Если какое-то из чисел равно нулю, то НОД будет равняться второму числу, т.к. ноль делится любым числом (с результатом, понятное дело, тоже ноль).)

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

А вот так может выглядеть реализация версии алгоритма делением:

Вторая версия в наши дни считается предпочтительней, так как содержит в себе, в среднем, ощутимо меньшее количество шагов. Тем не менее, во времена, когда компьютеры были большие и медленные, операция деления могла быть сама по себе сложной процедурой. И тогда первая версия алгоритма могла оказаться эффективней.

В качестве входных данных я использовал массив пар случайных чисел. Замеры производились, естественно, с использованием одного и того же массива для каждого способа. Разброс чисел для пар я взял от нуля до 9999. Замеры производились на количестве вычислений (пар чисел): одно, десять, 100, 1000, 10000, 100000, 1000000 и 10000000. Последнее заставляло ожидать результата уже несколько минут, поэтому на нем я решил остановиться.

Вот простой код генерации входных данных:

Сам замер выглядит, например, так:

А вот так выглядят результаты запуска на моем компьютере:

(Subtraction – вычитание, division – деление.)

В общем, очень хорошо видно, как сильно на современных компьютерах проигрывает метод вычитания.

«Улучшенная» версия алгоритма Евклида

В литературе можно встретить версию алгоритма, в которой одно из чисел на каждом шаге вместо остатка от деления на второе заменяется на разность между этим отстатком и вторым числом, но только в случае, если остаток от деления больше половины второго числа. Реализация этой версии может выглядеть так:

Такая модификация сокращает количество шагов алгоритма, но, судя по результатам замеров на моем компьютере, дополнительные вычисления и проверки на каждом шаге, нейтрализуют это преимущество и даже более:

(Improved – «улучшенная» версия.)

Еще немного о значимости алгоритма Евклида

Алгоритм имеет также геометрическую версию (для нахождения наибольшей меры двух отрезков).

Алгоритм был, конечно, обощен и для нахождения НОД любого количества чисел, не только двух. В двух словах идея такова: если обозначить функцию поиска НОД двух чисел как gcd(a, b), то, скажем, НОД трех чисел gcd(a, b, c) равен gcd(gcd(a, b), c). И так далее, для любого количества чисел НОД находится последовательным вычислением НОД НОД-а предыдущей пары чисел и следующего числа. Хотя, конечно, это касается поиска НОД вообще, а не только алгоритма Евклида.

Существует также обощение алгоритма для нахождения НОД полиномов. Но это уже выходит за рамки этого несложного поста, а в некоторой степени, и моих познаний в математике.

Сложность алгоритма Евклида

Временная сложность алгоритма исследовалась давно, не быстро и гораздо более учеными мужами, чем ваш покорный слуга. Тем не менее, вопрос давно закрыт и ответ получен. Собственно, еще в середине позапрошлого века. Габриэлем Ламе.

Если коротко, то ответ формулируется, собственно, теоремой Ламе, связанной с этим алгоритмом. Количество шагов алгоритма будет равно порядковому номеру ближайшего большего числа Фибоначчи наименьшему из двух чисел входных параметров минус 2. Оперируя чуть более традиционно-математическими обозначениями, то если u > v (и v > 1), то число проходов алгоритма будет равняться n — 2 при v

Источник

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

Содержание

История

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную по отношению теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

Алгоритм Евклида для целых чисел

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

b > r_1 > r_2 > r_3 > r_4 > \cdots >r_n» border=»0″ />

определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

Тогда НОД(a,b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.

Существование таких , то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

Проще сформулировать алгоритм Евклида так: если даны натуральные числа и и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Пример

Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала, от 1071 отнимем кратное значение 462, пока не получим разность меньше чем 462. Мы должны дважды отнять 462, (q₀ = 2), оставаясь с остатком 147

Затем от 462 отнимем кратное значение 147, пока не получим знаменатель меньше чем 147. Мы должны трижды отнять 147 (q₁ = 3), оставаясь с остатком 21.

Затем от 147 отнимем кратное значение 21, пока не получим знаменатель меньше чем 21. Мы должны семь раз отнять 21 (q₂ = 7), оставаясь без остатка.

Таким образом последовательность a>b>R1>R2>R3>R4>. >Rn в данном конкретном случае будет выглядеть так:

Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462)=21.

В табличной форме, шаги были следующие

Расширенный алгоритм Евклида и соотношение Безу

Формулы для могут быть переписаны следующим образом:

НОД

здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

Связь с цепными дробями

Отношение допускает представление в виде цепной дроби:

.

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу , взятому со знаком минус:

.

Последовательность равенств, задающая алгоритм Евклида может быть переписана в форме

Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объединены в форме

Третье равенство может быть использовано чтобы заменить знаменатель выражения r₁/r₀, получим

Последнее отношение остатков r_k/r_k−1 всегда может быть заменено используя следующее равенство в последовательности, и так до последнего уравнения. Результатом является цепная дробь

В приведённом выше примере, НОД(1071, 462) было посчитано и были найдены частные q_k 2,3 и 7 соответственно. Поэтому, 1071/462 может быть записана как

Вариации и обобщения

Обобщённый алгоритм Евклида для многочленов

Алгоритм Евклида и расширенный алгоритм Евклида естественным образом обобщается на кольцо многочленов k[x] от одной переменной над произвольным полем k, поскольку для таких многочленов определена операция деления с остатком. При выполнении алгоритма Евклида для многочленов аналогично алгоритму Евклида для целых чисел, получается последовательность полиномиальных остатков (PRS).

Пример для кольца Z[x]

Пусть cont(f) по определению — НОД коэффициентов многочлена f(x) из Z[x] — содержание многочлена. Частное от деления f(x) на cont(f) называется примитивной частью многочлена f(x) и обозначается primpart(f(x)).

эти определения понадобятся для нахождения НОД двух многочленов p1(x) и p2(x) в кольце Z[x]. Для многочленов над целыми числами верно следующее:

НОДНОД, НОДНОД.

Таким образом задача отыскания НОД двух произвольных многочленов сводится к задаче отыскания НОД примитивных полиномов.

Пусть есть два примитивных многочлена p1(x) и p2(x) из Z[x], для которых выполняется соотношение между их степенями: deg(p1(x)) = m и deg(p2(x)) = n, m > n. Деление многочленов с остатком предполагает точную делимость старшего коэффициента делимого на старший коэффициент делителя, в общем случае деление с остатком выполнить невозможно. Поэтому вводят алгоритм псевдоделения, который всё же позволяет получить псевдочастное и псевдоостаток (prem), которые будут сами по себе принадлежать множеству многочленов над целыми числами.

Под псевдоделением будем понимать, что самому делению предшествует умножение полинома p1(x) на , то есть , , где и — соответственно псевдочастное и псевдоостаток.

Итак, — (принадлежат кольцу многочленов над целыми числами), причём . Тогда алгоритм Евклида состоит из следующих шагов:

1. Вычисление НОД содержаний:

НОД.

2. Вычисление примитивных частей:

.

3. Построение последовательности полиномиальных остатков:

.

4. Выход и возврат результата:

Если , то вернуть , иначе вернуть .

Ускоренные версии алгоритма

См. также

Литература

Полезное

Смотреть что такое «Алгоритм Евклида» в других словарях:

алгоритм Евклида — Метод нахождения наибольшего общего делителя, названный так по имени древнегреческого математика, который впервые описал его в III веке до нашей эры. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации EN… … Справочник технического переводчика

Расширенный алгоритм Евклида — Алгоритм Евклида алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин. Содержание 1 История 2 Алгоритм Евклида для целых чисел … Википедия

Алгоритм Шенкса — (англ. Baby step giant step; также называемый алгоритм больших и малых шагов) в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… … Википедия

Алгоритм Фюрера — (англ. Fürer’s algorithm) быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером[1] из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его… … Википедия

Евклида алгоритм — Алгоритм Евклида алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин. Содержание 1 История 2 Алгоритм Евклида для целых чисел … Википедия

Алгоритм — У этого термина существуют и другие значения, см. Алгоритм (значения). Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правил … Википедия

АЛГОРИТМ — (алгорифм), единообразная математическая процедура ( рецепт ) для решения однотипных задач, выполняемая по строго определенным правилам. Применение алгоритма позволяет получить ответ типа да или нет на любой вопрос в классе задач, для решения… … Энциклопедия Кольера

Алгоритм Монтгомери — Алгоритм Монтгомери приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведение числа в степень по модулю, когда модуль велик (порядка сотен бит). Был предложен в 1985 году Питером… … Википедия

ЕВКЛИДА АЛГОРИТМ — способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом … Большой Энциклопедический словарь

Евклида алгоритм — способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом. * * * ЕВКЛИДА АЛГОРИТМ ЕВКЛИДА АЛГОРИТМ, способ нахождения наибольшего общего делителя двух… … Энциклопедический словарь

Источник