Как писать быстрые программы

[wrest]

Yadryara в сообщении #1720924 писал(а):

То есть разница между результатами у вас и у меня огромная. И лишь отчасти она может объясняться доп. проверкой степени. Остальное — пока объясняю разными паттернами.

Видимо и паттерном в том числе. В задачах D(96,L) цепочки наверное отбрасываются позже потому, что множителей надо набрать больше чем для D(48,L). Но тут я не знаю, паттерноведение не ведаю
Однако разница в 30 раз наводит на мысли, что дело не только в паттерне.

Отсюда логика построения паттерна должна быть такая, что надо увеличивать количество вмонтированных простых множителей при сохранении вероятности найти цепочку. Тогда фильтровать будет легче: цепочки будут отбрасываться раньше. То есть надо, чтобы числа были склонны скорее к перебору множителей чем к недобору.

[Yadryara]

Dmitriy40
Нету плато такого длинного, я же поэтому и остановился, хотя может стоило ещё строчку показать.

Меня пока интересовало распределение в начале и вблизи максимума. Чтобы сгладить статистику надо просто на подольше запустить, чтоб максимум был не 8 тысяч, а например 100 тысяч.

Ну вот, ниже тысячи падает и уже не возвращается:

[0, 1636, 3016, 3892, 4887, 5719, 6496, 7182, 7537, 7426, 7656, 7973, 8100, 7916, 8375, 8239, 8088, 8334, 8307, 8080, 8219, 8032, 7919, 8083, 8160, 7727, 7363, 7444, 7290, 7346, 7268, 7229, 7231, 7028, 6883, 6668, 6693, 6627, 6457, 6340, 6217, 5945, 6147, 6113, 5930, 5653, 5636, 5655, 5456, 5407, 5205, 5262, 5253, 5135, 4997, 5047, 4846, 4914, 4860, 4671, 4661, 4490, 4357, 4483, 4434, 4307, 4170, 4252, 4143, 4099, 4027, 3940, 3884, 3981, 3795, 3717, 3713, 3767, 3681, 3601, 3422, 3431, 3442, 3417, 3313, 3324, 3273, 3231, 3215, 3112, 3120, 3013, 3042, 3005, 3022, 2919, 2967, 2847, 2866, 2890, 2862, 2855, 2824, 2708, 2692, 2609, 2553, 2590, 2638, 2453, 2442, 2496, 2409, 2446, 2481, 2338, 2235, 2313, 2308, 2283, 2218, 2196, 2232, 2269, 2136, 2193, 2148, 2111, 2018, 2012, 2105, 2034, 2052, 1976, 1982, 1915, 1900, 1942, 1866, 1848, 1804, 1836, 1806, 1730, 1781, 1734, 1726, 1681, 1751, 1731, 1661, 1677, 1703, 1662, 1717, 1701, 1624, 1616, 1638, 1522, 1554, 1554, 1551, 1559, 1517, 1498, 1594, 1443, 1504, 1395, 1481, 1453, 1451, 1397, 1449, 1383, 1414, 1399, 1336, 1373, 1336, 1377, 1299, 1324, 1293, 1297, 1262, 1311, 1329, 1304, 1270, 1251, 1233, 1246, 1250, 1233, 1217, 1186, 1202, 1231, 1160, 1126, 1125, 1081, 1154, 1126, 1119, 1116, 1119, 1152, 1114, 1105, 1101, 1064, 1064, 1088, 972, 1055, 1067, 992, 1031, 977, 1036, 1011, 1008, 976, 981, 993, 961, 987, 1001, 1002, 971, 

Концовка скучная:

0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

-- 23.03.2026, 16:43 --

wrest
А вы запустите вашу программу по моему паттерну и увидите сами будет ли похожая статистика.

[wrest]

Yadryara в сообщении #1720934 писал(а):

А вы запустите вашу программу по моему паттерну и увидите сами будет ли похожая статистика.

Так вы его дайте в тему :)
Я какой-то, кажется первый, попробовал, так он оказался кривой. Числа вида n0+k*m на него не все делятся...

[Yadryara]

wrest, как думаете, а вот это я для кого написал?

Yadryara в сообщении #1720561 писал(а):

Я же вам актуальные наборы дал, для D(96,20). Или у вас не получается запустить?

[..]

И цепочки у меня перебираются чуть иначе:

не n=n0+m*i*2

а n = v[1] * (n0 + m * i)

[wrest]

Yadryara в сообщении #1720939 писал(а):

как думаете, а вот это я для кого написал?

Ок, подожду пока вы или ещё кто дадите сюда какой-нибудь несекретный паттерн с пояснениями как пользоваться.
Чтобы не только я мог попробовать поускорять, а кто угодно.

Ну и заодно, сообщите пож-ста с какой скоростью обрабатывается у вас, ибо если у вас уже в 10 раз быстрее, то незачем улучшать em3() с 29 страницы и/или em4() c 63 страницы.
А если у вас медленнее в 10 раз - то чего не берёте em3() с 29 страницы или em4() с 63 страницы?

Кстати это может и неплохо, что у вас по-другому считается. Наводит на мысли об унификации следующей версии, em5()

[Yadryara]

wrest в сообщении #1720933 писал(а):

Однако разница в 30 раз

А посмотрите статистику для $2^{17}$. Может разница сократится. Я посмотрел на том же наборе:

                       17                               20 
                      2                                2
Вход 1161866                          1161866

                626392928                       1516879608
Выход  48608    594427232               20097   1648034388
               1220820160                       3164913996

Средн                1051                             2724

Так что ничего удивительного, что времени на обсчёт всех фильтраций для $2^{17}$ тратится меньше чем для $2^{20}$. Потому что то самое вычисление места выполняется не 3.16 миллиарда раз, а лишь 1.22 миллиарда раз.

[wrest]

Yadryara в сообщении #1720952 писал(а):

А посмотрите статистику для $2^{17}$.

На 10 млн. цепочек: всего вычислений остатков/количество проверенных цепочек на стадии таблицы простых до 2^17
? 152104570/2447742+.
%2 = 62.140768920907513945505694636117695411
?
Но это, напомню, после "терапевтики".

Подозрительно, что у вас при переходе с таблицы простых до 2^20 на таблицу до 2^17 количество вычислений остатков падает в 2724/1051~2,6 раза, а у меня в 84/62~1,4 раза

Ну мой текст em4() на 63 странице есть, подробно комментирован, так что смотрите...
И кстати, можете сами попробовать с вашим секретным паттерном для D(96,20)

[Yadryara]

wrest в сообщении #1720955 писал(а):

На 10 млн. цепочек: всего вычислений остатков/количество проверенных цепочек на стадии таблицы простых до 2^17
? 152104570/2447742+.
%2 = 62.140768920907513945505694636117695411
?
Но это, напомню, после "терапевтики".

Правильно, я тоже смотрю после терапевтики. Только не понял почему у вас в этот раз 152 миллиона, а не 22 миллиона как было. У меня-то эти числа одинаковые, специально показал их в соседних колонках:1161866 и 1161866.

[wrest]

Yadryara в сообщении #1720962 писал(а):

Только не понял почему у вас в этот раз 152 миллиона, а не 22 миллиона как было.

Потому что это на 10млн цепочек а не на 1 млн., для статистики поточнее. На 10 поделите и будет как раньше :)
Главное же это сколько вычислений на цепочку. Для таблицы 2^20 у меня ~84 вычисления остатка на цепочку, а для таблицы 2^17 соответственно 62. А у вас -- 2^20 -> 2724 и 2^17->1051.

P.S. А, кажись это не на 10, а на 9 миллионов

[Yadryara]

Ну вот чтоб не было "кажись", я и предложил считать ту же самую выборку.

wrest в сообщении #1720955 писал(а):

И кстати, можете сами попробовать с вашим секретным паттерном для D(96,20)

Ну вот я попробовал пока запустить как есть:

yadryara@DESKTOP-QPP2F5P:~/em4-wrest$ gp2c-run -g em4.gp
Warning:em4.gp:62: Assignement to a less precise type: small<-int
pat_prime_lim=nextprime(vecmax(factor(vecprod(v))[1])+1)
Warning:em4.gp:123: Assignement to a less precise type: small<-gen
/* на i-е простое разделилось d-е число цепочки *//* выясняем не входит ли i-е простое в более высокой степени чем 1 */ai=valuation(((n0+(k*m))+d)-1,pr[i])
?

[wrest]

Yadryara в сообщении #1720964 писал(а):

Ну вот я попробовал пока запустить как есть:

Всё норм. Предупреждает о возможной потере точности, если максимальное встроенное простое в паттерне будет больше 2^64 или максимальная степень простого при разложении окажется больше 2^64. Но потеря не происходит т.к. первое равно 53 а второе вряд ли больше 10.

Дальше команда em4(name,start,len,prime_limit)
name - имя воркера, можно 0 или 5 или " Вася". На счёт не влияет, это только для печати лога.
start - начальное k в цикле k=start,finish
len - сколько цепочек считать, соответственно finish=start+len-1
prime_limit - таблица простых до, например 2^20

Посчитать 2 миллиона цепочек n=n0+k*m начиная с k=3 000 000 до k=4 999 999 с таблицей простых до 2^20:
em4("Вася",3*10^6,2*10^6,2^20)

Но в em4() c 63 страницы подсчёт количества вычислений остатков не ведётся

[wrest]

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

Тут я походу неправ, вероятность что $3^5$ превратится в $3^{6+}$ целых $1/3$, а в допустимые $3^7$ аж $1/9-1/27=2/27\approx7.4\%$.

Да, счётчики показывают, что $3^6$ присутствует в трети цепочек.
Тогда в "терапевтике" надо пропустить эти $3^7$ дальше?
Типа вместо
if(n%3^6<len , next);
пишем
if(n%3^7>len && n%3^6<len , next);

[wrest]

wrest в сообщении #1721026 писал(а):

Тогда в "терапевтике" надо пропустить эти $3^7$ дальше?
Типа вместо
if(n%3^6<len , next);
пишем
if(n%3^7>len && n%3^6<len , next);

Посчитал.
Если if(n%3^6<len , next); то этим отбрасывается 3 333 334 из 10 млн. цепочек (это 3/9=1/3) а если if(n%3^7>len && n%3^6<len , next); то отбрасывается 2 222 223 из 10 млн. (это 2/9)
Скорость (общая) меняется с 221 тыс/с до 191 тыс/с

Я так понимаю, что отбрасываются цепочки только по числам где в паттерне есть 3^5 (в том что у меня, с 23 страницы, это 19-е число в цепочке).

Тогда, терапевтику троек можно ускорить, если считать не остаток от деления конечного числа n в цепочке (n=n0+k*m+len-1) на 3^6 а пропускать каждый 3-й счётчик цепочек. Поскольку n - длинное, а k - короткое, то при компиляции через gp2c будет считаться немного быстрее.

Но это, конечно, существенно паттерно-зависимая штука.
А, ну собсно мы же имеем $(n0+18)=3^6t;(m+18)=3^2u$

[wrest]

wrest в сообщении #1721030 писал(а):

Тогда, терапевтику троек можно ускорить, если считать не остаток от деления конечного числа n в цепочке (n=n0+k*m+len-1) на 3^6 а пропускать каждый 3-й счётчик цепочек. Поскольку n - длинное, а k - короткое, то при компиляции через gp2c будет считаться немного быстрее.

Попробовал, разницы в скорости нет...

-- 26.03.2026, 13:25 --

Да, кстати, добавил ещё счётчик сколькот нашлось "плохих" высших степеней при проверке по таблице простых.
То есть таких простых множителей $p_i^{a_i}$, что $48 \neq 0 \mod{a_i+1}$
Оказалось, их не менее ~9 тыс на миллион цепочек. А это, соответственно, минус 9 тыс проверок ispseudoprime на миллион (около 3% от кол-ва проверок).

[Dmitriy40]

wrest
Разумеется при константных n0 и m выражение (n=n0+m*i)%p вполне можно заменить на i%p, только условие будет сложнее (точнее для размещённых простых оно просто будет (не)равно другой величине). Если бы Вы посмотрели на любой код VAL, то там так и сделано. А вот для неразмещённых простых придётся остаток проверять по списку, а не просто <len, и как из него быстро получить правильный d для каждого простого не очень понятно.
Так что для размещённых простых сделать можно (для ниж даже и d вычислять не нужно), даже должно быть чуть быстрее.