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

[Yadryara]

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

Но цепочки обычно выбывают задолго до того, как пройдут через все 84 тысячи.
Для таблицы до 2^20, в среднем вычисляется 85 раз на цепочку.

А я вот полагаю, что нужно считать не среднее, а средневзвешенное. Тем более что функцию вы сделали. И ещё нужно как-то учитывать те, которые так и не были отброшены. Хотя их и менее 0.2%.

У меня пока такие данные. Количество отбрасываний по псевдопрайм, в зависимости от количества проверенных предпростых:

  1     2     3     4     5     6     7     8     9    10    11    12    13    14    15
[ 0, 1636, 3016, 3892, 4887, 5719, 6496, 7182, 7537, 7426, 7656, 7973, 8100, 7916, 8375,

  16    17    18    19    20    21    22    23    24    25    26    27    28    29    30
8239, 8088, 8334, 8307, 8080, 8219, 8032, 7919, 8083, 8160, 7727, 7363, 7444, 7290, 7346,

Это только для 4-й фильтрации.

А средневзвешенное количество без учёта проскочивших цепочек пока довольно большое. Никакие не 85, а 1329.

[Yadryara]

Просто сумму проверок, то бишь вычислений места посчитаю.

Подали на вход после терапевтики: 1161866 цепочек.

Отбросили после двух предпростых: 1636. Проверок: 2*1636 =     3272
Отбросили после  3-х предпростых: 3016. Проверок: 3*3016 =     9048
Отбросили после  4-х предпростых: 3892. Проверок: 4*3892 =    15568
...
___________________________________________________________________
                                                         1516879608
Не было отброшено 20097 цепочек. Проверок: 82004*20097 = 1648034388
___________________________________________________________________
Всего                                                  = 3164913996

То есть неотброшенные цепочки вносят ещё больший вклад, чем все отброшенные вместе взятые.

А средневзвешенное количество, значит, стало ещё больше. Но считать пока не буду, перепроверю предыдущий результат.

-- 23.03.2026, 09:15 --

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

Никакие не 85, а 1329.

Это я не то сравнивал.

-- 23.03.2026, 09:18 --

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

Хотя их и менее 0.2%.

Менее 2%

[wrest]

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

А я вот полагаю, что нужно считать не среднее, а средневзвешенное.

Скажу так. Я посчитал количество цепочек, которые попали на стадию проверки по таблице простых до 2^20 (~272 тыс цепочек на миллион), посчитал количество вычислений остатков (примерно 22 700 тыс вычислений на миллион цепочек) и поделил, получилось ~83..85 на цепочку. Взвешенное оно или нет не понимаю
Для таблицы простых до 2^24 соответствющий коэффициент 170 вычислений остатков на цепочку.

-- 23.03.2026, 10:14 --

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

То есть неотброшенные цепочки вносят ещё больший вклад, чем все отброшенные вместе взятые.

Насчёт "вместе взытые" не знаю, но да - они очень много вносят, т.к. по ним проверка идёт по всем 82 тыс простых чисел до 2^20

Но вот у меня например общее время/скорость от размера таблицы в диапазоне 2^18...2^24 не зависит. Изменение размера таблицы в ~47 раз, при этом количество вычислений остатков меняется только в 2,4 раза.

[Yadryara]

wrest
Как раз хотел спросить у вас, что же это за число такое, 85.

Сумма произведений до  4 включительно:      27888
Сумма произведений до 85 включительно:   18524936   0.6 % от 3164913996

Более трёх миллиардов вычислений места пришлось сделать старым способом. Посмотрю на том же наборе, сколько будет новым способом.

-- 23.03.2026, 10:19 --

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

Я посчитал количество цепочек, которые попали на стадию проверки по таблице простых до 2^20 (~272 тыс цепочек на миллион), посчитал количество вычислений остатков (примерно 22 700 тыс вычислений на миллион цепочек) и поделил, получилось ~83..85 на цепочку.

Пока не понял. А можете так же как я посчитать? Или я неправильно считаю?

[wrest]

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

А можете так же как я посчитать? Или я неправильно считаю?

Я не понимаю как вы считаете. Мне кажется что я пишу очень ясно, простыми словами, но без срезаний углов, что и как. Вам наверное кажется что ясно пишете вы. Но я вас не понимаю.
Время счёта прямо пропорционально количеству одинаковых операций. Время вычисления остатка r=n%p не зависит от величин n и p (в моём em4() с 63 страницы оба числа короткие, т.е. n,p<2^64). Вот из этого и надо исходить.

[Yadryara]

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

да - они очень много вносят, т.к. по ним проверка идёт по всем 82 тыс простых чисел до 2^20

Ну вот я и умножил 82004, видите? Есть понимание как я считал?

Я пытался посчитать сколько раз выполняется вот эта строчка:

d=len-(pmods_n0[i]+k*pmods_m[i]+len-1)%pr[i];

Получилось, что 3 миллиарда раз на миллион цепочек.

У вас — сколько раз на 272 тысячи цепочек?

[wrest]

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

У вас — сколько раз на 272 тысячи цепочек?

При таблице простых до 2^20 -- 22 684 566 раз

На выходе из этапа проверки по таблице простых получается 52 цепочки из миллиона (это при размере таблицы простых до 2^20). Соответственно, доля этих 52 цепочек составляет
52*82008=4 264 416 или 19% от всех вычислений остатков.

Но эти 20% вычислений не пропадают зря, т.к. на выходе из проверки по таблице простых до 2^20, мы имеем по каждому i-му числу из цепочки $n_d=A_d\cdot B_d, d=0..20$ где A -- произведение всех простых множителей величиной до 2^20 с учётом их кратности $A=\prod \limits_{p_i<2^{20}}p_i^{a_i}$ , и A уже вычислено для всех чисел в цепочке, а также вычислено numdiv(A).
Остаётся только вычислить B=n/A, проверить B на простоту и факторизовать B, если это необходимо.

[Yadryara]

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

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

У вас — сколько раз на 272 тысячи цепочек?

При таблице простых до 2^20 -- 22 684 566 раз

На выходе из этапа проверки по таблице простых получается 52 цепочки из миллиона при ркзмере таблицы до 2^20. Соответственно, их доля составляет
52*82008=4 264 416

Вот я надеюсь, что понятно написал. У меня 1,5 ярда + 1,6 ярда = 3.1 ярда

А у вас непонятно, входят эти 4 миллиона в 22 миллиона или надо плюсовать и получать почти 27 миллионов вычислений места.

И не написано, как вы получили 22 миллиона, в какое место и какие счётчики вставили.

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

или 19% от всех вычислений остатков.

Получается что входят в 22 миллиона. Осталось понять как получены 18 миллионов из этих 22-х.

Когда пойму, как вы посчитали, а вы поймёте как я посчитал, тогда можно и о другом поговорить. А нынче пока воздержусь.

[wrest]

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

И не написано, как вы получили 22 миллиона, в какое место и какие счётчики вставили.

Вот сюда ставил:

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

сколько раз выполняется вот эта строчка:

d=len-(pmods_n0[i]+k*pmods_m[i]+len-1)%pr[i];

Получилось:

q9++;
d=len-(pmods_n0[i]+k*pmods_m[i]+len-1)%pr[i];

И вот этот q9 равен 22 684 566 после окончания вычислений, для таблицы простых до 2^20

[Yadryara]

Да, видимо, вы правильно посчитали.

3164913996 / 1161866 = 2724

22684566   /  272000 = 83

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

[Dmitriy40]

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

У меня пока такие данные. Количество отбрасываний по псевдопрайм, в зависимости от количества проверенных предпростых:

А почему возрастание не монотонное?! Что, есть цепочки, отбрасываемые по таблице до 2^9, но не отбрасываемые по таблице до 2^10?! При том что проверка простых идёт с меньшего к большему. Это вообще как так?!

[Yadryara]

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

Что, есть цепочки, отбрасываемые по таблице до 2^9, но не отбрасываемые по таблице до 2^10?!

Вроде нет таких. Может вы неправильно понимаете что я написал. Я привёл данные для $2^{20}$.

[Dmitriy40]

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

Может вы неправильно понимаете что я написал.

Может и неправильно. Объясните тогда как правильно понимать слова "Количество отбрасываний по псевдопрайм, в зависимости от количества проверенных предпростых"?

-- 23.03.2026, 15:06 --

И что значат числа 1..30 в заголовках ячеек таблицы?

-- 23.03.2026, 15:08 --

И что значит числа во второй строке таблицы?
А то что-то вообще ничего непонятно.

[Yadryara]

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

Объясните тогда как правильно понимать слова "Количество отбрасываний по псевдопрайм, в зависимости от количества проверенных предпростых"?

Здесь именно что количество проверенных предпростых:

  1     2     3     4
[ 0, 1636, 3016, 3892

То есть проверка только по одному предпростому, то бишь 79, ничего не может отбросить.

А вот проверки по двум первым предпростым, то бишь 79 и 83, и могут и отбросили. То есть в 1636 цепочках нашлось хотя бы одно число на одном из 10 подходящих мест, которое разделилось и на 79 и на 83, а затем проверка на составное, показала что число составное. Отброшено по перебору.

В каком-то количестве цепочек нашлось хотя бы одно число на одном из 10 подходящих мест, которое разделилось и на 79 и на 83, либо и на 79 и на 89, либо и на 83 и на 89, а затем проверка на составное, показала что число составное. Отброшено по перебору.
И ещё возможно, что на одном из 10 других подходящих мест, нашлось число, которое разделилось и на 79 и на 83 и на 89, а затем проверка на составное, показала что число составное. Отброшено по перебору.
Ну в сумме цепочек по этим основаниям набралось заметно больше — 3016.

А далее аналогичные проверки выполнялись уже для 4-х чисел: 79, 83, 89 и 97. И было отброшено 3892 цепочки.

[Dmitriy40]

А, то есть это не степени двойки размера таблицы, а именно что отбросы по первым простым, тогда понятно.
Ну тогда интересно как далеко сохраняется это вот плато около 7-8 тысяч на каждое следующее простое.
И где примерно это число стабильно падает скажем вдвое (если что из вектора это можно вытащить так: select(t->t<3500,q[],1)[1..20] - показать индексы первых 20 элементов меньших 3500, не один чтобы пропустить старт, а 20 чтобы убедиться в стабильности падения, может придётся и на 100 заменить).
И пожалуй интересна сумма этих чисел за последнюю половину (сколько всего отброшено простыми больше 2^19), за вторую четверть (простыми 2^18...2^19), за вторую "осьмушку" (простыми 2^17...2^18) (это всё легко получить командами типа vecsum(q[#q\8..#q\4])).
Впрочем очевидно я и сам могу всё это получить ... Если б не лениться.