Проведенное исследование по теме «Улучшение алгоритма кольцевой факторизации для построения простых чисел» позволяет сделать следующие выводы.
Первая задача, поставленная в данной работе, заключалась в том, чтобы проанализировать различные подходы к поиску простых чисел. В результате выполнения первой задачи установлено, что асимптотически наиболее быстрым является решето Аткина. При этом огромное значение имеет использование различных способов оптимизации алгоритмов просеивания. А лучше всего оптимизациям поддается решето Эратосфена.
Вторая задача, сформулированная в работе, предполагала выбор и реализацию наиболее эффективных алгоритмов поиска простых чисел. При выполнении этой части работы были реализованы и улучшены решета Сундарама, Аткина и Эратосфена. При их оптимизации использовались такие способы как: битовое сжатие, быстрый подсчет нулевых битов, оптимизация на уровне кода. Для решета Аткина также был разработан собственный метод оптимизации алгоритма, учитывающий его особенности. Этот метод меняет структуру основных циклов алгоритма таким образом, что удается полностью избавиться от тяжелых для процессора операций умножения и нахождения остатка от деления в основном теле цикла. Тестирование, проведенное в третьей главе работы, показало, что в режиме компиляции без автоматической оптимизации кода этот метод улучшения решета Аткина дает прирост скорости работы более чем в 10 раз!
Третья задача заключалась в реализации алгоритма кольцевой факторизации на основе решета Эратосфена. В работе был реализован алгоритм кольцевой факторизации 2-го и 3-его порядка. В сочетании с сегментированным решетом был реализован алгоритм кольцевой факторизации 2-го порядка.
Четвертой задачей в работе было улучшение алгоритма кольцевой факторизации. Для сегментированного решета Эратосфена со 2 порядком кольцевой факторизации также было использовано битовое сжатие. Помимо этого, для него был реализован способ быстрого подсчета количества простых чисел, ускоряющий эту часть алгоритма как минимум в 25 раз! Также был разработан и реализован собственный способ улучшения алгоритма, позволяющий снизить расход памяти на хранение базы простых чисел в 4 раза! Использование этого подхода уменьшает общий расход оперативной памяти алгоритмом примерно втрое и делает его практически не ощутимым при просеивании любых 64 битных чисел. Дополнительно ко всем внесенным улучшениям был реализован способ распараллеливания вычислений на все доступные ядра процессора, что позволяет ускорить алгоритм пропорционально количеству физических ядер процессоров в системе.
Провести сравнительный анализ эффективности реализованных алгоритмов по памяти и по времени стало пятой задачей работы. При выполнении этой части работы было проведено тестирование 18 различных реализаций решет. Среди несегментированных алгоритмов наиболее эффективным оказалось решето Эратосфена с 3 порядком кольцевой
факторизации. Но даже решето Эратосфена с 1 порядком кольцевой
факторизации превосходит по скорости работы оптимизированное решето Аткина. Решето Сундарама же многократно уступает всем реализованным алгоритмам. Результаты тестирования также показали, что для просеивания больших простых чисел обязательным является использование сегментированного решета. Среди сегментированных решет оптимальное соотношение скорости работы и объема задействованной оперативной памяти показало решето, использующее компактный способ хранения базы простых чисел. Применение кольцевой факторизации по результатам тестирования оказалось не только очень эффективным методом уменьшения объема потребляемой памяти, а также крайне эффективным способом ускорения работы алгоритма. Прирост в скорости работы оказался даже больше, чем ожидалось из теоретических оценок!


Купить