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

[Dmitriy40]

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

1. Надо собрать то, что попадает на полларда сейчас. Тестовый набор, так сказать, ну скажем из 100 чисел хотя бы.

Это разве проблема? Убираете Полларда с MPQS и запускаете для 200млн цепочек (минут на 15), вывалится в лог примерно 8*10=80 цепочек, плюс-минус.

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

Не думаю. Там же всё таки только ispseudoprime и всё.

Проблема не в том что там одна ispseudoprime, а в том что их запускается существенно больше (это и посчитать бы поточнее) чем в результате отбрасывается цепочек, т.е. низок КПД отброса. Вопрос конечно сколько раз вызывалась ispseudoprime для недобора делителей.

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

С замером времени засада на планшете. Очень нестабильно - чуть поработает и тротлит А может андроид там чегонибудь задумает и смещает с производительного ядра насоседнее и т.п.

Ну с тротлингом как бороться не знаю (разве что такты процессора считать вместо реального времени), а вот с перескоком между ядрами можно и средствами ОС: запускаете интерпретатор gp, средствами ОС разрешаете ему выполняться ровно на одном ядре, запускаете в gp тестируемую прогу. Как именно назначить ядро в линуксе я не в курсе, но точно можно (под виндой или через диспетчер задач вручную, или start /AFFINITY 0x01 gp.exe -q my.gp с правильном маской конечно).

[wrest]

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

Ну с тротлингом как бороться не знаю (разве что такты процессора считать вместо реального времени), а вот с перескоком между ядрами можно и средствами ОС: запускаете интерпретатор gp, средствами ОС разрешаете ему выполняться ровно на одном ядре, запускаете в gp тестируемую прогу. Как именно назначить ядро в линуксе я не в курсе, но точно можно

Бороться с тротлингом известно как: вентилятором. У меня есть, там пельтье охлаждает стенку планшета, а вентилятор охлаждает пельтье. Но это шумно На планшете у юзера нет никаких заметных прав в линукс без root-а. А на ноутбуке этой проблемы нет: там ядра одинаковые.

-- 21.03.2026, 01:32 --

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

Проблема не в том что там одна ispseudoprime, а в том что их запускается существенно больше (это и посчитать бы поточнее) чем в результате отбрасывается цепочек, т.е. низок КПД отброса. Вопрос конечно сколько раз вызывалась ispseudoprime для недобора делителей.

Посчитал:

? em4(666,0,20*10^6,2^20)
666-й поток приступил. Поиск D(48,21)
База n0=283938699868309713921641266159023371777169 шаг 2*m=458807004108608150236210618789181133892800
Задание: Старт: 0 шагов:20000000 Таблица простых до:1048576
Паттерн:секретный. Подготовился за:14 ms
Дошло до numdiv: 52556626259340931919271848023566857910792017169
Найдено D(48,21):52556626259340931919271848023566857910792017169
666-й поток кончил. Дошло до numdiv: 1 Найдено:1 Отброшено:19999999
Фильтры терапевтика:14556473 таблица:5442409 недобор:1109 Поллард/mpqs:8  numdiv:0
Проверок псевдопростых всего:5760033 из них в таблице:5755542 в недоборах:4439 в полларде:105
Проверок поллардом/mpqs начато:47 Поллард/mpqs нашёл множитель:52
Cкорость счета: 137337 цеп/сек. Время счёта:2min, 25,627 ms
time = 2min, 24,367 ms.
%1 = 1
?

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

[Dmitriy40]

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

Посчитал:

Выходит практическая каждая 4-я ispseudoprime результативна (отбрасывает цепочку), круто, все более сложные тесты думаю этого не пересилят: у меня ispseudoprime выполняется в среднем за 12мкс, три "лишних" вызова займут пусть 40мкс на цепочку или 45мс на все 1109 цепочек, из 145с общего времени это ничто.

[wrest]

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

меня ispseudoprime выполняется в среднем за 12мкс, три "лишних" вызова займут пусть 40мкс на цепочку или 45мс на все 1109 цепочек, из 145с общего времени это ничто.

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

Вообще я так скажу. Добавление проверки высших степеней в табличной части заметно замедлило счёт, а вот добавление проверки на недобор это замедление практически компенсировало. Такое у меня впечатление.

-- 21.03.2026, 02:01 --

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

Но там я и сам пока не осознал как в полларда вошло 47 цепочек, откинуто 8, а вышло ноль

А, ну я же считаю именно вызовы полларда. Ну вот на 8 цепочек понадобилось 47 вызовов. А результатов (успешных факторизаций) получено 52, т.е. были повторные вызовы на то же число. Выходит в среднем 7 вызовов поллардов или mpqs (отдельных счётчиков нет) на цепочку. Ну оно и понятно: до полларда дошли цепочки где скорее всего будет ровно или перебор чем недобор, т.к. недобор отфильтровали на предыдущей стадии.

И ещё статистика: в таблицу простых добавилось 40 чисел (у меня включено это).
Самое большое 117 бит.

? logint(165442140070855257127511604843401861,2)+1
%5 = 117

Это множитель 16-го числа в рекордной цепочке D(48,21)

[Dmitriy40]

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

в таблице "быстрая" проверка с ключом 1, а дальше медленная, без ключа.

Это (ключ 1 в таблице) не так принципиально, хоть и заметно, разница в скорости 10%-20%.
Только не в таблице и вне её, или быстрая и медленная, а с перебором (можно с ключом 1 и вообще >0, проверяем что число точно составное) и с недобором (обязательно без ключа или с ключом 0, проверяем что число точно простое). Т.е. проверка числа на простое обязательно без ключа, на составное можно и с ключом.

-- 21.03.2026, 02:33 --

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

И ещё статистика: в таблицу простых добавилось 40 чисел (у меня включено это).

Я обычно очищаю таблицу при переходе к следующей цепочке (после терапевтики чтобы пореже) - слишком невероятно чтобы один и тот же простой делитель больше 16млн встретился в разных цепочках и значит не нужно тратить время на лишние проверки делимости на простые из таблицы.

[wrest]

Dmitriy40
Я пока не придумал нужна ли мне эта таблица.
Я вижу что между появлениями строк
Кстати default не работает в gp2c (не может транслироваться в .с)
Пока пришлось добавить в конфиг.

[Yadryara]

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

Кстати default не работает в gp2c (не может транслироваться в .с)

Ну так я уже писал, что игрался с этой парочкой:

default(factor_add_primes,1);
removeprimes(addprimes());

И обнаружил что никакого влияния это вроде бы не оказывает.

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

Пока пришлось добавить в конфиг.

И она заработала? Как это сделать-то? Может у меня наконец проблемы с памятью прекратятся?

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

Warning: increasing stack size to 16000000.

Warning: increasing stack size to 32000000.

И не понимаю толком сколько памяти выделять на поток. А сильно много не могу.

[wrest]

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

И обнаружил что никакого влияния это вроде бы не оказывает.

Встроенная факториззация, при установленном factor_add_primes=1, добавляет в таблицу найденные простые. Поэтому, если прервать например factor по таймеру, то он ничего вернуть не успеет, но найденные простые в таблицу добавит (в предположении, что добавление в таблицу делается сразу, а не по окончании факторизации). А при следующей факторизации, будет пробовать подходят ли простые из таблицы.
Тогда, например замерив размер таблицы до и после, можно понять пополнилась ли она, т.е. успел ли factor что-то найти.

[Yadryara]

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

Но вы ведь только что написали что она не работает с трансляцией (а значит и с компиляцией), то бишь, как понимаю и у меня не работает:

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

Кстати default не работает в gp2c (не может транслироваться в .с)

[wrest]

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

И не понимаю толком сколько памяти выделять на поток.

Текущий размер стека (сколько занято) можно узнать командой getstack(), но стек постоянно опорожняется, это временная память.

? a=getstack();v=vector(10^6,i,10^30);b=getstack();print(a," ",b)
968 40001072
time = 205 ms.
? getstack()
%23 = 232

Постоянно занятая память называется куча (heap) и её размер можно узнать командой getheap()
Если вы создали какой-то большой вектор, то он попадает в кучу.

-- 21.03.2026, 11:35 --

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

Но вы ведь только что написали что она не работает с трансляцией

Я этого не писал. Механизм добавления найденных простых работает.
Что не работает в функциях созданных gp2c - это изменение настроек интерпретатора, т.е. команда default()

[Yadryara]

Извините, получается я перепутал default() и default(factor

Благодарю за ликбез про память. Мой вопрос был несколько не о том. Почему комп перестал сообщать об увеличении размера стека? Это было так удобно.

А сейчас я вот задал предел в 2000МБ для каждого из 6-ти потоков. Чувствовалось, что компу трудно пришлось: он сильно тормозил другие действия, в том числе браузер. Сейчас уже часть потоков завершилась.

Менял количество предпростых: брал 19, 20 и 21-ю степень 2-ки.

   19
  2  
  [1e58, 55738368, 21075850, 483015, 7091, 663, 11]               2h, 53min, 11,678 ms

   20
  2  
  [0, 55738368, 21076915, 364446, 4265, 445, 15]               3h, 36min, 32,145 ms
  [0, 55738368, 21075094, 364196, 4319, 456, 15]               3h, 43min, 13,586 ms

Здесь я по-прежнему показываю количество прошедших через фильтры цепочек. Кроме первого, там число не 0, а в 6 раз больше чем 55738368.

[wrest]

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

Мой вопрос был несколько не о том. Почему комп перестал сообщать об увеличении размера стека? Это было так удобно.

Тут нужна способность к телепатии, которой у меня нет.
Возможно комп не сообщает об увеличении потому что увеличение не происходит, так что не о чем и сообщать. Возможно параметр debugmem выставлен в ноль, это отключает сообщения о стеке. Может ещё что...

-- 21.03.2026, 13:04 --

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

Извините, получается я перепутал default() и default(factor

В функциях созданных при помощи gp2c не работает команда default,

Цитата:

Some functions are built-in in GP, and so are not available to libpari programs. So if you use them gp2c generate a program that needs to run under GP, or with gp2c-run. Since the C prototype for those functions are not available, the C compiler will output a warning. This serves as a reminder of the problem. They are all the plotting functions and allocatemem, default, extern, input, quit, read, system, whatnow.

Но написано так, что если запускается в интерпретаторе то работает. В общем неясно.

-- 21.03.2026, 13:08 --

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

А сейчас я вот задал предел в 2000МБ для каждого из 6-ти потоков. Чувствовалось, что компу трудно пришлось: он сильно тормозил другие действия, в том числе браузер.

Ну это скорее хорошо чем плохо, т.к. комп занимается делом: фильтрует цепочки, а не развлечениями типа сёрфинга интернета

-- 21.03.2026, 13:15 --

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

И не понимаю толком сколько памяти выделять на поток.

Тут ещё такое дело. "Поток" имеет в pari/gp конкретный смысл, и параметр для ограничения памяти для потока, называется threadsize и threadsizemax - это аналоги parisize и parisizemax в случае использования параллелизма, см. https://pari.math.u-bordeaux.fr/dochtml ... threadsize

[Yadryara]

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

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

Возможно комп не сообщает об увеличении потому что увеличение не происходит, так что не о чем и сообщать.

Телепатия тут ни при чём. Я же выше приводил скрин, что ему даже и 800 с чем-то MБ не хватает.

Раньше я неоднократно наблюдал такую совершенно планомерную картину увеличения памяти вдвое:

Warning: increasing stack size to 16000000.
Warning: increasing stack size to 32000000.
Warning: increasing stack size to 64000000.
Warning: increasing stack size to 128000000.
Warning: increasing stack size to 256000000.
Warning: increasing stack size to 512000000.
Warning: increasing stack size to 888000000.

И только после этого он сообщает что 800 с чем-то MБ ему мало.

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

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

Возможно параметр debugmem выставлен в ноль, это отключает сообщения о стеке.

Вот я про то же. Думаю, что инфа о стеке просто отключена. Только я её сознательно не отключал.

Вот такой main.c у меня. Вроде простой

#include <pari/pari.h>
extern void init_Test_21(void);

int main(int argc, char **argv) {
    pari_init(1500000000, 2);
    init_Test_21();
    pari_close();
    return 0;
}

Команда сложнее:

cd  &&  cd Pollard/21  &&  gp2c -g Test_21.gp > Test.gp.c  &&  gcc -o Test Test.gp.c main.c -lpari -lm   &&  ./Test

То есть всего два новых файла создаются: Test.gp.c и Test без расширения. А не 4 как раньше.

[Dmitriy40]

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

Думаю, что инфа о стеке просто отключена. Только я её сознательно не отключал.

Не отключали, но сразу выделили ему 1.4ГБ командой pari_init(1500000000, 2) - вот ему пока и хватает. Как не хватит - увеличивать не будет (для этого надо менять parisizemax), а сразу вылетит с ошибкой.

[Yadryara]

Это не я, это Квен в своё время предложил эту команду. А сделать как раньше, типа default(parisizemax, 1500M); не получается.

Интересное кино:

   17
  2  
  [0, 55738368, 21077202, 881954, 20926, 1322, 10]             1h, 13min, 59,600 ms

   18
  2  
  [0, 55738368, 21077663, 647950, 12165, 941, 17]              1h, 25min, 44,517 ms

   19
  2  
  [0, 55738368, 21075850, 483015, 7091, 663, 11]               2h, 53min, 11,678 ms
  [0, 55738368, 21078040, 482778, 7206, 627, 10]               1h, 39min, 43,367 ms

   20
  2  
  [0, 55738368, 21076915, 364446, 4265, 445, 15]               3h, 36min, 32,145 ms
  [0, 55738368, 21075094, 364196, 4319, 456, 15]               3h, 43min, 13,586 ms
  [0, 55738368, 21075972, 364069, 4262, 449, 15]               4h,  1min,  6,258 ms

   21
  2  
  [0, 55738368, 21076676, 278307, 2584, 312, 19]               5h, 20min, 29,142 ms
  [0, 55738368, 21078078, 278623, 2480, 315, 17]               5h, 13min,    868 ms

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

А скорость ещё буду перепроверять в одном потоке.