Тема: АНАЛИЗ СОВРЕМЕННЫХ АЛГОРИТМОВ НАХОЖДЕНИЯ НОД

Одной из центральных задач в компьютерной алгебре является вычисление набольшего общего делителя (НОД), в частности, при вычислении над рациональными или модульными числами.
Существует множество теоретических и практических применений набольшего общего делителя. В частности, он является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции. Также используется при решении линейных диофантовых уравнений, при построении непрерывных дробей, в методе Штурма, является основным инструментом для доказательства теорем в современной теории чисел, например, таких как теорема Лагранжа о сумме четырёх квадратов и основная теорема арифметики.
Один из основных и самых первых способов нахождения набольшего общего делителя является Алгоритм Евклида. Первое описание алгоритма находится в «Началах» Евклида (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Однако в XIX веке он был обобщён на другие типы чисел, такие как целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида также был обобщён на другие математические структуры, такие как узлы и многомерные полиномы.
В этой работе рассматриваются различные алгоритмы вычисления НОД для 2х чисел: алгоритм Евклида, Бинарный алгоритм, К-арный алгоритм, Ассоциативный к-арный алгоритм. Осуществляется программная реализация, сравнение скорости работы, сравнение количества итераций необходимых для вычисления НОД для этих алгоритмов. Исследование влияния входных и других параметров на работу алгоритма.

Купить

В работе рассматривались алгоритмы нахождения наибольшего общего делителя двух целых чисел: Алгоритм Евклида, Бинарный алгоритм, K-арный алгоритм, Ассоциативный к-арный алгоритм. Алгоритмы были реализованы на языке программирования Ruby, а также проведено тестирование и получение временных и итерационных характеристик этих алгоритмов на множестве различных сгенерированных наборов тестовых чисел. Затем был осуществлено анализ полученных результатов. В результате получили то, что наиболее быстрым по времени работы стал Алгоритм Евклида. Немного странно, учитывая то, что это и наиболее простой алгоритм. Несмотря на то, что в бинарном используется, казалось бы, более быстрая операция двоичного сдвига. Видимо, современное «железо» гораздо быстрее осуществляет медленную операцию деления с остатком. Наименьшее число итераций, как и ожидалось, у Ассоциативного к-арного алгоритма, но по времени он заметно проигрывает всем остальным алгоритмам. Однако, замечено то, что при росте входных аргументов Ассоциативный к-арный алгоритм замедляется заметно медленнее остальных алгоритмов. Опытным путем выявлено, что Алгоритм Евклида дольше работает при близких по значению аргументах, а для Ассоцивного к-арного алгоритма, напротив, такое соотношение аргументов оптимально, это справедливо и для обычного К-арного алгоритма. На Бинарный алгоритм данный параметр не оказывает влияния, для данного алгоритма важно лишь максимальное из значений аргументов. Если же разница между аргументами большая, то тут все наоборот, Алгоритм Евклида в лидерах, К- арные алгоритмы в аутсайдерах. По результатам 10-15 было выявлено оптимальное значение параметра «К» для К-арных алгоритмов. Для стандартного К-арного алгоритма оптимальным значением является 256 либо 512. Для Ассоциативного к-арного алгоритма этот параметр равен 512.

Купить