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

[Yadryara]

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

Если число несвободно от квадратов [..] вернуть ноль.

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

А самые первые, самые внешние проверки должны быть максимально простыми и быстрыми.

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

Сколько мегов понадобится для установки?

По поводу новой темы, это надо не столько с нами, сколько с Админом консультироваться. Есть вариант пока продолжать здесь.

[wrest]

P.S. Ну то есть в уже существующих в pari функциях логика должна быть такая (но не в такой последовательности).

omega_upto(n,m,s)={
if(s==0 && moebius(n)==0, return(0));
my(w=omega(n));
if(w>m, return(0));
return(w)
}

-- 30.11.2025, 13:13 --

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

Прошу проверить скорость работы вашей функции на приведённых примерах.

Как вы себе представляете проверку скорости "на приведённых числах"? Давайте готовый скрипт, я запущу...

-- 30.11.2025, 13:18 --

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

Сколько мегов понадобится для установки?

Понадобится ваше время (возможно несколько часов) и желание разбираться, в основном.
Мегов где-то 100-200. Скорее всего устанавливать будем отдельную копию pari в том же линуксе, т.е. у вас их окажется две.

[Yadryara]

Ну вот же вы засекали скорость:

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

Вот новая функция в сравнении с factor() на 50-значных числах
? for(i=1,10^3,omega_upto(10^50+random(10^7),4,0))
time = 33,433 ms.

Я привёл 42 числа. Могу ещё дать 420, например. Больше вроде не надо.

И я прошу:
Вы с ними поколдуете, проверите так и сяк, сколько времени займёт их проверка с выкидыванием квадратных и без выкидывания. Для 2-х, 3-х, 4-х множителей.

А я пока соображу как старую проверку в краткой форме записать. И тогда уже выложу скрипт.

[wrest]

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

Ещё вопрос, насколько долго идёт проверка бесквадратности, может она и не нужна.

Проверка идёт по найденным множителям. При s=0, если очередной найденный множитель кратный, проверка немедленно завершается и возвращается ноль. Если кратный множитель пока не найден но некратных множителей уже точно наберётся больше чем надо (нефакторизованный остаток составной), проверка завершается и возвращается ноль.

-- 30.11.2025, 13:31 --

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

Я привёл 42 числа. Могу ещё дать 420, например. Больше вроде не надо.

И я прошу:
Вы с ними поколдуете, проверите так и сяк, сколько времени займёт их проверка с выкидыванием квадратных и без выкидывания. Для 2-х, 3-х, 4-х множителей.

Ненене. Вы пишете скрипт, я его запускаю.
Как работает функция я дал выше в виде её записи стандартными функциями pari. Попробуйте, убедитесь что поняли как работает. Сделайте скрипт чтобы работал от 30 секунд до максимум 2 минут на вашей машине. Я его запущу в системе где нет новой функции omega_upto() как оптимизированной встроенной чтобы засечь контрольное время (т.е. как у вас) и где есть, чтобы посмотреть на разницу.

[Yadryara]

wrest
Подскажите пожалуйста, как назвать новую тему. Я создам пока в "Программировании".

[wrest]

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

Подскажите пожалуйста, как назвать новую тему.

Что-то вроде "Линукс: сборка исполняемого pari/gp из изменённого исходного кода"

[Dmitriy40]

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

Сначала одно число, для которого нужно 4 делителя, затем 3 числа, для которых нужно по 16 делителей. И наконец 17 чисел, для которых нужно по 8 делителей.

Оба комплекта чисел плохи как примеры на факторизацию: в каждом есть простые числа (10590660848462310667809465739916813508300432947 в первом и 12604882732247615298251370060880681098600668147, 420942280483222774338635734871711057096126209 во втором), что проверяется без факторизации намного быстрее и весь комплект отбрасывается (если я правильно понимаю).

-- 30.11.2025, 15:26 --

И из обоих комплектов условию на делители удовлетворяет лишь первое число второго комплекта.

[wrest]

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

Вроде всё работает. Теперь буду сам тестить и вас пока не напрягать

Ну что же,

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

Поздавлять будем вас если справитесь с установкой

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

Как я понимаю, скомпилировать свою функцию/программу при помощи gp2c, которая бы использовала новую omega_upto() пока не выйдет (это возможно, но будет отдельный квест), так что тестируете в интерпретаторе.

[Yadryara]

Только нужно ещё научиться запускать из консоли. Или как-то ещё запускать длинные файлы.

Я положил файл Test_1.gp в папку /home/pari. Но, например, вот такая команда не прокатила:

./gp Test_1.gp

Может не в ту папку положил.

[wrest]

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

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

Ага, очень информативно.

[Yadryara]

yadryara@DESKTOP-QPP2F5P:/home/pari$ ./gp Test_1.gp
Reading GPRC: /etc/gprc
GPRC Done.

GP/PARI CALCULATOR Version 2.18.1 (development 30566-7378c334ce)
amd64 running linux (x86-64/GMP-6.3.0 kernel) 64-bit version
compiled: Nov 30 2025, gcc version 13.3.0 (Ubuntu 13.3.0-6ubuntu2~24.04)
threading engine: pthread, nbthreads = 12
(readline v8.2 enabled, extended help enabled)

Copyright (C) 2000-2025 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?18 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 1048576, factorlimit = 1048576
*** error opening input file: `Test_1.gp'.
*** Break loop: type 'break' to go back to GP prompt
break>

[wrest]

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

*** error opening input file: `Test_1.gp'.
*** Break loop: type 'break' to go back to GP prompt
break>

Нет доступа. Что-то там у вас с этим не то
Дайте команду

ls -l | grep Test_1.gp

если там опять на этом файле будут одни чёрточки как тут было post1709097.html#p1709097
То и лечение такое же

sudo chmod 666 Test_1.gp

Ну и первой строчкой в Test_1.gp впишите (не забудьте)
install(omega_upto,GGG);

[Yadryara]

wrest
Да, чёрточки были, а потом после sudo chmod 666 заработало.

yadryara@DESKTOP-QPP2F5P:/home/pari$ ls -l | grep Test_1.gp
---------- 1 root root    350 Dec  1 02:43 Test_1.gp

Теперь буду более сложные тесты писать.

[Yadryara]

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

И из обоих комплектов условию на делители удовлетворяет лишь первое число второго комплекта.

Совершенно не согласен. У меня условию на делители удовлетворяют 11 чисел. Нумерация сквозная:

6.     numdiv = 8
11.    numdiv = 8
16.    numdiv = 8
18.    numdiv = 8
21.    numdiv = 8
25.    numdiv = 16
30.    numdiv = 8
32.    numdiv = 8
36.    numdiv = 8
39.    numdiv = 8
42.    numdiv = 8

А первое число второго комплекта это 22-е по сквозной нумерации. И оно не подходит, потому что имеет 16 делителей вместо 4-х требуемых.

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

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

А у Вас, кстати, регулярная ошибка:

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

Именно что ошибка. Ну не надо называть разные вещи одними и теми же словами. Видите к чему это привело.

[Dmitriy40]

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

Совершенно не согласен. У меня условию на делители удовлетворяют 11 чисел.

Согласен, у меня была ошибка в программе, сейчас тоже 11 чисел:

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

 1:    17406126303170342587707303078752980565139499:                      [487, 1; 923509, 1; 38701877783586051925130191104338953, 1], numdiv= 8
 2:   198368257307306547367919233421959045941111127:                         [11719757728380984539, 1; 16925969111710464773591093, 1], numdiv= 4
 3:    67864683258213453905507434431649214364331717:          [67, 1; 523, 1; 8975503, 1; 104857501130807, 1; 2057827822364809997, 1], numdiv=32
 4:    51231361266412682617729208094195819174793817:                     [97, 1; 2251, 1; 234632769245341967683225361897327736011, 1], numdiv= 8
 5:    27720211614413493095909609323615332724939333:                           [3314588639, 1; 8363092568487347999960851046534747, 1], numdiv= 4
 6:   329812967599172304533858794668689694030117289:                    [137, 1; 6037, 1; 398773219162092043751922505460475116381, 1], numdiv= 8 ----- OK
 7:    75557627931954653991506295409632438822595241:                          [199421143741849, 1; 378884738670259198613224171409, 1], numdiv= 4
 8:  6808281974011485429306085118517951541050278323:                        [4654175489, 1; 1462833103328967626150910941406909107, 1], numdiv= 4
 9:   105613238378017502504471126492245231661721769:              [1171, 1; 14249, 1; 1792379, 1; 3531402587813697913270819667809, 1], numdiv=16
10: 10590660848462310667809465739916813508300432947:                        Mat([10590660848462310667809465739916813508300432947, 1]), numdiv= 2
11:    37801287977854767404435927685604331380013443:                     [284003, 1; 483767, 1; 275136006958919345308672792453543, 1], numdiv= 8 ----- OK
12:  3812637905446431840411407666370052862988155861:        [71, 1; 20899, 1; 17310407, 1; 2759327374399853, 1; 53793672931796179, 1], numdiv=32
13:   353676985662934308015900525637296183950663809:               [77419, 1; 334349, 1; 1804110239, 1; 7573491515465084306720401, 1], numdiv=16
14: 15885991272693466001714198609875220262450649421:            [127033, 1; 2081387071, 1; 2468149204429, 1; 24342966562299916343, 1], numdiv=16
15:   563999690154797609528314743545865808134342583:                         [264833407169, 1; 2129639520118730831523264861439607, 1], numdiv= 4
16:  4236264339384924267123786295966725403320173179:                   [11418769, 1; 79869542899147, 1; 4644966280436340948116353, 1], numdiv= 8 ----- OK
17:  5957246727260049750642824478703207598418993533:                        [2885317120486609363127, 1; 2064676594805412164809579, 1], numdiv= 4
18:     3221384917659252615383854932127391438386667:                      [17989, 1; 41761, 1; 4288098073374302768160574623655823, 1], numdiv= 8 ----- OK
19:  9531594763616079601028519165925132157470389653:                        [127, 1; 75051927272567555913610387133268757145436139, 1], numdiv= 4
20:    34366665814372019473692154915900963250298863:          [1409, 1; 6907, 1; 263023, 1; 2988547728853, 1; 4492447676240712679, 1], numdiv=32
21:   787735104431080958762687534373977864253751211:                    [7789, 1; 137650077058000783667, 1; 734720295979783245997, 1], numdiv= 8 ----- OK

 1:    20716571327653129599025261239577452499526299:                [4231, 1; 504857, 1; 138051677, 1; 70252985569905925163151961, 1], numdiv=16
 2:   236095618293919953557257711858327013293248727:                     [947, 1; 790567, 1; 315354669535331595835223269430486123, 1], numdiv= 8
 3:    65178939724348484736720672535435868938469413:                     [315047, 1; 22019127413137, 1; 9395758347729939897244067, 1], numdiv= 8
 4:    60974976936430280937523424105308320283475417:               [461, 1; 3517, 1; 13894667, 1; 2706638207276384021097841759523, 1], numdiv=16 ----- OK
 5:    32992277036564937526323202136956850338056133:                           [8839, 1; 3732580273398001756570109982685467851347, 1], numdiv= 4
 6:   392539600658230234201599759681405293728048489:        [4027, 1; 254003, 1; 191875751, 1; 180609809477, 1; 11073924889326947, 1], numdiv=32
 7:    89927819730660751236038311968233158848518441:               [157, 1; 451337, 1; 7723020498649, 1; 164326000966105452385501, 1], numdiv=16
 8:  8103138899302038406018737896280437849100429523:                        [2380239978079, 1; 3404336946664415610967546341671437, 1], numdiv= 4
 9:   125699661595821094386994272075264409847541289:                    [186889, 1; 17113611006949297, 1; 39301462521710034552433, 1], numdiv= 8 ----- OK
10: 12604882732247615298251370060880681098600668147:                        Mat([12604882732247615298251370060880681098600668147, 1]), numdiv= 2
11:    44990658175779709571390969878217779055088643:                    [131, 1; 113274361, 1; 3031931813293654304774010974838473, 1], numdiv= 8 ----- OK
12:  4537757783609141507370493221917045195496240533:   [107, 1; 991, 1; 1286881, 1; 47126689, 1; 7786516971787, 1; 90622351337923, 1], numdiv=64
13:   420942280483222774338635734871711057096126209:                          Mat([420942280483222774338635734871711057096126209, 1]), numdiv= 2
14: 18907324098371422947377055091321021647901002221:                        [3003334931, 1; 6295443076698734986137000745762318591, 1], numdiv= 4
15:   671265944320878921208652843478852839570449783:                    [179, 1; 77237544849063895301, 1; 48552670618242319475977, 1], numdiv= 8 ----- OK
16:  5041953092899046119300548024352272439440267259:             [2927, 1; 3821, 1; 220673, 1; 2042912856995912223938158484927849, 1], numdiv=16
17:  7090246536889283605266395659245383117962875833:             [3361, 1; 21503, 1; 75527680379, 1; 1298935607682155301947038469, 1], numdiv=16
18:     6041804627605173364805066468613752823338003:                     [2335147, 1; 138026354821, 1; 18745215333703532648952869, 1], numdiv= 8 ----- OK
19: 11344394459022853768426233054792612988740601333:            [103, 1; 19853, 1; 36720349, 1; 151081452531966683005615511961563, 1], numdiv=16
20:    26923921820393624702566116185576392521040943:          [1049, 1; 29423, 1; 2802131, 1; 9774765113, 1; 31847923103524490603, 1], numdiv=32
21:   937553261076268906481506864032447354441372011:                    [67, 1; 984587, 1; 14212387787843720434421512867868992459, 1], numdiv= 8 ----- OK