Аткин vs Эратосфен

[venco]

Кому-нибудь удалось реализовать решето Аткина, чтобы работало быстрее решета Эратосфена?

Теоретически Аткин быстрее $O(n/\log \log n)$ vs $O(n\log\log n)$ у Эратосфена. Но на практике приходится использовать блочный вариант в обоих случаях, чтобы блок влезал в кеш, иначе сразу медленнее на порядок. Так вот блочные варианты обоих методов имеют оверхед, причём у решета Аткина он растёт заметно быстрее.

К примеру, мне удалось сделать решето Эратосфена по модулю 30 (в одном байте), и решето Аткина по модулю 24 (на байт), т.к. в нём используется модуль 12.
В результате решето Аткина у меня работает где-то на 25% медленнее до $10^{10}$, и при дальнейшем росте чисел начинает быстро отставать, например до $10^{11}$ - уже медленнее в 2 раза.

Сначала я решил, что не заметил какой-то оптимизации в решете Аткина, и скачал primegen-0.97, программу, которую на нескольких сайтах назвали самой быстрой программой поиска простых чисел, использующую как раз решето Аткина. Оказалось, что их реализация даже медленнее чем моя, и замедляется с ростом $n$ ещё быстрее.

И вот я в непонятках, есть ли возможность сделать решето Аткина быстрее решета Эратосфена?

[worm2]

С учётом того, что $\log \log n$ ограничена константой --- вряд ли :)

[venco]

venco в сообщении #310586 писал(а):

Теоретически Аткин быстрее $O(n/\log \log n)$ vs $O(n\log\log n)$ у Эратосфена.

Посмотрел свою реализацию, и оказалось, что мой Аткин имеет сложность $O(n)$. И я совершенно не вижу, где тут можно сэкономить...

[venco]

Прочитал статью Аткина. Оказалось, что ассимптотика $O(n/\log\log n)$ подразумевает соответствующее увеличение модуля (12 в обычной реализации). Т.е. если модуль фиксирован, то сложность решета Аткина $O(n)$.
Если теперь учесть потери от блочной реализации, то у Аткина это $O\left({n^{1.5}\over B}\right)$, где $B$ - размер блока, а у Эратосфена - $O\left({n^{1.5}\over B\log n}\right)$. Т.е. у Аткина эти потери начинают превалировать при $n\approx B^2\approx 10^{14}$ в нашем случае, а у Эратосфена - при $n\approx (B\log n\log\log n)^2\approx 10^{18}$.
Вывод: как часто бывает, ассимптотически более быстрый и сложный алгоритм на практике проигрывает более простому.

[ni10]

venco в сообщении #310586 писал(а):

Но на практике приходится использовать блочный вариант в обоих случаях, чтобы блок влезал в кеш, иначе сразу медленнее на порядок. Так вот блочные варианты обоих методов имеют оверхед, причём у решета Аткина он растёт заметно быстрее.

К примеру, мне удалось сделать решето Эратосфена по модулю 30 (в одном байте), и решето Аткина по модулю 24 (на байт), т.к. в нём используется модуль 12.
В результате решето Аткина у меня работает где-то на 25% медленнее до $10^{10}$, и при дальнейшем росте чисел начинает быстро отставать, например до $10^{11}$ - уже медленнее в 2 раза.

Я вот тоже занимался реализацией решета аткина. Но нигде не находил про блочный вариант, не могли бы вы сказать что это такое? как я понял это разбиение на части отрезка до заданного числа. Но как это все сделать чтобы считало правильно и влезало в кэш? не могли бы вы подкинуть идею или алгоритм?

[hurtsy]

venco в сообщении #311198 писал(а):

Вывод: как часто бывает, ассимптотически более быстрый и сложный алгоритм на практике проигрывает более простому.

Эратосфену можно не задумываться о реализации, у него компьютера не было. Но ведь до нужных на практике величин простых ни с каким решетом не доберешься. С уважением,