Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

Алгори́тм Эвкли́даалгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин.

История Править

Древнегреческие математики называли этот алгоритм мща  или оеоа — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

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

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

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

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

r_1 = a + b(-q_0)
r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)
\cdots
\gcd (a,b) = r_n = as + bt

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

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

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

\frac ab=[q_0; q_1, q_2,\cdots,q_n].

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

[q_0; q_1, q_2,\cdots,q_{n-1}] = -\frac ts.

Вариации и обобщения Править

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

  • Одним из методов ускорения целочисленного алгоритма Евклида является использования симметричного остатка:
r_i \equiv r_{i-2} \pmod{r_{i-1}},
где
-\frac{r_{i-1}}{2}\leq r_i\leq\frac{r_{i-1}}{2}.
  • Одна из наиболее многообещающих версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии Разделяй и Властвуй позволяет уменьшить асимптотическую сложность алгоритма.

См. также Править

Литература Править

  • Виноградов И. М. Основы теории чисел.
  • Курант Р., Роббинс Г. Что такое математика? Дополнение к главе I, § 4.
  • Щетников А. И. Алгоритм Евклида и непрерывные дроби. Новосибирск: АНТ, 2003.
  • Fowler D. H. The Mathematics of Plato’s Academy: a new reconstruction. 2nd ed. Oxford: Clarendon Press, 1999.
  • von zur Gathen J., Gerhard J. Modern Computer Algebra. ISBN 0-521-82646-2


ar:خوارزمية إقليدس bg:Алгоритъм на Евклид ca:Algorisme d'Euclides cs:Euklidův algoritmusel:Αλγόριθμος του Ευκλείδη Шаблон:Link FA eo:Eŭklida algoritmohu:Euklideszi algoritmus id:Algoritma Euklideanlt:Euklido algoritmas lv:Eiklīda algoritms mn:Евклидийн алгоритм nds:Euklidsch Algorithmus nl:Algoritme van Euclides no:Euklids algoritme pl:Algorytm Euklidesasimple:Euclidean algorithm sl:Evklidov algoritem sr:Еуклидов алгоритам sv:Euklides algoritmuk:Алгоритм Евкліда vi:Giải thuật Euclid

Викия-сеть

Случайная вики