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

Материал из Википедии — свободной энциклопедии

Имеется викиучебник по теме:
Алгоритм Евклида

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

[править] История

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

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

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

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

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

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

a = bq₀ + r₁

b = r₁q₁ + r₂

r₁ = r₂q₂ + r₃

r_{k − 2} = r_{k − 1}q_{k − 1} + r_k

r_{n − 1} = r_nq_n

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

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

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

• Пусть a = bq + r, тогда gcd(a,b) = gcd(b,r).
• gcd(0,r) = r для любого ненулевого r.

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

На С

// фукнция получения НОД
int NOD(int a, int b)
{
// пока числа не равны 0
while(a!=0 && b!=0)
{
if(a>=b) a=a%b;
else b=b%a;
}
return a+b; // Одно - ноль
}

взято с [1]

Альтернативный алгоритм, с использованием рекурсии

int NOD(int a, int b) {
        //Если а делится на b без остатка, значит найден общий делитель, ф-я завершается
	if(a%b == 0) {
		return b;
	}
	//Иначе вызываем ф-ю опять, передавая второе число и остаток от деления первого на второе
	else { 
		return NOD(b, a%b);
	}	
}

взято из книги Брайона Оверленда С++ Без страха Изд-во Триумф 2005 ISBN 5-89392-107-0

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

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

r₁ = a + b( - q₀)

r₂ = b − r₁q₁ = a( − q₁) + b(1 + q₁q₀)

gcd(a,b) = r_n = as + bt

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

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

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

.

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

.

[править] Вариации и обобщения

• Кольца в которых применим алгоритм Евклида, называются евклидовыми кольцами, к ним относятся в частности кольцо многочленов.

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

• Одним из методов ускорения целочисленного алгоритма Евклида является использования симметричного остатка:

где

• Одна из наиболее многообещающих версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. При применении стратегии Divide & Conqurer наблюдается большое ускорение асимптотической скорости алгоритма.

[править] См. также

• Евклидово кольцо
• Непрерывная дробь
• Примеры реализации алгоритма Евклида
• Обоснование Алгоритма Евклида

[править] Литература

• Виноградов И. М. Основы теории чисел.
• Курант Р., Роббинс Г. Что такое математика? Дополнение к главе 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