ВВЕДЕНИЕ 3
1. Применение и актуальность алгоритма Евклида 5
2. Средства программной реализации 7
3. Различные методы реализации алгоритма Евклида 9
3.1. Классический алгоритм Евклида 9
3.2. Бинарный алгоритм Евклида 10
3.3. k-арный алгоритм Евклида 11
3.4. Ассоциативный k-арный алгоритм Евклида 13
4. Сравнивание различных методов реализации алгоритма Евклида 17
4.1. Сравнивание классического алгоритма Евклида 17
4.2. Сравнивание бинарного алгоритма Евклида 19
4.3. Сравнивание k-арного алгоритма Евклида 20
4.4. Сравнивание ассоциативного k-арного алгоритма Евклида 21
4.5. Сравнивание наиболее оптимальных методов реализации алгоритма Евклида 23
5. Методы быстрого умножения больших чисел 25
5.1. Алгоритм Карацубы 25
5.2. Алгоритм Тоома-Кука 26
5.3. Алгоритм Шёнхаге — Штрассена 28
5.4. Сравнивание методов быстрого умножения больших чисел 29
6. Дерево Штерна-Броко 31
7. Оптимизация ассоциативного k-арного алгоритма Евклида 33
7.1. Сравнивание применения дерева Штерна-Броко при различных параметрах k 33
7.2. Пример работы модифицированного ассоциативного k-арного алгоритма 35
7.3. Сравнивание модифицированного и исходного ассоциативных алгоритмов 38
7.4. Сравнивание модифицированного и всех рассмотренных версий алгоритма Евклида 39
ЗАКЛЮЧЕНИЕ 42
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 44
ПРИЛОЖЕНИЕ

Купить

Целью данной работы является разработка модернизированного ассоциативного k-арного алгоритма Евклида.
Алгоритм Евклида является старейшим математическим алгоритмом, применяемым в наше время. Данный алгоритм во всех своих различных методах реализации по сей день применяется в математике и криптографии. С его помощью можно эффективным и быстрым способом найти наибольший общий делитель (НОД) двух целых чисел А > В > 0, определить являются ли два положительных числа взаимно простыми . Со временем у алгоритма появились различные методы его реализации для увеличения его эффективности при работе с большими числами.
В нашей работе мы рассмотрим:
• Классический алгоритм Евклида
• Бинарный алгоритм Евклида
• k-арный алгоритм Евклида
• Ассоциативный k-арный алгоритм Евклида
Для того чтобы найти возможность модификации самой современной его версии, мы постараемся углубленно изучить алгоритм Евклида. Для этого мы реализуем упомянутые выше методы реализации алгоритма Евклида поиска наибольшего общего делителя. Сравним данные алгоритмы по различным параметрам (скорости работы и количеству итераций), а также на основе получившихся результатов выдвинем предположения по оптимизации работы последней предложенной версии алгоритма Евклида.
Также для ускорения умножения больших чисел, рассмотрим, реализуем и сравним друг с другом (по времени работы) методы быстрого умножения:
• алгоритм Карацубы
• алгоритм Тоома-Кука
• алгоритм Шёнхаге — Штрассена
Для поиска правильной дроби в ассоциативном k-арном алгоритме Евклида, представленном в статье [1], рассмотрим дерево всех неотрицательных несократимых дробей — дерево Штерна-Броко. Сравним его использование со стандартным применением ряда Фарея. Для этого встроим функцию построения дерева и поиска коэффициентов х, у в ассоциативный k-арный алгоритм и сравним его с исходным вариантом по различным параметрам (времени работы и количеству итераций).

Купить