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

[Yadryara]

Решил разбираться с функцией em3, не торопясь. В интерпретаторе на сильно загруженном компе запускал пока так:

for(i=0,7,em3(i,i*10^6,10^6,2^20))

И сделал нормальную табличку:

  Старт  Интервал   Таблица   Подго  Найдено   Прошло    Проверено  Cкорость   Время
  канди       млн   простых   товка  цепочек  цепочек  псевпростых     счёта   счёта
  датов                  до                                          цеп/сек     сек
      0         1   1048576   24 ms        1        2      1100107     13488    74.1
1000000         1   1048576   23 ms        0        0      1098511     14419    69.4
2000000         1   1048576   23 ms        0        1      1098296     13639    73.3
3000000         1   1048576   24 ms        0        1      1097853     13992    71.5
4000000         1   1048576   25 ms        0        3      1097228     13675    73.1
5000000         1   1048576   26 ms        0        2      1097272     13471    74.2
6000000         1   1048576   24 ms        0        1      1097228     13672    73.1
7000000         1   1048576   20 ms        0        2      1096437     13558    73.8

[wrest]

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

Решил разбираться с функцией em3, не торопясь. В интерпретаторе на сильно загруженном компе запускал пока так:

Хорошо. По крайней мере, работает
Немного странно что 4-й миллион, где прошло 3 цепочки, по скорости недостаточно сильно упал относительно тех, где прошли 1 и 2 цепочки. Видимо, сказывается загруженность компа.
После компиляции ожидайте минимум 4-кратный рост при параллельном запуске, может и больше.

[Yadryara]

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

Немного странно что 4-й миллион, где прошло 3 цепочки, по скорости недостаточно сильно упал относительно тех, где прошли 1 и 2 цепочки.

Не 4-й, а 5-й миллион. Сейчас лучше:

? default(parisizemax,2^27)
? init_wrest_2()

      0    1000000   1048576  11 ms   1   2   1100107   69783   14,330 ms
1000000    1000000   1048576   7 ms   0   0   1098511   76887   13,006 ms
2000000    1000000   1048576   7 ms   0   1   1098296   72955   13,707 ms
3000000    1000000   1048576   8 ms   0   1   1097853   67732   14,764 ms
4000000    1000000   1048576   7 ms   0   3   1097228   61496   16,261 ms
5000000    1000000   1048576   8 ms   0   2   1097272   67453   14,825 ms
6000000    1000000   1048576   7 ms   0   1   1097228   69454   14,398 ms
7000000    1000000   1048576   7 ms   0   2   1096437   68662   14,564 ms

1min, 55,925 ms

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

После компиляции ожидайте минимум 4-кратный рост при параллельном запуске, может и больше.

Параллельный пока не пытался делать. Обычный да, почти в 5 раз быстрее. Но обольщаться не буду.

[wrest]

Yadryara
Есть ещё такой лайфхак.
Обратите внимание на комментарий в тексте с функцией em3 в самом начале:

/*
GP;default(threadsize,32M);
GP;default(debugmem,0);
*/

gp2c добавляет то, что идет в комментарии после символов "GP;" как команды в файл *.gp.run
Соответственно, когда вы даёте команду gp2c-run -g <filename>.gp то после компиляции и запуска интерпретатора, эти команды выполняются в интерпретаторе. Так что вы можете добавить например такой комментарий

/*
GP;default(parisizemax, 2^27);
GP;init_wrest_2();
*/

и исполнение запустится автоматически

[wrest]

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

[Dmitriy40]

(Оффтоп)

Да, очень сложно/некомфортно видя цифру 4 говорить пятый ...

[Yadryara]

wrest
Спасибо. А я-то всё думал: кто это романсы поёт инстансы

Вот теперь на пустом компе разное количество потоков погонял. Вот результаты для 12-ти.

  Старт  Интервал   Таблица   Подго  Найдено   Прошло    Проверено  Cкорость       Время
  канди       млн   простых   товка  цепочек  цепочек  псевпростых     счёта       счёта
  датов                  до                                          цеп/сек     
      0   1000000   1048576    7 ms        1        2      1100107    110023    9,089 ms
1000000   1000000   1048576    4 ms        0        0      1098511    125360    7,977 ms
2000000   1000000   1048576    4 ms        0        1      1098296    117439    8,515 ms
3000000   1000000   1048576    4 ms        0        1      1097853    113173    8,836 ms
4000000   1000000   1048576    4 ms        0        3      1097228    100170    9,983 ms
5000000   1000000   1048576    4 ms        0        2      1097272    106507    9,389 ms
6000000   1000000   1048576    4 ms        0        1      1097228    112321    8,903 ms
7000000   1000000   1048576    4 ms        0        2      1096437    104777    9,544 ms
8000000   1000000   1048576    4 ms        0        1      1096459    111209    8,992 ms
9000000   1000000   1048576    5 ms        0        0      1097220    123046    8,127 ms
10000000  1000000   1048576    5 ms        0        2      1095642    104733    9,548 ms
11000000  1000000   1048576    4 ms        0        2      1096163    104144    9,602 ms
                                                                         1min, 48,562 ms

      0   1000000   1048576    70 ms       1        2      1100107    68460    14,607 ms
1000000   1000000   1048576    68 ms       0        0      1098511    76976    12,991 ms
2000000   1000000   1048576    70 ms       0        1      1098296    72547    13,784 ms
3000000   1000000   1048576    73 ms       0        1      1097853    70651    14,154 ms
4000000   1000000   1048576    74 ms       0        3      1097228    64804    15,431 ms
5000000   1000000   1048576    69 ms       0        2      1097272    67503    14,814 ms
6000000   1000000   1048576    71 ms       0        1      1097228    69594    14,369 ms
7000000   1000000   1048576    72 ms       0        2      1096437    66401    15,060 ms
8000000   1000000   1048576    69 ms       0        1      1096459    69036    14,485 ms
9000000   1000000   1048576    71 ms       0        0      1097220    74716    13,384 ms
10000000  1000000   1048576    71 ms       0        2      1095642    66361    15,069 ms
11000000  1000000   1048576    70 ms       0        2      1096163    66291    15,085 ms
                                                                               15,531 ms

[wrest]

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

Вот результаты для 12-ти.

Не хватает вам ясности изложения. Попробую восполнить.

Итого, суммарная скорость скомпилированной программы в многопоточном режиме составила 12млн. цепочек / 15,53 сек = 773 тыс. цепочек в секунду. То есть комп обсчитал 12 млн. цепочек за 15,5 секунд - верно?
В однопоточном режиме скомпилированная программа показала скорость 12 млн. цепочек / 1 мин 48,6 сек = 110 тыс. цепочек в секунду.

Коэффициент многопоточности составил 773 тыс цепочек/ (12 потоков * 110 ) = 0,6 на поток.

И это, как я понимаю, 100% проверка, то есть с дофакторизаций всех прошедших через фильтр цепочек, верно?

Неплохо!

Ну и -- какой же произошёл прирост скорости по сравнению со скоростью которая была до истории с установкой WSL (и до оптимизации собственно алгоритма)?

[Yadryara]

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

То есть комп обсчитал 12 млн. цепочек за 15,5 секунд - верно?
В однопоточном режиме скомпилированная программа показала скорость 12 млн. цепочек / 1 мин 48,6 сек = 110 тыс. цепочек в секунду.

Коэффициент многопоточности составил 773 тыс цепочек/ (12 потоков * 110 ) = 0,6 на поток.

Три раза да.

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

И это, как я понимаю, 100% проверка, то есть с дофакторизаций всех прошедших через фильтр цепочек, верно?

Нет. Потому что я не изменял суть вашей функции. А в ней нет допроверки.

Ещё я посчитал время для тех же 12 миллионов для $2^{18}$ и $2^{19}$. Оно похуже — 19.0 и 17.4 секунды соответственно.

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

Ну и -- какой же произошёл прирост скорости по сравнению со скоростью которая была до истории с установкой WSL (и до оптимизации собственно алгоритма)?

Затрудняюсь ответить. Мне интереснее всего узнать какой будет эффект, если я смогу реализовать эти новшества в рабочей программе.

В ней получение начального числа цепочки-кандидата, то есть n, гораздо сложнее.

[wrest]

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

Потому что я не изменял суть вашей функции. А в ней нет допроверки.

В функции em3 с 29-й страницы -- проверка есть:

  \\ прошедшие полностью факторизуем, не будем откладывать.
  n=n0+2*k*m; c=0; for(i=1,len,if(numdiv(n+i-1)==48,c++));if(c==len,q2++);

Иначе в стартовом миллионе ничего бы не нашлось (в столбце "найдено цепочек" был бы ноль).

-- 08.12.2025, 18:46 --

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

Ещё я посчитал время для тех же 12 миллионов для $2^{18}$ и $2^{19}$. Оно похуже — 19.0 и 17.4 секунды соответственно.

Да, и как раз из-за окончательной проверки numdiv-ом прошедших через фильтр цепочек. Больше прошло -> дольше проверка.

-- 08.12.2025, 18:57 --

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

В ней получение начального числа цепочки-кандидата, то есть n, гораздо сложнее.

Ну тут такое дело: функция em3() исходит из того, что числа n это арифметическая прогрессия, n(k)=n0+2*k*m и в этом случае в главном цикле не надо реально делить на простые, чтобы определить делимость.
Кстати шаг прогрессии сейчас не передаётся как параметр, шаг просто равен 2m. Учтите это при модификации.

[Yadryara]

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

В функции em3 с 29-й страницы -- проверка есть:

Да, конечно. Уже успел забыть. Видимо потому что я её в рабочей проге выкинул и свою проверку делал с подсчётом valids и расстановкой единичек и пробелов.

Тогда и 4-й ответ: "да". Допроверка была сделана. В этот раз её не выкидывал.

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

Ну тут такое дело: функция em3() исходит из того, что числа n это арифметическая прогрессия, n(k)=n0+2*k*m и в этом случае в главном цикле не надо реально делить на простые, чтобы определить делимость.

А при нынешней серии паттернов ещё до того как посчитано n, уже ясно, что одно частное на конкретном месте — простое. А поскольку простые среди огромных чисел редкость, дело редко доходит до начала проверки цепочки.

Вот есть такая предварительная фильтрация:

kanp = n0 + m * i;
if(!ispseudoprime(kanp,1), next);
n = aa * kanp - ip;

[wrest]

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

Вот есть такая предварительная фильтрация:

kanp = n0 + m * i;
if(!ispseudoprime(kanp,1), next);
n = aa * kanp - ip;

Не ясно что это значит. Кто такой канп и почему он может быть простым если обязательно должен делиться на v[1]. Опять загадки.
Ну ок, я предупредил :)

[Yadryara]

канп — КАНдидат в Простые. По просьбе Владимира перебор идёт не по k, а по i.

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

Кто такой канп и почему он может быть простым

Не может быть простым, а должен быть простым. Иначе берём следующее i.

Потому что всего 22 частных, к которым есть чёткие требования: 1 частное должно иметь ровно 2 делителя (onlyp[]), 1 частное должно иметь ровно 4 делителя (pq[]), 17 частных должны иметь ровно 8 делителей (pqr[]), 3 частных должны иметь ровно 16 делителей (pqrs[]).

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

если обязательно должен делиться на v[1].

Совершенно он не должен ни на какое v[] делиться.

[Dmitriy40]

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

Не ясно что это значит.

В эталонном коде нет мест кортежа где после деления на v[] должно остаться одно простое, а в коде Yadryara такое место есть.
Потому он перебирает не k, а i, и сначала получает это простое, проверяет что оно не составное и только тогда получает нормальное пригодное к дальнейшей проверке n. И там свои (другие) n0 и m (надо было назвать их p0 и mp).
Так что kanp это (n+ip-1)/v[ip] в позиции ip, которое должно быть простым (2 делителя numdiv или 1 omega).
Потому что проверка на простоту в данном случае была быстрее проверки остальных мест на количество делителей. Плюс там тоже использован трюк с forprime и проверкой не разделилось ли оно на малые простые (что быстрее isprime). И да, в нём тоже можно заменить деление на сложение по модулю или хотя бы на короткое деление как у Вас.

[wrest]

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

И да, в нём тоже можно заменить деление на сложение по модулю или хотя бы на короткое деление как у Вас.

А чем сложение по модулю отличается от короткого деления?
Вот делить-то можно например вычитанием, а умножать -- сложением :)