2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Аткин vs Эратосфен
Сообщение17.04.2010, 15:56 
Заслуженный участник


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

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

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

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

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

 Профиль  
                  
 
 Re: Аткин vs Эратосфен
Сообщение17.04.2010, 17:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Аткин vs Эратосфен
Сообщение17.04.2010, 21:33 
Заслуженный участник


04/05/09
4511
venco в сообщении #310586 писал(а):
Теоретически Аткин быстрее $O(n/\log \log n)$ vs $O(n\log\log n)$ у Эратосфена.
Посмотрел свою реализацию, и оказалось, что мой Аткин имеет сложность $O(n)$. И я совершенно не вижу, где тут можно сэкономить...

 Профиль  
                  
 
 Re: Аткин vs Эратосфен
Сообщение19.04.2010, 20:59 
Заслуженный участник


04/05/09
4511
Прочитал статью Аткина. Оказалось, что ассимптотика $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}$.
Вывод: как часто бывает, ассимптотически более быстрый и сложный алгоритм на практике проигрывает более простому.

 Профиль  
                  
 
 Re: Аткин vs Эратосфен
Сообщение22.04.2012, 17:18 


22/04/12
1
venco в сообщении #310586 писал(а):
Но на практике приходится использовать блочный вариант в обоих случаях, чтобы блок влезал в кеш, иначе сразу медленнее на порядок. Так вот блочные варианты обоих методов имеют оверхед, причём у решета Аткина он растёт заметно быстрее.

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


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

 Профиль  
                  
 
 Re: Аткин vs Эратосфен
Сообщение23.04.2012, 16:00 


01/07/08
813
Киев
venco в сообщении #311198 писал(а):
Вывод: как часто бывает, ассимптотически более быстрый и сложный алгоритм на практике проигрывает более простому.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group