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

[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млн встретился в разных цепочках и значит не нужно тратить время на лишние проверки делимости на простые из таблицы.