Пентадекатлон мечты

[EUgeneUS]

Dmitriy40 в сообщении #1585840 писал(а):

Ну и сравнивать незаконченные счёты не совсем корректно.

Незаконченные счёты - только в первом пункте, про влияние ключа -p. И их планируется закончить.

Dmitriy40 в сообщении #1585840 писал(а):

Проверьте сами: возьмите интервал поменьше (типа 1e31 или 1e30) в разных местах (скажем 7e31 и 28e31) и сравните время его счёта.

Это проверено. Вот пример:

001 pcoul(12 14) -p500 -f13 -g10 -x70000000000000000000000000000000 -b1673 *RT*
305 17^2 2.11^2 3.13^2 2^2.7 5.29^2 2.3^2 19^2 2^5 3.59^2 2.5^2 7^2 2^2.3 11.53^2 2.71^2: 86 / 1121 (598.30s)
...
305 83^5 2.11^2 3.13^2 2^2.7 5.233^2 2.3^2 23^2 2^5 3.173^2 2.5^2 7^2 2^2.3 11.29^2 2 (382480.82s)
367 coul(12, 14): recurse 18204937503, walk 36193728459, walkc 11267017416 (382578.14s)

001 pcoul(12 14) -p500 -f13 -g10 -x70000000000000000000000000000000:140000000000000000000000000000000 -b1673 *RT*
305 17^2 2.11^2 3.13^2 2^2.7 5.53^2 2.3^2 19^2 2^5 3.31^2 2.5^2 7^2 2^2.3 11.61^2 2.23^2: 14126 / 17502 (598.78s)
...
305 47^5 2.11^2 3.13^2 2^2.7 5.43^5 2.3^2 23^2 2^5 3 2.5^2 7^2 2^2.3 11.131^2 2 (453189.86s)
367 coul(12, 14): recurse 39680658921, walk 39209013082, walkc 24584726073 (453730.00s)

001 pcoul(12 14) -p500 -f13 -g10 -x140000000000000000000000000000000:210000000000000000000000000000000 -b1673 *RT*
305 17^2 2.11^2 3.13^2 2^2.7 5.23^2 2.3^2 19^2 2^5 3.41^2 2.5^2 7^2 2^2.3 11.61^2 2.67^2: 9222 / 9391 (598.31s)
...
305 71^5 2.11^2 3.13^2 2^2.7 5.151^2 2.3^2 37^2 2^5 3.337^2 2.5^2 7^2 2^2.3 11.23^2 2 (512175.09s)
367 coul(12, 14): recurse 16111246180, walk 15919922916, walkc 3230541205 (512523.59s)

Мы видим, что время для диапазона такого же размера несколько растёт, от того, с насколько больших чисел начинается диапазон.
Поэтому, мы как бы (при линейной зависимости от величины диапазона) можем ожидать, что время расчета диапазона 7-21e31 (не разбитого на два) будет на меньше удвоенного времени расчета диапазона 0-7e31, а оно заметно меньше.

Dmitriy40 в сообщении #1585840 писал(а):

Насчёт зависимости от -p я вот делал специальные тесты: post1574922.html#p1574922

Спасибо! Это важная информация, наличие которой я упустил. $5+11$ - это как раз "Группа Б" и есть.

[Dmitriy40]

EUgeneUS в сообщении #1585904 писал(а):

Мы видим, что время для диапазона такого же размера несколько растёт, от того, с насколько больших чисел начинается диапазон.

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

EUgeneUS в сообщении #1585904 писал(а):

Поэтому, мы как бы (при линейной зависимости от величины диапазона) можем ожидать, что время расчета диапазона 7-21e31 (не разбитого на два) будет на меньше удвоенного времени расчета диапазона 0-7e31, а оно заметно меньше.

Ну вот Вы и увидели что там нет линейной зависимости ... В принципе при наличии автовыбора момента переключения с квадратичного на линейный режим априорные ожидания могут и не оправдываться, хоть одни, хоть другие. Ну либо мне просто лень думать какие из ожиданий более практичные.
Я бы сказал что функция времени - от двух аргументов, и длины интервала, и расположения его на числовой оси (диапазона). Вот скажем длина линейного перебора зависит линейно от размера интервала, а длина квадратичного перебора - как корень из конца интервала (разница корней из конца и начала интервала), и соответственно момент переключения режимов тоже зависит от расположения интервала в диапазоне, а от него и общее время. Лучше бы это конечно прямо проверить, но мысли такие. Так что не вижу ничего особо удивительного в странном поведении функции времени при игнорировании одного из аргументов.

PS. Сравнивать диапазоны от нуля вообще малоосмысленно, слишком часто там простые попадаются и это сильно искажает статистику, надо брать хотя бы от 1-10% верхней границы (не от 0e31 до 7e31, а хоть от 1e31 или 1e30 до 7e31, или от 1e31 до 8e31 если хочется длиной именно 7e31).

-- 18.03.2023, 19:45 --

И да, похоже линейная зависимость есть от -x, но не от длины интервала, для которой она лишь для близких и относительно малых интервалов. Т.е. должно быть линейно для 0-1e31, 0-1e32, 0-1e33, 0-1e34, и например 20-21e31, 20-22e31, 22-24e31, и постоянно для например 26-27e30, 27-28e30, 28-29e30, и т.д., но не для столь огромных (относительно своего расположения) как 0-7e31, 7-14e31, 14-21e31. Чтобы интервал 7e31 вышел на константу (или на линейность от размера интервала) надо брать диапазон где-нибудь 200e31 и дальше.

[EUgeneUS]

Dmitriy40
У меня вопросы сугубо практичные.

Есть цель посчитать все паттерны "группы Б" ($5+11$) до 21e31.

1. Сколько будут потери времени, если этот диапазон делить на три куска по 7e31 или на два по 10.5e35, а не считать целиком?
2. Сколько будет выигрыш по времени, если ключ -p500 уменьшить до -p200, или до -p150?

При этом прямые эксперименты осложнены тем, что расчет диапазона 0-7e31 с -p500 занимает 2 миллиона секунд (на один паттерн)

[Dmitriy40]

Надеюсь ответы на них Вы уже получили (сами, в процессе тестов). Потому что так вот априори на первый я не отвечу, тестировать надо (не обязательно на столь огромных кусках, но тогда в сравнимых условиях, брать и диапазоны меньше, а насколько меньше это тоже вопрос непростой), а на второй частичный ответ есть в том моём сообщении, но его тоже придётся проверить прямо (что зависимость вышла на "плато" (стабильность, не обязательно линейно) и прошла начальные пертурбации). В общем не занимался я столь долгими исследованиями, может Hugo что скажет.

[EUgeneUS]

Dmitriy40

По первому вопросу ответа точного у меня нет. Но есть ощущение, что считать "цельным куском" будет не медленнее, а скорее - будет быстрее.

По второму вопросу будет более-менее понятно, когда закончится считаться паттерн с ключами -p200 и -p150. (Правда он считается на другом компе, чем паттрены с ключом -p500).

[Huz]

@EugeneUS Sorry for the delay, it has been so quiet here that I have been checking less frequently for new messages.

In respect of "-p", it is expected that it affects things sub-quadratically precisely because the switching from quadratic to linear search optimizes things to be sub-quadratic.

In respect of using -x<start>:<finish> to slice the search space, please note this section from the compile-time options in the README:

Цитата:

-DLARGE_MIN: add extra checks to cope better with runs where the minimum value to check is relatively large (as specified with -x<min>:<max>). For the majority case where min is 0 or small, we assume these checks are an unnecessary expense; hence we do not enable them by default.

The main difference is that in a build without LARGE_MIN, the code does not subtract the "start" value to determine the true size of the range, so if "start" is a large-enough proportion of "finish" it will be suboptimally reluctant to switch to linear.

If you wish I can ask DemIS to additionally make a LARGE_MIN build for this and future releases.

@Dmitriy40 Did you have a chance to look at the new options to control assignment of different powers? Do they give you the level of control you had wanted?

[Dmitriy40]

Мрак, неужели пара проверок, пусть даже во всех циклах, столь медленны?! Вот уж не подумал бы, там же по любому в проверке на простоту (или количество делителей) этих проверок уж точно не одна и даже не десяток. Мне как-то вообще странны некоторые из принятых решений, я бы сделал по другому (более оптимально на свой взгляд - правда далеко не факт что получилось бы).

Huz в сообщении #1585929 писал(а):

@Dmitriy40 Did you have a chance to look at the new options to control assignment of different powers? Do they give you the level of control you had wanted?

Judging by their description, yes, they do. But I didn't really check them because I was busy with other things and now I don't really remember why I wanted them so much... Or rather, so far I've abandoned the idea of brute force (there was an idea to move some of the brute force cycles from pcoul to an external program). Maybe as soon as I hit another threshold (which is very close), so again I will try to figure it out and use it.

[Huz]

Dmitriy40 в сообщении #1585940 писал(а):

Мрак, неужели пара проверок, пусть даже во всех циклах, столь медленны?!

I do not imagine it is a huge speed up, but every little helps - at the time I added the option nobody (including me) was asking for runs with a non-zero starting point. Also, I am used to an environment in which people that want to use my code are able to compile it, so making something a compile-time option is enough to make the option itself available.

I am still hopeful that one day either you or Eugene will acquire the setup to compile the code; to the best of my understanding it is not particularly difficult (see the README for details).