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

[Yadryara]

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

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

Да, и для более быстрой работы заметно отставание:

Число 100000000000000001380000000000000004437 в программе Test_1.gp раскладывается за 17 ms, в программе Test_2.gp то успевает, то не успевает за 20.

Test_1.gp

/*
GP;init_Test_1();
*/                  
/*                      
GP;quit;                
*/                      
{t0=getwalltime(); print; t3=getwalltime();
if( type(kfnew = alarm(1,factor(100000000000000001380000000000000004437))) <> "t_ERROR",
print(strtime(getwalltime()-t3) , "   ", kfnew[1] , "   ", kfnew[2]) ;
);
print;print("                               ",strtime(getwalltime()-t0));print;
}

Несколько раз проверял на пустом компе. 5 раз подряд показывал одно и то же время факторизации:

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

17 ms   [10000000000000000051, 10000000000000000087]~   [1, 1]~

                               17 ms

Test_2.gp

#install(my_ualarm, GG, my_ualarm)

{
    my_ualarm(20000, 0);
    factor(100000000000000001380000000000000004437);
    my_ualarm(0, 0);
}

Здесь пока не разобрался что означает второй параметр в my_ualarm.

[wrest]

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

Здесь пока не разобрался что означает второй параметр в my_ualarm.

Видимо, интервал повторения таймера. Если ноль - то не повторять.

-- 08.03.2026, 10:47 --

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

#install(my_ualarm, GG, my_ualarm)

Это довольно странно выглядит. Должно бы быть vLL, по идее.

[wrest]

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

Но вас это (стабильность/переносимость) вряд ли волнует, верно?

[Dmitriy40]

Yadryara
Если factor() запустит алгоритм ECM, то время факторизации будет зависеть в том числе от того какое это число по счёту после запуска PARI - так как ECM использует случайные числа и в зависимости от них может быстрее или медленнее находить простые делители. Пруф:

? x=nextprime(10^30-random(10^29))*nextprime(10^30-random(10^29))
%1 = 909165008476014999590146574242966924037355637363444071390071
? setrand(50)
? random()
%2 = 1041444962
? random()
%3 = 423238409
? setrand(50)
? random()
%4 = 1041444962
? setrand(50)
? factor(x)
  *** factor: Warning: increasing stack size to 16000000.
time = 7,520 ms.
%6 =
[913676242697998258643647795217 1]

[995062546215865242001070144263 1]

? random()
%7 = 2049990632

Видим что после factor состояние ГСЧ изменилось.

А после Вашего числа состояние ГСЧ не меняется - и значит делители найдены не методом ECM:

? setrand(50)
? factor(100000000000000001380000000000000004437)
time = 78 ms.
%2 =
[10000000000000000051 1]

[10000000000000000087 1]

? random()
%3 = 1041444962

И в общем да, столь близкие делители находятся методом Ферма или его модификациями. С реальными числами это мало соотносится, лучше использовать достаточно разные простые в разложении, например как я выше.

[Yadryara]

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

Это довольно странно выглядит. Должно бы быть vLL, по идее.

Я-то в этом ничего не понимаю. Но, пока работает, не трогаю.

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

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

Не знаю как это сделать. И так ли уж нужно.

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

Но вас это (стабильность/переносимость) вряд ли волнует, верно?

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

Файлы у меня такие:

main.c

#include <pari/pari.h>

/* Объявление функции из сгенерированного файла */
extern void init_Test_2(void);

int main(int argc, char **argv) {
    pari_init(100000000, 2);  /* Инициализация PARI: память, размер стека */
    init_Test_2();            /* Вызов вашего кода */
    pari_close();             /* Завершение работы PARI */
    return 0;
}

my_ualarm.c

#include <pari/pari.h>
#include <unistd.h>

/* Обёртка с уникальным именем */
GEN my_ualarm(GEN gusec, GEN ginterval) {
    long usec = gtos(gusec);      /* Конвертация PARI -> C */
    long interval = gtos(ginterval);
    ualarm((useconds_t)usec, (useconds_t)interval);
    return gen_0;
}

Test_2.gp.c

/*-*- compile-command: "cc -c -o Test_2.gp.o -g -O3 -Wall -fomit-frame-pointer -fno-strict-aliasing -fPIC -I\"/usr/include/x86_64-linux-gnu\" Test_2.gp.c && cc -o Test_2.gp.so -shared -g -O3 -Wall -fomit-frame-pointer -fno-strict-aliasing -fPIC -Wl,-shared -Wl,-z,relro Test_2.gp.o -lc -lm -L/usr/lib/x86_64-linux-gnu -lpari"; -*-*/
#include <pari/pari.h>
/*
GP;install("my_ualarm","GG","my_ualarm");
GP;install("init_Test_2","v","init_Test_2","./Test_2.gp.so");
*/
void init_Test_2(void);
extern GEN my_ualarm(GEN, GEN);
/*End of prototype*/

void
init_Test_2(void)     /* void */
{
  pari_sp ltop = avma;
  glength(gen_0);
  my_ualarm(stoi(2600), gen_0);
  Z_factor(readseq("10000000000009800000000002077"));
  my_ualarm(gen_0, gen_0);
  avma = ltop;
  return;
}

И довольно большой файл 17КБ Test_2 в непонятной кодировке.

А вот файлов .o .so и .run вообще нету. Но работает как-то. Пока не знаю как привести к привычному состоянию.

[Yadryara]

Тут проблема обнаружилась. Я так понял что эта функция my_ualarm гарантированно возвращает 0, независимо от того есть Alarm clock или нет.

То есть пока непонятно как строить дальнейшую работу в зависимости от того есть Alarm clock или нет.

[wrest]

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

Тут проблема обнаружилась. Я так понял что эта функция my_ualarm гарантированно возвращает 0, независимо от того есть Alarm clock или нет.

Ну да, так она написана. Но вообще ualarm() видимо не вполне правильный подход. Лучше было бы setitimer() как мне предлагал Qwen. У ualarm() есть пара проблем
-- это устаревшая функция
-- она не поддерживает длительности больше 1 секунды

[Yadryara]

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

Лучше было бы setitimer() как мне предлагал Qwen.

Хорошо, я переделаю. Что конкретно нужно изменить в файлах?

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

-- она не поддерживает длительности больше 1 секунды

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

[wrest]

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

Хорошо, я переделаю. Что конкретно нужно изменить в файлах?

Ну это общая идея. Что конкретно - спросите у Квена.

[Yadryara]

Да, Квен в качестве программиста всё растёт в моих глазах.

Теперича, поправив С-код и .gp-код, добился удобного вывода.

Когда не успевает:

ТАЙМ-АУТ! (лимит 100000 mks, потрачено 100084 mks)

Когда успевает:

Лимит 120000 mks
Фaкторизация завершена за 113925 mks
83249599403652415669870228237450726343942320967741813929973
Найдено 5 факторов:
[70199, 1; 624060433, 1; 937475263, 1; 253201399905476699, 1; 8005687975704882887, 1]

-- 09.03.2026, 07:27 --

И ещё есть сверхзадача: прервать факторизацию, как только третий фактор найден.

[Yadryara]

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

Для чего нужен специалист,

Я, кстати, думал что вы и есть специалист.

Квен писал(а):

Но мы можем написать свою функцию, которая ищет факторы по одному через Z_smallest_factor() и прерывает, когда найдено 3.

Вот это пока откладывается. Доступ на сегодня закончен.

Так что нужно попробовать извлечь хоть какую-то пользу из успешного тестирования применения setitimer. То есть нужно как-то интегрировать простенький файл Test_5.gp и нашу весьма немаленькую программу .gp , которая запускается совершенно по-другому.

Вот Test_5.gp :

#install(gp_safe_factor, GG, safe_factor)

{
\\  my(n = 10000000000000000000000000069800000000000000000000000120901);

    my(n = 83249599403652415669870228237450726343942320967741813929973);
    my(limit = 110000);
    my(res = safe_factor(n, limit));
    my(status  = res[1]);
    my(elapsed = res[2]);
    my(factors = res[3]);

    if (status == -1,
        print("ТАЙМ-АУТ! (лимит ", limit, " mks, потрачено ", elapsed, " mks)");
    ,
        my(nfactors = matsize(factors)[1]);

        print("Лимит ", limit, " mks");
        print("Фaкторизация завершена за ", elapsed, " mks");
        print(n);
        print("Найдено ", nfactors, " факторов:");
        print(factors);
    );
}

Ещё у меня два файла timer_wrapper_5.c и main.c. И вот такими командами из Убунты я запускаю:

yadryara@DESKTOP-QPP2F5P:~/Test5$ gp2c -g Test_5.gp > Test_5.gp.c
yadryara@DESKTOP-QPP2F5P:~/Test5$ gcc -o Test_5 Test_5.gp.c timer_wrapper_5.c main.c -lpari
yadryara@DESKTOP-QPP2F5P:~/Test5$ ./Test_5
ТАЙМ-АУТ! (лимит 110000 mks, потрачено 110529 mks)
yadryara@DESKTOP-QPP2F5P:~/Test5$ ./Test_5
ТАЙМ-АУТ! (лимит 110000 mks, потрачено 110428 mks)
yadryara@DESKTOP-QPP2F5P:~/Test5$ ./Test_5
ТАЙМ-АУТ! (лимит 110000 mks, потрачено 110143 mks)
yadryara@DESKTOP-QPP2F5P:~/Test5$ ./Test_5
ТАЙМ-АУТ! (лимит 110000 mks, потрачено 110511 mks)
yadryara@DESKTOP-QPP2F5P:~/Test5$ ./Test_5
ТАЙМ-АУТ! (лимит 110000 mks, потрачено 110077 mks)
yadryara@DESKTOP-QPP2F5P:~/Test5$

Здесь видно, что запаздывание порой превышает 500 микросекунд.

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

yadryara@DESKTOP-QPP2F5P:~/D96-20/0-0-10-10-0-9!$ gp2c-run -g  Rab_243_20_0_test_3.gp

Ну и файлы у меня в папке запуска другие.

То есть нужно либо в рабочую прогу Rab_243_20_0_test_3.gp встраивать Test_5.gp либо наоборот, в Test_5.gp встраивать длиннющую рабочую прогу. Второй вариант конечно не хочется делать.

[Yadryara]

Ко второму варианту склоняюсь. Потому что, как понимаю, вот тот самый в итоге запускаемый файл, Test_5, который без расширения, это что-то типа экзешника, только для Линукса. Старым способом такой файл не создаётся.

А вот здесь посмотрите, плиз, timer_wrapper_5.c , кто в С разбирается. Часть я закоментил, но нет ли здесь ещё чего-нибудь лишнего? Четырежды встречается 1000000, это прям так надо или Квен перестарался?

#include <pari/pari.h>
#include <sys/time.h>
#include <signal.h>
#include <setjmp.h>
#include <stdio.h>

static jmp_buf timeout_env;
static volatile sig_atomic_t timeout_flag = 0;

void timeout_handler(int sig) {
    timeout_flag = 1;
    longjmp(timeout_env, 1);
}

GEN gp_safe_factor(GEN n, GEN gusec) {
    struct itimerval timer, old_timer;
    struct sigaction sa, old_sa;
    struct timeval start, end;
    GEN result = NULL;
    long usec = gtos(gusec);
    long elapsed_usec = 0;

    sa.sa_handler = timeout_handler;
    sa.sa_flags = 0;
    sigemptyset(&sa.sa_mask);
    sigaction(SIGALRM, &sa, &old_sa);

    timer.it_value.tv_sec = usec / 1000000;
    timer.it_value.tv_usec = usec % 1000000;
    timer.it_interval.tv_sec = 0;
    timer.it_interval.tv_usec = 0;

    if (setjmp(timeout_env) == 0) {
        gettimeofday(&start, NULL);
/*        fprintf(stderr, "[DEBUG] Запуск таймера на %ld мкс\n", usec); */
/*        fprintf(stderr, "[DEBUG] Запуск factor()\n");                 */
        
        setitimer(ITIMER_REAL, &timer, &old_timer);
        result = Z_factor(n);
        setitimer(ITIMER_REAL, &old_timer, NULL);
        
        gettimeofday(&end, NULL);
        elapsed_usec = (end.tv_sec - start.tv_sec) * 1000000 + 
                       (end.tv_usec - start.tv_usec);
        
/*        fprintf(stderr, "[DEBUG] Фaкторизация завершена за %ld mks\n", elapsed_usec); */
    } else {
        gettimeofday(&end, NULL);
        elapsed_usec = (end.tv_sec - start.tv_sec) * 1000000 + 
                       (end.tv_usec - start.tv_usec);
/*         fprintf(stderr, "[DEBUG] Тайм-аут сработал через %ld мкс!\n", elapsed_usec); */
    }

    sigaction(SIGALRM, &old_sa, NULL);

    /* Возвращаем массив: [статус, время, результат] */
    /* статус: 0 = успех, -1 = тайм-аут */
    GEN res = cgetg(4, t_VEC);
    gel(res, 1) = stoi(timeout_flag ? -1 : 0);
    gel(res, 2) = stoi(elapsed_usec);
    gel(res, 3) = timeout_flag ? gen_0 : result;
    
    timeout_flag = 0;
    return res;
}

[wrest]

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

Я, кстати, думал что вы и есть специалист.

Не, я детально в линуксе, и в Си, не разбираюсь.

-- 09.03.2026, 13:07 --

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

Когда не успевает:

Код:

ТАЙМ-АУТ! (лимит 100000 mks, потрачено 100084 mks)

Непонятно, вычисления-то прерываются когда не успевает? Дайте какое-нибудь число секунд на 5 факторизации...

[Yadryara]

Я кстати уже начал внедрять рабочую программу в нововведение. Да, именно так

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

Ну вот как он 10 чисел факторизует. По 5 чисел по двум паттернам:

(Оффтоп)

1

Лимит 300000 mks
Фaкторизация завершена за 120627 mks
6075464189284607781796135983145758248084558425096411125
Найдено 6 факторов:
[3, 1; 5, 3; 19, 1; 98057, 1; 762651346311797399, 1; 11402234099985224890319290639, 1]

2

Лимит 300000 mks
Фaкторизация завершена за 21611 mks
12571092077295037109854845851965645773741657922368628725
Найдено 7 факторов:
[3, 1; 5, 2; 19, 1; 1697, 1; 11701, 1; 16467641903, 1; 26978755166885501125375295133179327, 1]

3

Лимит 300000 mks
Фaкторизация завершена за 84919 mks
19066719965305466437913555720785533299398757419640846325
Найдено 8 факторов:
[3, 1; 5, 2; 19, 1; 101, 1; 409, 1; 15401, 1; 47515624534661497, 1; 442620046215601762498110473, 1]

4

Лимит 300000 mks
Фaкторизация завершена за 125 mks
25562347853315895765972265589605420825055856916913063925
Найдено 4 факторов:
[3, 1; 5, 2; 19, 1; 17938489721625190011208607431302049701793583801342501, 1]

5

Лимит 300000 mks
Фaкторизация завершена за 17470 mks
32057975741326325094030975458425308350712956414185281525
Найдено 9 факторов:
[3, 1; 5, 2; 19, 1; 283, 1; 461, 1; 1009, 1; 1521973, 1; 43585749388084291, 1; 2576269185415375609333, 1]

1

Лимит 300000 mks
Фaкторизация завершена за 90231 mks
3662984981514261005523078493930177592270423952388007925
Найдено 6 факторов:
[3, 1; 5, 2; 19, 1; 3689297, 1; 2360682169373637173, 1; 295147517865880761213848801, 1]

2

ТАЙМ-АУТ! (лимит 300000 mks, потрачено 300388 mks)

3

Лимит 300000 mks
Фaкторизация завершена за 323303 mks
16654240757535119661640498231569952643584622946932443125
Найдено 5 факторов:
[3, 1; 5, 4; 19, 1; 3702679491756928676452391, 1; 126256528792561308579701707, 1]

4

Лимит 300000 mks
Фaкторизация завершена за 485053 mks
23149868645545548989699208100389840169241722444204660725
Найдено 5 факторов:
[3, 1; 5, 2; 19, 1; 2135394489377489691103, 1; 7607738025613753279753662258299, 1]

5

Лимит 300000 mks
Фaкторизация завершена за 387853 mks
29645496533555978317757917969209727694898821941476878325
Найдено 6 факторов:
[3, 1; 5, 2; 19, 1; 157, 1; 779982083709089, 1; 169886780041346531536604122618447753, 1]

[wrest]

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

Лимит 300000 mks
Фaкторизация завершена за 387853 mks

Чёт я не понял, если это просто таймер, который считает сколько длилась факторизация, а не прерывает её, зачем он вам?