Вывихнул мозг асинхронностью очередной раз. Пытаюсь шаги цикла к next_prime() приделать. Пока результаты от 1 до 10^9 такие


next_prime() - достраивает решето с 1, пропускает четные, эталонный показатель.
next_prime2() - не тратит лишнюю память, только заполняет кусок решета (64 кб), это вышеупомянутый next_prime64() без оптимизации, только в x32 варианте. Тормозит из-за высчитывания смещений перед началом заполнения решета.
next_prime3() - тоже самое что и 2, только с пропуском кратных 2 и 3. Причем в обоих циклах (вычеркивания и чтения). Чуть быстрее первого. Надеялся на большее.

Цикл вычеркивания дальше не оптимизировать, т.к. там будет куча умножений и из-за них тормозит больше чем без них. Вычеркивание без 2,3 сделал сдвигами. Остается оптимизировать только цикл считывания результатов.
С ним все плохо, таблица шагов не ложится сюда один-в-один из моего синхронного Эратосфена. Запутался в смещениях. Доделаю, но не думаю что по времени ниже 1,5 сек. опущусь. Надо еще какие-то идеи по оптимизации алгоритма.

PS После из самого быстрого next_primeX() сделаю next_prime64() и найдем MAX(next_prime64()), а пока надо 0.5 сек Аткина как-то обогнать.

Владимир2012 Dima T не обижайся.
То чего ты хочешь достичь - "Лично мне охота Аткина обогнать, посчитать за <0,5 сек диапазон до 10^9."
Как по мне, то лучше "ляг поспи и все пройдет" /хотя тебе виднее .../
Не обижаюсь, обгоню :) У того же автора Эратосфен в три раза быстрее моего (0,6 сек). Он, как ты пишешь, 15 лет занимался проблемой, а я всего вторую неделю. Все еще впереди.

PS Туда специально не заглядываю, не люблю списывать.

Почитал вышеупомянутый сайт http://primesieve.org/ там форсированный Эратосфен в основе. Причем форсировали его капитально.
Затестил до 10^9: 0,06 сек. (4 ядра), 0,12 сек. (1 ядро)
Можно смело заявлять: Эратосфен победил Аткина.

Optimizations used in primesieve Uses a bit array with 8 flags each 30 numbers for sieving
Pre-sieves multiples of small primes <= 19
Compresses the sieving primes in order to improve cache efficiency [5]
Starts crossing off multiples at the square
Uses a modolo 210 wheel that skips multiples of 2, 3, 5 and 7
Uses specialized algorithms for small, medium and big sieving primes
Uses a custom memory pool (for big sieving primes)
Processes two sieving primes per loop iteration to increase instruction-level parallelism
Parallelized (multi-threaded) using OpenMP

По существу направления оптимизации такие:
- обсчет окнами
- биткарта без кратных 2,3,5 (30 чисел на байт)
- оптимизация шагов цикла с пропуском кратных до 19
- оптимизация умножений и корней
- распараллеливание расчета

У меня все те же направления (два последних обдумываю), осталось суметь нормально реализовать их в коде.

А моя поделка выше не взлетает :(
Добавил пропуски кратных 2,3,5,7,11,13 - стало чуть медленнее работать. Итераций меньше, но доп.вычисления съедают всю экономию. Вариант с пропуском 2,3 пока самый быстрый. Буду его дотачивать. После распараллеливания на 4 ядра разгоню до <0,5 сек.

maytonДима. Меня интересует продолжение расчёта за границей Эратосфена.
У тебя есть рабочий макет?
Понятней напиши что хочешь получить.
Для x64 мой next_prime64() считает почти до 2^64. Споткнется из-за разрядности в самом конце интервала, точнее после квадрата максимального простого 2^32, т.к. там там надо будет next_prime(2^32) посчитать, а это x32 пока. Как это вылечу посчитаю next_prime64(2^64 - 10000).

Он немного неоптимизирован по скорости и расходу памяти, но как оказалось скорость особо некуда разгонять, а памяти ему надо максимум 256 мб.

По сути сейчас его и ускоряю, только в виде x32 версии. А x32 только потому что компилятор у меня такой, x64 просто тормозит из-за эмуляции работы с x64

Теоретически дальше можно в x128 переделать. Надо только чтобы арифметика x128 считалась (+-*/%).

SerValExec time : 24.6 seconds.
Всего лишь в 100 раз медленнее одного ядра моего проца :)

SerValА поскольку "качество" программирования у меня одинаковое и для CPU и для ГПУ, то видно, что на ГПУ всё выполняется в 20 раз быстрее чем на ЦПУ. :)
Мне-то это что дает? Я качество алгоритма улучшаю. Количество (время выполнения) это просто мера сравнения на одном и том же железе.

И не факт что мой код взлетит на твоем ГПУ, там нужно сильное распараллеливание алгоритма, а у меня однопоточный. Можешь затестить действительно ли всё в 20 раз быстрее на ГПУ :)

SerValЭто какбэ даёт понимание, что сколько не улучшай качество алгоритма на одном процессоре, 2048 процессоров Вам не обогнать.
Разумеется, если эти процессоры не у такого "программиста" как я :)
Наивный. Если бы все алгоритмы легко паралеллились, то в ЦПУ давно было бы по несколько тысяч ядер, интел давно предлагал 800 ядерный проц выпустить, прототипы показывал, только он нафиг не нужен, т.к. 4 ядра занять нечем.
Почитай про Закон Амдала , поймешь что сначала надо мозг сломать об распараллеливание алгоритма, а потом уже его в ГПУ отправлять