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

[Dmitriy40]

wrest
Задача не время ограничить, а делители найти.
А factor без порога умеет их находить быстро (менее 0.1с) и больше 2^20, методом ECM.
Но чтобы он не стал искать их секундами и надо ограничить время работы factor без порога.

[wrest]

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

А factor без порога умеет их находить быстро (менее 0.1с) и больше 2^20, методом ECM.

А, вон оно что. Так-то Yadryara пишет что

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

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

Я думал, что за миллисекунды до SQUFOF/ECM и дело-то не дойдёт даже.
Ну в общем задача видится решаемой, но надо потрудиться :)
Ну и я полагаю, что если даже будет предложен способ не прямой замены alarm() а с некоторым изменением подхода, то тоже хорошо.

Qwen предлагает сделать библиотеку с функцией alarm_usec() которая будет принимать микросекунды:

Используется синтаксис C

/* alarm_usec.c */
#include <pari/pari.h>
#include <sys/time.h>
#include <signal.h>

/* 
 * Функция устанавливает таймер на usec микросекунд.
 * Когда время выйдет, ядро PARI получит SIGALRM и прервет вычисление.
 */
void alarm_usec(long usec) {
    struct itimerval timer;
    
    /* Если usec <= 0, отключаем таймер */
    if (usec <= 0) {
        timer.it_value.tv_sec = 0;
        timer.it_value.tv_usec = 0;
    } else {
        timer.it_value.tv_sec = usec / 1000000;
        timer.it_value.tv_usec = usec % 1000000;
    }
    
    /* Интервал 0 означает одноразовый таймер (как стандартный alarm) */
    timer.it_interval.tv_sec = 0;
    timer.it_interval.tv_usec = 0;

    /* ITIMER_REAL генерирует SIGALRM, который PARI уже ловит */
    if (setitimer(ITIMER_REAL, &timer, NULL) < 0) {
        pari_err(e_SYS, "setitimer");
    }
}

затем использовать так:

Используется синтаксис C++

/* 1. Подключаем функцию из библиотеки */
/* vL означает: void return, Long argument */
install(alarm_usec, vL, alarm_usec, "./alarm_usec.so");

/* 2. Вспомогательная функция для удобного вызова */
alarm_ms(ms) = alarm_usec(ms * 1000);

/* 3. Пример использования с обработкой прерывания */
test_alarm() = {
    my(res);
    iferr(
        /* Начинаем таймер на 500 миллисекунд */
        alarm_ms(500); 
        
        /* Запускаем тяжелое вычисление */
        /* Например, факторизация большого числа */
        res = factor(2^127 - 1); 
        
        /* Отключаем таймер, если успели */
        alarm_usec(0); 
        
        print("Вычисление завершено успешно: ", res);
    ,
        /* Обработка ошибки прерывания */
        E -> {
            if (component(E, 1) == "alarm interrupt",
                print("Время вышло! Вычисление прервано.");
            ,
                /* Если ошибка другая, пробрасываем дальше */
                error(E)
            )
        }
    );
}

/* Запуск */
test_alarm();

[Yadryara]

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

Я думал, что за миллисекунды до SQUFOF/ECM и дело-то не дойдёт даже.

Так я же приводил времена:

   1 ms
>2  242 ms
   80 ms
   1,683 ms
   1,504 ms
>2  148 ms
   2 ms
   3 ms
   44 ms
>2  119 ms
   3 ms
   9 ms
>2  136 ms

То есть немаленькая часть чисел полностью раскладывается за единицы миллисекунд.

-- 06.03.2026, 18:23 --

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

Так оставьте только проверку до 2^20 по словарю через factor(n,2^20),

Вы уже забыли? Там другая проверка. Берётся фактор, например, 97 и на делимость на него проверяется сразу вся цепочка. Не 20 раз, а один. Затем следующий. И так до $2^{20}$.

[wrest]

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

Вы уже забыли?

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

-- 06.03.2026, 18:42 --

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

Берётся фактор, например, 97 и на делимость на него проверяется сразу вся цепочка. Не 20 раз, а один. Затем следующий. И так до $2^{20}$.

И при чём тут alarm()?

-- 06.03.2026, 18:51 --

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

Так я же приводил времена:

Приводили, наверное. Но т.к. вы недостаточно ясно описали что вы приводили, то и результат такой: у аудитории в моём лице не отложилось.

-- 06.03.2026, 18:52 --

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

А каким образом у Вас вообще работает код #factor()[2]?! У меня он выдаёт ошибку:

Всё хотел ответить и забывал. gp2c рассматривает векторы и матрицы как один тип: vec по крайней мере я так понял отсюда https://pari.math.u-bordeaux.fr/pub/par ... .html#sec4

Цитата:

vec Vectors and matrices of PARI objects, represented by t_VEC, t_COL or t_MAT GENs.

[Yadryara]

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

И при чём тут alarm()?

Тут конечно ни при чём.

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

[wrest]

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

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

Никак, пока она не появится, не будет опробована и т.п.
План такой:

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

Сперва надо определиться вставлять ли новую функцию в ядро или делать в стороне и подключать через паришный install
Затем выяснять как устроена сигнализация в pari/gp чтобы в неё беспроблемно встроиться.
Ну и потом приступать к реализации задуманного.
Т.е. нужно провести R&D :) Для чего нужен специалист, ну или долгое общение с ИИ.

[Yadryara]

Тоже пообщался с Квеном, сделал кое-какие тестовые запуски. Ну вот он, например, пишет вроде совсем простой совет:

Цитата:

/* В начале файла с gp2c директивами */
#install(ualarm, uuu, ualarm) \\ Регистрируем системную функцию

/* В коде GP */
{
my(long usec = 500000); \\ 0.5 секунды в микросекундах
ualarm(usec, 0); \\ Вызов C-функции
/* Ваше вычисление */
factor(...);
ualarm(0, 0); \\ Отключение
}

Но я пока не понимаю что это за файл "с gp2c директивами".

[wrest]

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

Но я пока не понимаю что это за файл "с gp2c директивами".

Вырвано из контекста, но вы наверное спрашивали про gp2c?
Спросите у Квена что оно имело в виду :) Видимо, это, см. https://pari.math.u-bordeaux.fr/pub/par ... html#sec23

4.6  The install command
The install command is interpreted as a gp2c directive. This allows using installed function in compiled programs, see Section 2.4.

However this has some side-effects:

If present, the lib argument must be a string, not an expression that evaluate to a string.
The install command is not compiled, instead it is added to the list of functions to install.

Ну и, кажется, вас догоняет нежелание писать функции :)

[Yadryara]

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

Спросите у Квена что оно имело в виду :)

Спросил конечно. Оказалось, это самое начало файла .gp.

Ну и вопросы-ответы продолжались около 10 вопросов, пока бесплатный доступ не закончился.

То есть его же код не работал, он исправлял, затем исправлял снова и снова. И это нередко бывает, даже когда он говорит что код будет работать. Так что я по-прежнему им редко пользуюсь.

Вот один из самых последних вариантов кода:

#install(ualarm, lll, ualarm)

{
    ualarm(500000, 0);       \\ 0.5 секунды (500000 микросекунд)
    factor(10000000000000000000000000069800000000000000000000000120901);
    ualarm(0, 0);            \\ Отключение таймера
}

Это 59-значное число, удобное для тестирования alarm, на разложение которого через factor компу потребовались 2 секунды.

[wrest]

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

Ну и вопросы-ответы продолжались около 10 вопросов, пока бесплатный доступ не закончился.

Вроде же Квен бесплатный в принципе?

[Yadryara]

Как вижу, бесплатный, только ограниченный. Хотя может это потому что я там не регаюсь, а выбираю "Оставаться вышедшим".

Кстати у меня-то рабочий код по другому начинается. Вот он тестовый код полностью:

/*
GP;init_Test_1();
*/                  
/*                      
GP;quit;                
*/                      
{t0=getwalltime(); print; t3=getwalltime();

if( type(kfnew = alarm(3,factor(
10000000000000000000000000069800000000000000000000000120901))) <> "t_ERROR",

print(strtime(getwalltime()-t3) , "   ", kfnew[1] , "   ", kfnew[2]) ;

);

print;print("                               ",strtime(getwalltime()-t0));print;
}

И вот в этом варианте как раз видно как он раздербанивает матрицу на два вектора:

yadryara@DESKTOP-QPP2F5P:~/TEST$ gp2c-run -g Test_1.gp

2,103 ms   [100000000000000000000000000319, 100000000000000000000000000379]~   [1, 1]~

                               2,104 ms

[DemISdx]

Yadryara
Нужно быть крайне осторожным в попытках добраться до миллисекунд.
Иначе получится прямо противоположный эффект от названия темы.

(Оффтоп)

В линуксах чувствительность обычно 1000000 тикеров на секунду.
Если пытаться отловить один из этой массы, то на его перехват потребуется энное число тикеров из этой-же массы.
Ведь в эту массу входят все и вся, что отвечает за работу самой системы.
Поэтому в системах введены делители.
Чтобы системы не тормозили, есть некоторое число параметров отвечающих за эти делители.

Прошито это, например, в параметре CONFIG_HZ=1000 в бутконфиге загрузки линукса.
т.е. получается 1000000 / 1000 = 1000 и вот полученное это "как часто" мы можем что-то считывать программным образом.
Под виндой, если мне не изменяет память, последнее равно 128-ми.

[Yadryara]

Ну это вроде понятно что сама ловля тоже занимает время. Непонятно только как ловить эти доли секунды. Кто-нибудь, приведите, пожалуйста, хоть какой-то работающий пример.

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

В любой цепочке-кандидате есть круглым счётом 20 чисел. И отбросить её можно по любому из этих чисел.

В какой-то момент нужно только знать раскладывается то или иное число на 2 фактора или на больше чем 2. И список таких чисел обычно немаленький. Ну вот быстренько попытались проверить одно число, если через какое-то маленькое время факторизация не закончена, считаем его пока подходящим, прерываем его проверку и проверяем следующее число.

Сколько именно времени проверять, покажет практика.

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

2-я фильтрация: запреты по допам для перебираемого места с простым (до 600).

4-я фильтрация: проверка всей цепочки по предпростым до $2^{20}$, сбор факторов

Вот меня же не спрашивают почему до 600 или почему до $2^{20}$. Эти числа на практике было получены и они могут меняться. Насколько помню, D(24,20) была найдена с настройкой $2^{19}$.

[Dmitriy40]

DemISdx
А ещё, насколько я представляю как сделано в PARI, завершение времени таймером не обрывает выполняющийся процесс, а лишь вызывает некую call_back функцию, которая ставится в очередь исполнения планировщика и которая потом когда получит управление посылает сигнал основному процессу прервать вычисления и восстановить состояние. В итоге, сигнал будет послан когда произойдёт переключение задач планировщиком, плюс к этому основной процесс должен снова получить управление (а ведь могут быть и другие активные процессы ждущие выполнения), опросить очередь сообщений и адекватно отреагировать. Если в системе активных процессов (в очереди планировщика) больше количества логических ядер, то получение сигнала может отложиться на тик (а то и больше) переключения задач. Плюс основной процесс может нечасто опрашивать очередь сообщений (или вообще не опрашивать).
В итоге времена менее нескольких тиков переключения задач планировщиком ловятся ненадёжно, как повезёт.

Вот сделать паузу на заданное время, отдав управление другим - это можно точнее, тут процесс снимается из очереди планировщика и не "мешает" обработке срабатывания таймера, по которому он просто возвращается обратно в очередь планировщика и если нет других ждущих процессов, то сразу получает управление, ему даже очередь сообщений проверять не надо.

-- 07.03.2026, 15:15 --

По идее правильнее было бы запускать отдельным потоком не таймер, а саму PARI функцию (factor или numdiv или что там), а основному процессу ждать завершения потока с timeout (под виндой что-то типа WaitForSingleObject в WinAPI) и получив управление обратно разбираться что произошло, таймаут или нормальное завершение потока вычислений. Но это несколько сложнее, надо передавать состояние PARI окружения в отдельный поток и потом аккуратно возвращать обратно.

[Yadryara]

Вроде кое-какой прогресс таки наквенил Правда, он меня заставил кучу всяких файлов создать.

Если число успевает разложиться, то прога ничего не пишет, а если не успевает, то пишет:
"Alarm clock".

yadryara@DESKTOP-QPP2F5P:~/TEST$ gp2c -g Test_2.gp > Test_2.gp.c
yadryara@DESKTOP-QPP2F5P:~/TEST$ gcc -o Test_2 Test_2.gp.c my_ualarm.c main.c -lpari
yadryara@DESKTOP-QPP2F5P:~/TEST$ ./Test_2
Alarm clock
yadryara@DESKTOP-QPP2F5P:~/TEST$

Но работает видно медленно что ли. Число 100000000000000000000002360000000000000000000002899 раскладывается за 296-297 ms, но в Квеновском варианте не успевает и за 310. За 315 — успевает.

То есть номинально вроде удалось перейти не к милли а сразу к микросекундам, но ещё тестить и тестить...