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


Купить