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

[Dmitriy40]

Странно, мне на 99 уровней загрязнения (или рекурсии) для диаметров до 2047 хватает общего массива 100*172*128=2.2МБ. И это я не стал его размещать в стеке, тогда не надо *100, разместил статически все 100 уровней вложенности. На предпросчитанные остатки по модулям надо ещё 1.3МБ. Остальные массивы считанные килобайты.
Наверное да, битовые команды исключают необходимость масок и экономят память ...

[Klein]

CPU: Intel i7-14700KF
Модель GPT-5.6 sol (ultra)
Размер массива ~170Kb (624 × 110 × 2 = 137 280 плюс overhead).

Цитата:
"
Для всех шести паттернов вида [0, 210, ..., 1260] реализован новый точный алгоритм AP210, вычисляющий слои A0–A4.
Для максимального паттерна медианное время расчета A0–A3 составляет 0,170 с на 28 потоках, а расчет A0–A4 занимает около 26,15 с. Запросы MAXN=5..99 отклоняются заранее, поскольку уже пятый слой содержит около 776 млрд подмножеств. Полный расчет при MAXN=90 остается исследовательской задачей, а результаты изучения PBMC, PBCount, DPMC и методов древесной декомпозиции приведены в AP210_RESEARCH.md."

Для имплементации использовались 4 относительно новые статиь опубликованные на с arxiv.org .

.\hl1-c-windows-x86_64.exe --threads 28 --ap210 --plain 4 0 210 420 630 840 1050 1260
[257619065666936663002818342572650555133360202322984936310291194163335589592017813775714218034098240993294470984737328882339087437917876471110103946648669695783051976138957239329425731377479805667736892117711811940188160000000000000000000000000000000000000, 27046008160589924746177826270503700764807412208442697045988581515368165897941535371839676358095914213362614858929592083584139263969840538837078794549284024520710594065866208122923891084591989803769194237874567808253575281089025502667188644409179687500000000, 1410056925676748203376725330172334235764876028751152438436366170915973019573428745057357466641668391466256514219747762123697354059482194864620801954050151196750808886499991911020369369129706261762604464476158718663958021025907113931571200000000000000000000000, 48674447267818670331437004428155957557304351000442479967832488191630832868593569408585193349078340395758665586835364986312298519112087867414040264894380840538405641171554054609458192021781823103812699562462174278095854794219934332098271571695610742256893677294, 1251504904391191564792766713763713646972427708572099280759469647577003141121848411575225735685419669563143014635618677857224298835312017282544691362982025979624369525201316378014548109196104739054569293016671833142940519795309823694489355113103097856000000000000]
Time: 26.649797100s

[Klein]

Помимо разработки алгоритма AP210 для вычисления слоев A0–A4, модель также в процессе оптимизировала общие алгоритмы, применяемые к другим паттернам и диапазонам слоев. (alderlake - Intel процессоры 12 поколения)


На восьми потоках

.\hl1-c-windows-alderlake.exe --threads 8 --tiled --plain 99 0 110
[1184794736150025000, 16859671669800960000, 113402284046134888374, 479392457805790470144, 1428494592766413777574, 3189625825866809747296, 5538154844652822968774, 7658726745848271141284, 8570498175790734960094, 7841767030108829207254, 5903388996261958758904, 3667314316625188105690, 1880008791392177707080, 793072342272734288602, 273708728311875469998, 76575512538913594328, 17135473474146656486, 3009387016149433986, 403835051230427806, 39837681078866066, 2726178673625610, 117941760127526, 2736937010836, 23930334360]
Time: 0.192155300s

.\hl1-c-windows-alderlake.exe --threads 8 --tiled --plain 99 0 120
[121559939928992565000, 1842791168403046400000, 13251192626877535865232, 60120149862456082280448, 193100115326644768426050, 467003757531892097439680, 883050949240082662516760, 1338106833191830983852644, 1652333656803286333838258, 1681717813884577438699078, 1421414585715742397221170, 1002185282912455416567124, 590572618054651960858606, 290755449375773214653056, 119276704995130069143352, 40565565192200362211424, 11348839754355911479646, 2582986309781505597484, 470985585196795618826, 67363083401090669050, 7336922561625575824, 583112370621265630, 31705508149667576, 1063095915085094, 18394436530972, 123864586560]
Time: 1.580745500s

.\hl1-c-windows-alderlake.exe --threads 8 --tiled --plain 99 0 128
[2689513670928960500625, 43177833345455226880000, 329689835733621529757745, 1592939415925724366241792, 5465931244308064600331668, 14171131688640743533408512, 28834815910410635247798180, 47215130740390443744367176, 63292669214262524867821641, 70292540991806725613305652, 65205616129239317245202789, 50787451060035369572768656, 33309135225983918652216886, 18409235736997835646559960, 8563442100194093954615362, 3342077285421926452294482, 1088514464572527981679868, 293593565515446717727920, 64883565054782942543074, 11581742339715310797890, 1637896596817616456928, 178746935978137889650, 14506248091842030276, 828847328685950690, 30539606179246778, 616812542484936, 4573930475520]
Time: 3.432091600s

[Yadryara]

Klein, Спасибо. Прошу обратить внимание модели на точность, о которой писал Дмитрий. И уж тем более не нужно столько знаков как здесь:

Klein в сообщении #1727767 писал(а):

.\hl1-c-windows-x86_64.exe --threads 28 --ap210 --plain 4 0 210 420 630 840 1050 1260
[257619065666936663002818342572650555133360202322984936310291194163335589592017813775714218034098240993294470984737328882339087437917876471110103946648669695783051976138957239329425731377479805667736892117711811940188160000000000000000000000000000000000000,

[Yadryara]

Чтобы лучше сориентироваться, вот табличка что уже посчитано и что считается:

Паттерн                 Посчитано констант
                                          
[0, 210]                                13
[0, 210, 420]                            9
[0, 210, 420, 630]                       7 *
[0, 210, 420, 630, 840]                  7
[0, 210, 420, 630, 840, 1050]            6 *
[0, 210, 420, 630, 840, 1050, 1260]      6 *

* — В работе очередная константа.

Результаты по паттернам длиной 4 и 6 могут быть уже сегодня, а вот когда 7-ка досчитается — непонятно.

То есть ваш расчёт

Klein в сообщении #1727767 писал(а):

.\hl1-c-windows-x86_64.exe --threads 28 --ap210 --plain 4 0 210 420 630 840 1050 1260

эквивалентен подсчёту 5 констант для 7-ки.

Желательно посчитать именно побольше констант, частично пожертвовав точностью.

[Yadryara]

А зачем нужны-то эти константы? Для прогнозирования.

Взглянем сюда:

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

Таблица разрешённых вариантов

Паттерн      Загрязняющих          К  о  н  с  т  а  н  т  ы
             0     1     2            С0        С1        С2
[0,  ]
    2        1                     1.320
    4        1                     1.320
    6        2     2               2.641     5.716
    8        1     2     1         1.320     5.716     4.151
   10        4     6     2         1.760     8.575     8.302

Как определить количество простых чисел в интервале от 0 до $x$? Например, вот так:

$$\int\limits_{2}^{x} \dfrac{dt}{\ln t}$$

Как определить количество пар простых близнецов или кузенов в интервале от 0 до $x$? Например, вот так:

$$\int\limits_{2}^{x} \dfrac{1.320}{\ln^2 t} \, dt$$

Как определить количество секс-пар в интервале от 0 до $x$? Например, вот так:

$$\int\limits_{2}^{x} \left( 2.641 - \dfrac{5.716}{\ln t} \right) \dfrac{dt}{\ln^2 t}$$

Как определить количество кортежей по паттерну [0, 8] в интервале от 0 до $x$? Например, вот так:

$$\int\limits_{2}^{x} \left( 1.320 - \dfrac{5.716}{\ln t} + \dfrac{4.151}{\ln^2 t} \right) \dfrac{dt}{\ln^3 t}$$

[wrest]

Я научился считать эти числа методом Монте-Карло :) Относительная погрешность держится вдоль чисел на уровне 0,01%-0,001% почти до конца, но на последних числах заметно подрастает. Ну и это около линейно по диаметру по времени, так что большие диаметры тоже норм. считает, вроде.

[Yadryara]

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

Я научился считать эти числа методом Монте-Карло :) Относительная погрешность держится вдоль чисел на уровне 0,01%-0,001% почти до конца, но на последних числах заметно подрастает.

И кто же у нас говорил что нужно излагать ясно?

Последние числа — это те которые в самых правых, самых загрязнённых столбцах? Они, как правило, и не колышат. Так что да, интересно, в студию эту Монтю вместо с Карлой

[wrest]

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

Последние числа — это те которые в самых правых, самых загрязнённых столбцах?

Я так и не понял как они называются, так что говорю "эти числа".

-- добавлено через 3 минуты --

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

Они, как правило, и не колышат. Так что да, интересно,

А ну раз не колышат, то и фиг с ними...

[Yadryara]

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

А ну раз не колышат, то и фиг с ними...

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

[wrest]

Yadryara
Ок, Монте-Карло насчитало для 99 0 252 такое:

(Оффтоп)

[1321225721343104387926978209495028347426570240, 37187595292673623400624098566740893326116913152, 509279972491940968756108741553620419119671148544, 4521930511307323612075296768632612818259294552064, 29266679083080517574188445884672050076617606692864, 147177885335623384451145421424646183153928033533952, 598625628396973163280609568965013752787762092703744, 2024078374535718483010669588107480970579688170717184, 5803360266396396044949194773834559713426434779250688, 14321920537991530351880192373099476713607184498294784, 30776563895893903888355407492208855250621830216548352, 58118576467190417027613562049839671939660664174280704, 97159210961941220340103382427556632879594689712357376, 144652611516266487844130828687165635461402123382554624, 192738695704344881130334332922797001309135047242022912, 230758757347687725150365451560781508169948288922943488, 249073067724130343832785342340684327914142352581591040, 243021044331048065924827829428621509791857717027012608, 214809475142875422580034274807577691629338659039215616, 172307126449763839686996132741405732024497035414601728, 125593645512063064544016541618295601741859700372144128, 83265532455822474023130597454362674743877089001209856, 50242651868466143628285572151046441432681418003054592, 27601635941306253038105176466679928598686421697429504, 13806210335914692047127657328951599017773072360931328, 6286332282371074342693071610920698676335270317522944, 2604333677334534067982147585720048347592187963244544, 980967040555676780749312858256444510091264584056832, 335612826404689723683247398599009731839579339620352, 104157920147287786776956920390024657130907607498752, 29275949304846886370916745823470107327211849646080, 7436973982688311655254360539938316261362512166912, 1702837457532727581661527778847100420629859401728, 350145206209687919341540801881000196181124448256, 64324551451044762766517086511947045774525726720, 10478498133651053742457109557661559528806678528, 1496864897297460743844121090650219874025996288, 184405217945809258166309316407897584744529920, 19100577097998070199923941488729383579418624, 1598987004741065085092263537325914019856384, 101390861855869822314742684758204594782208, 4320408108791951169546037565364889452544, 92485800494017304825530205431184490496]

Поскольку точных значений нет у меня - смотрите большие ли получились ошибки.

[Yadryara]

Первые 4 совершенно не совпадают:

C:\HL1\Asm>hl1-vc-time.exe 3 0 252
[1321225721343107573e27, 3718786307748430823e28, 5092876054967091042e29, 4522036825323027234e30]
Time: 9.345s

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

Паттерн                 Посчитано констант
                                          
[0, 210]                                13
[0, 210, 420]                            9
[0, 210, 420, 630]                       8
[0, 210, 420, 630, 840]                  7
[0, 210, 420, 630, 840, 1050]            6 *
[0, 210, 420, 630, 840, 1050, 1260]      6 *

* — в работе очередная константа.

[wrest]

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

Первые 4 совершенно не совпадают:

Ага, чета не то запостил. Перепостил сейчас, в тот же пост.

[Dmitriy40]

Дальше правильные:

>hl1-vc-time2.exe 6 0 252
[1321225721343107573e27, 3718786307748430823e28, 5092876054967091036e29, 4522036825323027101e30, 2926764440317507873e31, 1471843172901679649e32, 5986591883665824887e32]
Time: 79.717s

[wrest]

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

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

Это искусство неосвоено. Пока умею считать только что-то типа 99 0 X  где X<256