Итоги не очень. Слил все идеи воедино, скорость особо не выросла, получилось только память поэкономить.
Переименовал немного, теперь:
next_prime() это последняя x64 версия
next_prime32() это старый next_prime()
next_prime64() тот же какой был, прототип текущего next_prime()

Что получилось оптимизировать:
1. Память: под решето 64кб и от 16 кб под кэш для инициализации. 16 кб хватает до ~10^10, максимум 196 Мб для 10^19
2. Пропуск кратных 2,3 немного ускорил, дальше наращивать - бесполезно, тормоза только возрастают.
3. Возможна многопоточность, только надо изначально инициализировать кэш next_prime(MAX) (позже попробую обогнать Аткина на 4 ядрах)
Результаты на линукс x64 (g++ nextprime.cpp -O2)Test(0M...1000M): next_prime32()
count 50847534 primes. time 1974 msec speed 25758K/sec OK

Test(0M...1000M): next_prime64()
count 50847534 primes. time 2045 msec speed 24864K/sec OK

Test(0M...1000M): next_prime()
count 50847534 primes. time 1741 msec speed 29205K/sec OK

Test(4000M...6000M): next_prime()
count 89583557 primes. time 3540 msec speed 25306K/sec OK

Test(4000M...6000M): next_prime64()
count 89583557 primes. time 4314 msec speed 20765K/sec OK


Максимума разрядности x64 достигнуть не удалось. Чуть раньше останавливается из-за превышения разрядности во время заполнения решета.
Максимум получил 18 446 744 030 759 878 627 до 2^64 не дошел на 42 949 750 784.

Исходники next_prime.h зафиксировал. Там же nextprime.cpp тесты

PS Потестил корректность сколько смог, рандомно результаты между собой посравнивал. Работает. Но primesieve говорит что в диапазоне 4...6 млрд. на одно число меньше. Поразбираюсь позже.

Dima Tprimesieve говорит что в диапазоне 4...6 млрд. на одно число меньше. Поразбираюсь позже.
Нашел причину. Ошибка в тестах была. Поправил. Проверил до 10^10 количество совпадает.

maytonА тут кастинг обязательно указывать?



Не знаю как правильно написать. MSVC нормально понимает без (uint64_t).
g++ варнинги писал, добавил (uint64_t) - ничего не поменялось, затестил - понимает правильно, оставил так.

Сделал пример многопоточного использования multi_prime.cpp

В 4 потока на 4 ядрах посчитал до 10^9 за <0,5 сек :)



PS Сделал потоки на WinAPI, под линуксом не соберется.

Навел порядок, причесал исходники.
Сделал два файла с x32 и x64 версиями next_prime() внутри:
next_prime32.h
next_prime64.h

От x64 в реальности польза сомнительная, все равно тормозит на больших числах, и на малых при x32 компиляторе, поэтому сделал отдельно x32 вариант, для практических задач ее хватит (по крайней мере мне).
Настроил x32 на минимальный расход памяти 22.5 кб на расчет любого до 2^32.

Исходники тут

PS mayton, исправь, пожалуйста, ссылку в первом посте на действительно последний вариант.
PPS egorych, ты был прав 17466144 :)

maytonПолучается что я не могу различать присвоение "0" и неуспех.
Затести


результат-1 0 0
Там есть mpz_init_set_str() - это совмещенные mpz_init() и mpz_set_str()


maytonНу... я не совсем понял что на что я должен исправить.

а так написать
next_prime32.h
next_prime64.h
Тесты и примеры использования

maytonВобщем я решил взять некую паузу и вернуться к истокам. С Эвклиду. Этот старый бородач
создал алгоритм которому нет аналогов в мире в соотношении простоты и полезного эффекта.
Я имею в виду НОД (в англоязычном варианте GCD - Greatest Common Divisor).
На отличную мысль натолкнул, давно ломал голову над заменой GUID`у в ограниченной распределенной системе.

Задача: имеем N несвязанных БД, документы из которых в итоге сливаются в одну. Например клиенты банка в оффлайне готовят платежки, затем пересылают в банк, каждой платежке надо присвоить уникальный id. Пример надуманный, для общего понимания задачи.
При ожидаемом общем количестве записей менее 1 млрд. обычного int с запасом хватает, но т.к. распределенная система невозможно гарантировать уникальность, поэтому счетчики не подходят.
GUID задачу решает, но тормоза из-за размера, 16 байт на id: база быстро пухнет от хранения и выборки в разы замедяляются.

Решение: выдаем каждой БД уникальное простое число (шаг счетчика) не меньше заданного (это константа, минимум), далее счетчиком генерим последовательность с этим шагом. Остатается только пропустить те значения где при разложении на множители есть простые больше минимума.
Т.е. задаем какой-то минимум для всей системы, например 1000, и дальше выдаем простые последовательно каждой базе (1009,1013,1019... тысячной базе 9433) по сути это ID базы. Например база с ID 1013 генерит последовательность 1013, 2026, 3039 ... пропуская пересечения с другими последовательностями (например 1022117 = 1009*1013). Остается сделать проверку что нет простого делителя больше заданного минимума.
В итоге получаем боле-мене равномерное использование всего диапазона 2^32 Побочный эффект по конкретному значению можно вычислить ID базы которая его сгенерила.

Только придумал, не тестил, но вроде должно взлететь. Надо еще над выбором минимума подумать.

PS была мысль раздавать диапазоны id (например 1000-1999, 2000-2999, 3000-3999 ...) и по мере использования выдавать следующий, оно более линейно, но тоже не идеально, диапазон кончился, связи с раздающим нет, все встало.

Владимир2012, чтобы флудить не в тему есть отдельный форум .

Потестил. Не взлетело. Слишком много пропускать надо, 50-70% пропусков. Дорогая плата за расширяемость. Если дополнительно максимальное простое ограничить, то пропусков значительно меньше, но с фиксированным максимумом проще классическое решение: задаем уникальное исходное значение <max и увеличиваем счетчик шагом max.

?Что ж так сложно то...
В первой базе генерим id вида k*N+0, во второй - k*N+1, в третьей k*N+2, ..., в N-ной базе - k*N+(N-1).
Уже написал что к этому все приходит 17505147
Тут жесткое ограничение по N, т.е. с появлением N+1 базы будет большая проблема.
Хотел избавиться от ограничения по N, получается непрактично.

maytonДанную задачу можно решить 1000 способами. Но самое главное - дать точный ответ на вопрос
какие требования ты выставляешь к последовательности.
Логи надо писать в моей распределенной системе сообщений: кто-кому-когда-чего. В идеале должно фоном копиться и на сервер скидываться по мере возможности, лог надо вести за 1-2 последних месяца, в этом промежутке времени желательно чтобы сообщение имело уникальный ID, чтобы просто сводить логи отправителя и получателя. Сейчас каждый сам генерит ID сообщений, для передачи хватает т.к. срок жизни в кэше получателя = время доставки + минута, если совпало в этом промежутке - есть механизм смены ID, можно конечно извратиться и их использовать, но копаться в таких логах неудобно будет.

Сообщений между всеми меньше миллиона в месяц. Т.е. в идеале ID должно быть 7-8 разрядное число.

Пока раздача диапазонов приоритетный вариант. Думал может простым числам тут применение найдется. В принципе идея неплохая: выдал один раз каждому узлу по уникальному числу и пусть генерит ID по кругу, лишь бы повторы не чаще раз в 2 месяца, но есть узлы где где всего 10-20 сообщений в сутки, есть 5-10 тысяч.

Владимир2012GUID привел в пример потому, что на форумах не встречал ни каких других подходов к получению
уникального кода.
Выше 17505369 классический подход генерации ID для распределенных БД.
По большому счету все подходы (в т.ч. GUID) сводятся к тому чтобы выдать каждому генератору какую-то уникальную константу, к которой генератор добавляет свое уникальное число по заданному алгоритму. Т.е. константа определяет диапазон в котором работает генератор. А дальше конкретные реализации, связанные с оптимизацией ради уменьшения размера ID. Все оптимизации сводятся к ограничению количества констант и диапазона в котором может работать конкретный генератор.

Разрядности 128 бит GUID`а достаточно чтобы не заморачиваться что в один прекрасный день кончатся ID или невозможно будет выдать очередную константу новой базе, но во-первых базы раздуваются в разы по сравнению с int, как следствие в разы замедляются выборки. И во-вторых банальное желание покопаться руками в базе (в поисках какого-нибудь косяка) превращается в кошмар: запомнить/записать 7-8 цифр обычного ID элементарно, а 36 знаков GUID`a - уже проблема.

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

По поводу анонимности: она нужна далеко не всегда, но нынешнее маниакальное желание всяких вэб-сервисов собрать максимум инфы о пользователях немного напрягает и заставляет задумываться.