Нашел время понять, что такое - асимптоматика.

Но здесь трудно оценить процесс вычисления, поскольку используются процедуры Питона.

Если рассматривать результаты вычислений по времени, то они очень отличаются:
утром ПК считает быстро, а вечером медленнее.

Если в среднем, то для мини диапазона на 500 000 нечётных чисел на проверку уходит 4 - 5 минут уже довольно давно.

А в этом диапазоне числа, разные с точки зрения параметра s.
У 50% s = 1, у 25% s = 2 и т.д.

У меня было 15 диапазонов по 50 000 000.
Я взял в каждом диапазоне 1-й мини диапазон по 1 000 000 и посмотрел на время его выполнения.

Получилось (мин.сек.):
0.21, 1.36, 2.24, 2.34, 2.56, 3.11, 3.58, 3.53, 3.46, 5.41, 4.10, 4.27, 4.46, 4.42, 5.34

В предыдущем сообщении асимптоматика эвристического алгоритма считается с учётом проверки чисел на делители.
Это ошибочно.

Поэтому для асимптоматики были проведены расчёты эвристического алгоритма без учёта проверки на делители.

В результате:
на диапазоне от 5 до 50 000 000 время проверки мини диапазона из 1 000 000 чисел составляет 9 сек.

на диапазоне от 350 000 000 до 400 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 12 сек.

на диапазоне от 700 000 000 до 750 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.

на диапазоне от 1 500 000 000 до 1 550 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.

на диапазоне от 2^200 +1 до 2^200 +1 + 50 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 2 мин. 06 сек. (найдено на мини диапазоне 7134 простых числа)

на диапазоне от 2^500 +1 до 2^500 +1 + 400 000 время проверки мини диапазона
уже из 200 000 чисел составляет 3 мин. 21 сек. (найдено на мини диапазоне 576 простых числа)

на диапазоне от 2^1024 +1 до 2^1024 +1 + 400 000 время проверки мини диапазона
уже из 200 000 чисел составляет 21 мин. 59 сек. (найдено на мини диапазоне 281 простое число)

exp98Вам надо скорее патентовать его в просчитанном диапазоне.
А то ведь на хабру глянет пара вдумчивых глаз, придёт сюда, и скажет: "Ага!" И бабла у неё будет больше, и возможностей, и выч-х мощностей.
Патентовать - подольше будет, чем считать до ярда, а вот статейку тиснуть можно быстрее.
Так что, не упускай из виду. http://sci-article.ru/articles_current.php

Кажется, получилось "тиснуть" статью в журнал.

maytonGennadiy Usov, рано еще писать статьи. Надо баги поискать.В статье описан эвристический алгоритм.
Программа не рассматривается, есть только ссылка на неё.

В статье указаны некоторые исходные данные для программы, но они указаны для чисел до 700 000 000.
Если в программе для больших чисел что-то изменится,
то поменяются исходные данные, но уже в новой возможной публикации.

exp98Ах ,забыл. Повторю старый вопрос. На месте редакции также попросил бы сравнение со стариной Мюллером по кол-ву раундов, коль скоро взялись Мюллера оптимизировать.Спасибо за вопрос!

Отвечаю:

По тесту Мюллера-Рабина количество раундов оптимально около log (n).
При этом, если два условия теста не выполняются, то число - составное.
В этом случае количество раундов будет намного меньше.

По эвристическому алгоритму:
- для s = 1 (50% всех нечётных чисел) количество раундов А (пока 10 - 15, дальше покажут проверки).
- для s > 1 количество раундов может быть А * s. Исследования до 1 000 000 000 показали, что количество раундов не превышает А * 8.
При этом, если при некоторой комбинации a (основание степени) и s2 (0=< s2 < s) определяется остаток по модулю, отличный от 1 и от (n - 1), то число n - составное.
В этом случае количество раундов будет намного меньше.

maytonавторВ результате:
на диапазоне от 5 до 50 000 000 время проверки мини диапазона из 1 000 000 чисел составляет 9 сек.
на диапазоне от 350 000 000 до 400 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 12 сек.
на диапазоне от 750 000 000 до 800 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.
на диапазоне от 1 500 000 000 до 1 550 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.По этим диапазонам мы сверим с моим алгоритмом. Количество штук.В первом случае - 3001132,
во втором - 2532800,
в третьем - 2442998 (я изменил диапазон),
в четвертом - 2364554

Следующие уточнения:

1. Лучше для Range ввести 2 колонки, может быть придётся вычитать.
2. 2-я и 3-я колонки - эти цифры посчитаны алгоритмом, почему они в разных колонках?
3. Что будем заносить в колонку Elapsed time?
Время всего диапазона или мини диапазона.
У меня иногда "глючит" время - приходится выключать ПК (наверное, охлаждаться).
4. О какой формуле с логарифмом идёт речь?
5. В коде - число за точкой это ....?

maytonНарисовал теоретическую табличку. Primes theoretical взял по формуле.
Range Primes Found Primes (theoretical) Elapsed time 3 - 50 000 000 2 820 471 8,38 350_000_000 - 400_000_000 2 404 426 9,59 750_000_000 - 800_000_000 2 330 675 10,06 1_500_000_000 - 1_550_000_000 2 252 774 надо пересчитать2^200 +1 - 2^200 + 1 + 1 000 000 7134 2,06 2^500 +1 - 2^500 + 1 + 200 000 576 3,21 2^1024 +1 - 2^1024 +1 + 200 000 281 21,59

maytonНарисовал теоретическую табличку. Primes theoretical взял по формуле.
Range Primes Found Primes (theoretical) Elapsed time 3 - 50 000 000 3 001 132 2 820 471 8,38 350_000_000 - 400_000_000 2 532 800 2 404 426 9,59 750_000_000 - 800_000_000 2 442 998 2 330 675 10,06 1_500_000_000 - 1_550_000_000 2 364 554 2 252 774 надо пересчитать2^200 +1 - 2^200 + 1 + 1 000 000 7134 2,06 2^500 +1 - 2^500 + 1 + 200 000 576 3,21 2^1024 +1 - 2^1024 +1 + 200 000 281 21,59

maytonПо натуральному логарифму.
Я осилил посчитать.

Деление посчитаю в больших десятичных. А вот как учесть плюс 1 миллион?Через о(малое)...

Gennadiy UsovmaytonПо натуральному логарифму.
Я осилил посчитать.

Деление посчитаю в больших десятичных. А вот как учесть плюс 1 миллион?Через о(малое)...Разница между и очень мала.

Разница где-то на 50-м знаке. Это надо обязательно учесть?