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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вход: натуральное число 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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