Участник:Vvnikolaev/Решето Эратосфена

Автор статьи: Николаев Владимир

Свойства и структура алгоритмов

Общее описание алгоритма

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа [math]\displaystyle{ n }[/math]. Приписывается древнегреческому математику Эратосфену Киренскому (откуда и название). Алгоритм проходит список всех чисел от [math]\displaystyle{ 2 }[/math] до [math]\displaystyle{ n }[/math] и на каждом шаге убирает часть из них, не являющихся простыми. Таким образом происходит фильтрация («решето» в названии).

Математическое описание алгоритма

Пусть требуется найти все простые числа от [math]\displaystyle{ 2 }[/math] до [math]\displaystyle{ n }[/math]. Алгоритм состоит из следующих шагов:

1. Выписываются подряд все натуральные числа от [math]\displaystyle{ 2 }[/math] до [math]\displaystyle{ n }[/math]
2. Берется [math]\displaystyle{ p = 2 }[/math]
3. Зачеркиваются числа от [math]\displaystyle{ p^2 }[/math] до [math]\displaystyle{ n }[/math] с шагом [math]\displaystyle{ p }[/math] (то есть все числа от [math]\displaystyle{ 2 }[/math] до [math]\displaystyle{ n }[/math], кратные [math]\displaystyle{ p }[/math], кроме него самого)
4. Ищется первое не зачеркнутое число в списке, превышающие [math]\displaystyle{ p }[/math], и это значение присваивается переменной [math]\displaystyle{ p }[/math]
5. Повторяются шаги 3 и 4 пока возможно

Соответственно алгоритм заканчивает свою работу при [math]\displaystyle{ p^2 \gt n }[/math].

Вычислительное ядро алгоритма

Основное время работы приходится на шаг №3 алгоритма. Можно показать, что сложность алгоритма составляет [math]\displaystyle{ O(nlog(log(n))) }[/math].

Макроструктура алгоритма

Алгоритм можно разбить на 2 части:

1. Первая часть — создается и заполняется единицами булев массив длины [math]\displaystyle{ n }[/math]
2. Вторая часть — последовательно рассматривается каждое, еще не помеченное число, и с помощью него производится фильтрация бо́льших чисел

Схема реализации последовательного алгоритма

Псевдокод вычислительного ядра алгоритма:

Вход: натуральное число n

Пусть A — булев массив, индексируемый числами от 2 до n, изначально заполненный значениями true.

 для i := 2, 3, 4, ..., пока i2 ≤ n:
  если A[i] = true:
    для j := i2, i2 + i, i2 + 2i, ..., пока j ≤ n:
      A[j] := false

Выход: числа i, для которых A[i] = true.

Последовательная сложность алгоритма

Сложность алгоритма складывается из двух составляющих. Первое — выписывание всех чисел от [math]\displaystyle{ 2 }[/math] до [math]\displaystyle{ n }[/math]. Это, очевидно, делается за [math]\displaystyle{ O(n) }[/math]. Вторая составляющая — повторение шагов 3 и 4 — вычислительное ядро алгоритма. Сложность этой части составляет [math]\displaystyle{ O(nlog(log(n))) }[/math]. Строгое доказательство этого факта можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers».

Информационный граф

Информационный граф рассматриваемого алгоритма:

Ресурс параллелизма алгоритма

Вычислительное ядро алгоритма можно распараллелить, но не полностью. Разобьем все натуральные числа [math]\displaystyle{ \{2, \dots, n\} }[/math] на 2 множества — [math]\displaystyle{ \{2, \dots, \sqrt n\} }[/math] и [math]\displaystyle{ \{\sqrt n + 1\dots, n\} }[/math]. Поиск простых чисел на первом множестве распараллелить нельзя, а на втором — можно (различия заключаются в том, что числа из второго множества не будут проверяться в качестве делителей — они все больше [math]\displaystyle{ \sqrt n }[/math]). Поэтому проверка на простоту для первого множества будет выполняться на каждом потоке, а второе можно разбить на [math]\displaystyle{ p }[/math] частей ([math]\displaystyle{ p }[/math] — количество процессов) и проверять каждую часть на простоту отдельно. Так как первая часть при больших [math]\displaystyle{ n }[/math] значительно меньше второй, то можно предположить, что параллельное выполнение даст хороший прирост к скорости.

Входные и выходные данные алгоритма

Входные данные алгоритма — одно число [math]\displaystyle{ n }[/math], до которого нужно найти все простые числа. На выходе алгоритм выдает либо булев массив длины [math]\displaystyle{ n }[/math], отражающий для каждого натурального числа, является ли оно простым, либо список простых чисел от [math]\displaystyle{ 2 }[/math] до [math]\displaystyle{ n }[/math] (что конкретно — зависит от реализации и не имеет особого значения).

Программная реализация алгоритма

Масштабируемость алгоритма и его реализации

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета.

График сильной масштабируемости:

Число, до которого нужно искать простые числа, [math]\displaystyle{ n = 10^7 }[/math]. По графику видно, что распараллеливание дает выигрыш в скорости выполнения, но с увеличением числа используемых ядер, этот выигрыш все меньше. Это связано с лишними накладными расходами.

График слабой масштабируемости:

При одном процессе, число [math]\displaystyle{ n \approx 5000000 }[/math]. Видно, что при фиксированном отношении сложности задачи к числу процессов, время решения задачи растет. Это связано с тем, что при распараллеливании появляются дополнительные накладные расходы, а так же с тем, что задача распараллеливается не полностью. При увеличении сложности задачи в [math]\displaystyle{ 64 }[/math] раза (и одновременно числа процессов, потому что производилось исследование слабой масштабируемости), время выполнения увеличилось в [math]\displaystyle{ 5 }[/math] раз.

Существующие реализации алгоритма

Однопоточные реализации с различными улучшениями:

1. Однопоточная реализация: http://e-maxx.ru/algo/eratosthenes_sieve
2. Однопоточная реализация, работающая за сублинейное время: http://e-maxx.ru/algo/prime_sieve_linear

Многопоточные реализации:

1. https://github.com/keyfunda/primes-parallel-sieve
2. https://github.com/Heliosmaster/BSPEratosthenes
3. https://github.com/marius92mc/sieve-of-eratosthenes-with-MPI