кортежи последовательных простых. ключ к 19-252

[Yadryara]

Я тоже 53# для 19-252 посмотрел.

И, чтобы одно и тоже с Вами не считать, решил попробовать 11-156. И, несмотря на ускорение в десятки раз по сравнению с версией от конца марта, уже 53# очень долго считается, а идти надо до 73#

Время считается нарастающим итогом:

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]

cg  o = 1 --> 53#: [0, 0, 346, 52098, 2422270, 53269464, 676038228, 5518432022,
31042023092, 125945754432, 377124103914, 835316590502, 1352829251706, 1573561804
962, 1290179936268, 734028919188, 287186981548, 77441625286, 14636196348, 197261
6318, 183542808, 9139200], sum=6707708700000, #ww[]=1108+256923, time : 1h, 11mi
n, 19,740 ms

cg  o = 2 --> 53#: [0, 0, 0, 2594, 218448, 7663836, 143503484, 1630237650, 12120
974500, 61544654988, 217837600988, 540074213820, 933178997114, 1113110186592, 90
7282170970, 502045567388, 189869011998, 50901584284, 10339571050, 1627087816, 17
4413280, 9139200], sum=4541896800000, #ww[]=636+286801, time : 1h, 46min, 36,967
 ms

Это для pmid=19. А вот для pmid=23:

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]

cg  o = 1 --> 53#: [0, 0, 346, 52098, 2422270, 53269464, 676038228, 5518432022,
31042023092, 125945754432, 377124103914, 835316590502, 1352829251706, 1573561804
962, 1290179936268, 734028919188, 287186981548, 77441625286, 14636196348, 197261
6318, 183542808, 9139200], sum=6707708700000, #ww[]=9443+69428, time : 1h, 35min
, 36,314 ms

cg  o = 2 --> 53#: [0, 0, 0, 2594, 218448, 7663836, 143503484, 1630237650, 12120
974500, 61544654988, 217837600988, 540074213820, 933178997114, 1113110186592, 90
7282170970, 502045567388, 189869011998, 50901584284, 10339571050, 1627087816, 17
4413280, 9139200], sum=4541896800000, #ww[]=5778+76085, time : 2h, 41min, 24,539
 ms

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

таблица по 31# как и на PARI и потом перебор 31#->53#,

Опечатка? Разве не 41# должно быть оба раза ?

[Dmitriy40]

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

Опечатка? Разве не 41# должно быть оба раза ?

Нет, pmid=31, т.е. при расчёте паттернов первая таблица wm[] строится по 31#, а всё дальше считается или второй таблицей ww[] (в PARI), или перебором всех вариантов комбинаций (в асме), второе кстати по идее дольше (это как та предыдущая программа с Calc() вместо использования Map).
Все запуски разумеется от уже известных vc[] для расчёта только одного следующего (и лишь одна итерация первого цикла, т.е. всего один паттерн длиной 20 для каждого целевого простого).

[Yadryara]

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

Нет, pmid=31

А, этот новый pmid. Я-то имел в виду, что формула работает только начиная с перехода через $\frac16$ диаметра, то бишь с перехода $41\#\to43\#$. А широкая вилка $4p$ перестаёт работать начиная с перехода через $\frac14$ диаметра, то бишь с $61\#\to67\#$. Если будете считать выше $\frac14$, не забудьте.

Похоже, что 11-156 если и поддастся обсчёту, то только на асме. $53\#$ закончил, а вот для $59\#$ при pmid=23 :

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]

cg  o = 1 --> 59#: [0, 222, 82090, 6543412, 225750128, 4311178206, 51441210230,
411263227556, 2295438598960, 9145751387246, 26291207853468, 54681452438522, 8195
0035872968, 87642969023972, 66012653678284, 34565516579420, 12497036765212, 3142
067593058, 562073176280, 72449877794, 6314782812, 276380160], sum=37933249200000
0, #ww[]=12494+264522, time : 7h, 8min, 41,733 ms

-- 21.05.2024, 06:12 --

Впрочем, хорошие новости, 2-я часть cg посчиталась гораздо быстрее:

cg  o = 2 --> 59#: [48, 17332, 1570178, 59004208, 1155474144, 13635619100, 10626
2199670, 577311718890, 2264830161040, 6576484861006, 14311826435652, 23314255857
862, 28104334710978, 24611612418472, 15278437258924, 6508642740932, 181488839938
6, 306282682574, 27042674212, 868483392], sum=123817932288000, #ww[]=3559+123953
, time : 8h, 43min, 19,801 ms

[Dmitriy40]

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

Я-то имел в виду, что формула работает только начиная с перехода через $\frac16$ диаметра, то бишь с перехода $41\#\to43\#$. А широкая вилка $4p$ перестаёт работать начиная с перехода через $\frac14$ диаметра, то бишь с $61\#\to67\#$. Если будете считать выше $\frac14$, не забудьте.

Да, это помню. Но меня пока не интересовала корректность, в ней уже убедились (хоть бы и по правым элементам, да и 43# и 47# совпали же), меня интересовала скорость.

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

Впрочем, хорошие новости, 2-я часть cg посчиталась гораздо быстрее:

Не, 7ч на итерацию это за гранью разумного. Попробуйте поиграться с pmid, может слишком его увеличили. А чтобы не ждать часами каждый раз сделайте проход по первой таблице неполным, например перед foreach(wm[kk],mm, обнулите счётчик cnt=0;, а сразу после него командой if(cnt++>#wm[kk]/100, break); оборвите перебор достаточно рано (примерно на 1% размера для каждого kk, которое по смыслу и k, т.е .величина загрязнения и индекс в vc[]). Числа будут неверные, зато для теста скорости при разных pmid неплохо, но скорость будет с небольшой ошибкой (не все размеры разделятся на 100 корректно, особенно малые, до 100 вообще обсчитываться не будут, но малые размеры и на общее время влияют слабо, т.е .время будет чуть заниженным, но если от pmid оно будет меняться на десятки процентов и более, то можно и пренебречь).

[Yadryara]

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

Не, 7ч на итерацию это за гранью разумного. Попробуйте поиграться с pmid, может слишком его увеличили.

Спасибо, хотя вряд ли. Всё ж таки уже 4-я, последняя часть cg обсчитывается. А части g2 традиционно в разы быстрее считаются. К вечеру посчитает.

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

А чтобы не ждать часами каждый раз сделайте проход по первой таблице неполным, например перед foreach(wm[kk],mm, обнулите счётчик cnt=0;, а сразу после него командой if(cnt++>#wm[kk]/100, break); оборвите перебор достаточно рано

Спасибо, попробую.

[Dmitriy40]

Решил проверить свою идею что вторая таблица заметно ускоряет расчёт по сравнению с асм прогой, в которой вместо второй таблицы обсчёт ведётся фактически функцией Calc() из мартовской проги на PARI. Заменил в последней проге вторую таблицу на вызов Calc(), запустил ... Вышло более чем вдвое медленнее. Так что асм ускоряет не в 130 раз, а скорее в 250 раз, да ещё и плюс многопоточность ускоряет линейно. И если на нём сделать именно обсчёт именно второй таблицей возможно будет ещё вдвое быстрее текущего (а может и более чем вдвое, операции с Map на асме явно сильно быстрее чем в PARI).

[Yadryara]

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

в которой вместо второй таблицы

Вторая таблица это попросту вторая часть обсчёта с forprime(p=pmid+1,pfin, ?

Деление на 3 части не пробовали?

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

Всё ж таки уже 4-я, последняя часть cg обсчитывается. А части g2 традиционно в разы быстрее считаются. К вечеру посчитает.

Быстрее. Ещё даже полчетвёртого не было. Оказалась допустимой всего одна часть g2, которая и была посчитана за час. Это про 59#.

Эксперименты с изменением pmid для 1% для 61# :

(pmid = 17)

Очень мне не понравились нулевые результаты и я их не сохранил.

(pmid = 19)

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]


cg  o = 1 --> 61#: [0, 0, 2592, 300212, 14882038, 410635166, 6611137936, 6420129
1932, 390992735360, 1549798244042, 4126111097366, 7549153760550, 9580923611458,
8349004930214, 4821249980534, 1724058247552, 339125962248, 28106956800], sum=385
29763776000, #ww[]=609+104847, time : 26,967 ms

cg  o = 2 --> 61#: [0, 0, 1176, 287484, 21042110, 681954056, 11847710904, 123065
447484, 817810687042, 3636903999694, 11166189249798, 24129116421930, 36860148741
018, 39229724795002, 28087881534510, 12804622175102, 3431064075090, 474652483200
, 25131254400], sum=160798861860000, #ww[]=1105+193187, time : 2min, 4,289 ms

cg  o = 3 --> 61#: [0], sum=0, #ww[]=189+0, time : 2min, 4,289 ms


24  cg = [0, 0, 0, 3768, 587696, 35924148, 1092589222, 18458848840, 187266739416
, 1208803422402, 5186702243736, 15292300347164, 31678270182480, 46441072352476,
47578729725216, 32909131515044, 14528680422654, 3770190037338, 502759440000, 251
31254400, 0, 0, 0, 0]    199328625636000

time: 2min, 4,304 ms




6  do = [2, 8, 10, 12, 14, 16]

g2  o = 1 --> 61#: [0], sum=0, #ww[]=0+0, time : 0 ms

g2  o = 2 --> 61#: [0], sum=0, #ww[]=0+0, time : 16 ms

g2  o = 3 --> 61#: [0, 0, 2976, 317200, 14960326, 414603938, 7150492584, 7785669
6976, 541904381244, 2446315672330, 7254091994174, 14223241236686, 18385539219222
, 15425074647334, 8128057111360, 2533675012224, 416754224226, 27334195200], sum=
69467424768000, #ww[]=512+95718, time : 33,928 ms

g2  o = 4 --> 61#: [0], sum=0, #ww[]=0+0, time : 33,937 ms

g2  o = 5 --> 61#: [0], sum=0, #ww[]=0+0, time : 33,942 ms

g2  o = 6 --> 61#: [0, 0, 1872, 564390, 41094846, 1277548086, 20409812454, 18599
8343256, 1034799801798, 3672828518064, 8544194466402, 13184183166114, 1339506686
2626, 8654190999324, 3311718960528, 661841049744, 52010090496], sum=527185612800
00, #ww[]=402+56487, time : 46,384 ms


25  g2 = [0, 0, 0, 0, 4848, 881590, 56055172, 1692152024, 27560305038, 263855040
232, 1576704183042, 6119144190394, 15798286460576, 27407424402800, 3178060608184
8, 24079265646658, 11439776071888, 3195516061968, 468764314722, 27334195200, 0,
0, 0, 0, 0]    122185986048000

time: 46,393 ms


vc  -->  61# : [111640, 31625712, 2665076454, 102715972092, 2215165565386, 30151
792566126, 279846566871920, 1860208198174708, 9120897605779606, 3349113551356411
2, 92511252557449270, 191678640868047274, 295683402187707676, 336176409851755598
, 278459582849680032, 166044741960622736, 70553546580226010, 21264695637682614,
4573189967035162, 711917801388152, 79915508989812, 5963112053508, 219364454400,
0]      1502528038502400000


time: 2min, 50,703 ms

Нулевой результат в 3-й части cg — неправильный. Там далеко не нули.

(pmid = 23)

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]


cg  o = 1 --> 61#: [0, 0, 147108, 17337976, 698848248, 13793727228, 157005608376
, 1130414673834, 5426451462880, 17868941510736, 41080363191118, 66995974092520,
78624579314504, 66524536627314, 39541154760250, 15533593121260, 3705712693816, 4
98929234832, 33266688000], sum=337135433040000, #ww[]=5512+122282, time : 2min,
50,657 ms

cg  o = 2 --> 61#: [0, 200, 88334, 7766616, 307878930, 6876919418, 93484615216,
810829854868, 4662231561546, 18266444296804, 49625967622080, 94522468835180, 126
834378083418, 119187068019254, 76661500960140, 32370724826244, 8481384687892, 12
85401481452, 94842897408], sum=532903920395000, #ww[]=10272+141682, time : 10min
, 16,978 ms

Запустил 61# с pmid = 19. Как и ожидал, длина ww[] превысила миллион, но время хорошее. Видимо, 61# посчитается быстрее чем 59#.

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]


cg  o = 1 --> 61#: [2894, 1129150, 102116542, 3822102252, 75610880780, 906529144
060, 7171446933568, 39537571328190, 157185431641358, 459025441602110, 9918012344
09586, 1585976304644902, 1868767176065862, 1608166568646582, 996920281971314, 43
7839109065888, 134587428052770, 29196788973602, 4663285643946, 559567314888, 438
36940956, 1437004800], sum=8322428975616000, #ww[]=609+1134260, time : 3h, 20min
, 51,961 ms

cg  o = 2 --> 61#: [694, 351940, 40016650, 1824585098, 42906637870, 600898727284
, 5497141704362, 34949197073574, 160573587231950, 543477952437388, 1359880823341
284, 2500412046211962, 3343171338551826, 3211145606393732, 2188257252894326, 104
6603036735858, 349836781271810, 82540276181028, 14079492880192, 1747528231932, 1
47735099240, 6397440000], sum=14842971864000000, #ww[]=1105+1233474, time : 8h,
53min, 43,191 ms

[Yadryara]

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

Видимо, 61# посчитается быстрее чем 59#.

Да, быстрее: 13 часов против 18-ти. Но загадывать наперёд поостерегусь.

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

Как и ожидал, длина ww[] превысила миллион, но время хорошее.

В этом способе перераспределения памяти хорошо то, что эта самая длина ww[] не только не скачет как раньше, меняясь в разы, но и порой почти одинаковая: 1134260, 1233474, 1132106.

(Стата по 61#)

cg  o = 1 --> 61#: [2894, 1129150, 102116542, 3822102252, 75610880780, 906529144
060, 7171446933568, 39537571328190, 157185431641358, 459025441602110, 9918012344
09586, 1585976304644902, 1868767176065862, 1608166568646582, 996920281971314, 43
7839109065888, 134587428052770, 29196788973602, 4663285643946, 559567314888, 438
36940956, 1437004800], sum=8322428975616000, #ww[]=609+1134260, time : 3h, 20min
, 51,961 ms

cg  o = 2 --> 61#: [694, 351940, 40016650, 1824585098, 42906637870, 600898727284
, 5497141704362, 34949197073574, 160573587231950, 543477952437388, 1359880823341
284, 2500412046211962, 3343171338551826, 3211145606393732, 2188257252894326, 104
6603036735858, 349836781271810, 82540276181028, 14079492880192, 1747528231932, 1
47735099240, 6397440000], sum=14842971864000000, #ww[]=1105+1233474, time : 8h,
53min, 43,191 ms

cg  o = 3 --> 61#: [0, 72, 32328, 5132664, 307753102, 8889969656, 144968560820,
1470737589912, 9861837704692, 45355355863710, 146083716744674, 332608303480962,
536108462892618, 609675055380568, 486507916996600, 270995670313310, 104972284453
596, 28111723016138, 5107087328566, 605981583600, 43986837612, 1437004800], sum=
2577663728640000, #ww[]=189+1132106, time : 10h, 21min, 35,495 ms


24  cg = [0, 3588, 1481162, 142165520, 5651820014, 118825271752, 1516317841000,
12813557198750, 75957505991676, 327620856578000, 1047858749903208, 2497765774495
544, 4418996654337826, 5748046977510306, 5428987230420882, 3671685451862240, 175
5437816115056, 589396493778176, 139848788170768, 23849865852704, 2913077130420,
235558877808, 9271449600, 0]    25743064568256000

time: 10h, 21min, 35,497 ms




6  do = [2, 8, 10, 12, 14, 16]

g2  o = 1 --> 61#: [0], sum=0, #ww[]=0+0, time : 5 ms

g2  o = 2 --> 61#: [0], sum=0, #ww[]=0+0, time : 9 ms

g2  o = 3 --> 61#: [0, 484, 581234, 69083542, 3185805828, 76177957004, 106712328
8052, 9337730704888, 53083234699446, 201157037507994, 516523017078332, 906736915
239244, 1091201532845794, 898996619903474, 506255018748958, 195981147496634, 533
10218617144, 10530390187096, 1507940691612, 141427275240, 6397440000], sum=44459
15185152000, #ww[]=512+557886, time : 1h, 35min, 388 ms

g2  o = 4 --> 61#: [0], sum=0, #ww[]=0+0, time : 1h, 35min, 405 ms

g2  o = 5 --> 61#: [0], sum=0, #ww[]=0+0, time : 1h, 35min, 408 ms

g2  o = 6 --> 61#: [0, 42888, 10298546, 738036436, 23455908706, 396121189886, 39
53733630742, 25030747106308, 105649308254630, 307817300043430, 632536867312338,
925235250780424, 962782860787094, 708416925389496, 366751404788612, 134365645901
998, 35871844026192, 7351209399182, 1169021435372, 126060627720, 6397440000], su
m=4217484902400000, #ww[]=402+646791, time : 2h, 44min, 15,617 ms


25  g2 = [0, 0, 0, 43372, 10879780, 807119978, 26641714534, 472299146890, 502085
6918794, 34368477811196, 158732542954076, 508974337551424, 1149059884390670, 183
1972166019668, 2053984393632888, 1607413545292970, 873006423537570, 330346793398
632, 89182062643336, 17881599586278, 2676962126984, 267487902960, 12794880000, 0
, 0]    8663400087552000

time: 2h, 44min, 16,348 ms


vc  -->  61# : [108052, 30191510, 2535184052, 97991433422, 2127011507618, 291735
98576482, 272645362057174, 1821821693810676, 8964195681719130, 32997523657650164
, 91356158180939430, 189814692697158018, 293915450568952590, 335840098702378862,
 279919316905752600, 168129961407329142, 72004806803298542, 21878554858763198, 4
744392990841068, 745597287896106, 84747808443488, 6431297624676, 241430784000, 0
]      1502528038502400000


time: 13h, 5min, 51,865 ms

[Dmitriy40]

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

Вторая таблица это попросту вторая часть обсчёта с forprime(p=pmid+1,pfin, ?

Да.

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

Деление на 3 части не пробовали?

Смысла не вижу: цель экономии памяти и так достигнута, а скорость от разбиения вообще говоря должна падать (и на две тоже, если растёт это скорее везение). К тому же видно что максимальная скорость достигается вовсе не при разбиении на одинаковые размеры таблиц, а в соотношении 1:100 или даже $n:n^2$ (или ещё выше степень). Впрочем, ради интереса попробовать можно будет.

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

Запустил 61# с pmid = 19. Как и ожидал, длина ww[] превысила миллион, но время хорошее.

Скоро (не обязательно на следующем простом, может и через одно-два) видимо придётся увеличивать pmid чтобы уменьшить второй размер. Вообще с некоторого p# размеры расти почти перестанут, для однотабличной программы это было примерно на трети диаметра, тут может на одно-два простое дальше (потому что деление на две таблицы лишь частично исключает повторы).

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

В этом способе перераспределения памяти хорошо то, что эта самая длина ww[] не только не скачет как раньше, меняясь в разы, но и порой почти одинаковая: 1134260, 1233474, 1132106.

На самом деле скачет только так, просто вторым числом выводится максимум, а он почему-то более стабилен. Скачки легко увидеть в диспетчере задач в винде, график занятой памяти, вершины пиков (размер ww[]) будут на разной высоте.

[Yadryara]

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

Смысла не вижу: цель экономии памяти и так достигнута, а скорость от разбиения вообще говоря должна падать (и на две тоже, если растёт это скорее везение).

Всё никак не соберусь ещё раз проверить, рост скорости от расщепления это тоже везение?

А ведь это хронологически первый способ экономить память.

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

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

Заметил, что не написал слово "максимум", но не стал редактировать, решил что и так будет понятно, ведь три примера я привёл.

Вот ещё два:

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]


cg  o = 1 --> 67#: [3574, 1926028, 267873430, 16189627288, 514272336734, 9542054
371058, 111084711012830, 853571522208232, 4483427812498680, 16467587429202364, 4
2853629817510750, 79463288364392690, 105009354529670000, 98510830131126016, 6521
0539918771486, 30316162030353362, 9929110649591728, 2336442731339718, 4079706628
12932, 52790596005500, 4562564397600, 198320640000], sum=456020624577672000, #ww
[]=769+1564042, time : 8h, 4min, 3,992 ms

cg  o = 2 --> 67#: [22226, 8923648, 1094142972, 58801920864, 1660087227602, 2757
0566753890, 290519396951380, 2044315865860448, 9940984214122286, 341565157122397
70, 84043595139004496, 149033054558505866, 190507160740828590, 17465987153759975
0, 113830354078946092, 52223813606497110, 16779262272193780, 3800105238105786, 6
19132668247084, 73469346738884, 5944442767476, 241430784000], sum=83203763080838
4000, #ww[]=1330+1643600, time : 22h, 7min, 42,381 ms


24  cg = [0, 25800, 10849676, 1362016402, 74991548152, 2174359564336, 3711262112
4948, 401604107964210, 2897887388068680, 14424412026620966, 50624103141442134, 1
26897224956515246, 228496342922898556, 295516515270498590, 273170701668725766, 1
79040893997717578, 82539975636850472, 26708372921785508, 6136547969445504, 10271
03331060016, 126259942744384, 10507007165076, 439751424000, 0]    12880582553860
56000

time: 22h, 7min, 42,512 ms



4  do = [2, 4, 8, 10]

g2  o = 1 --> 67#: [0], sum=0, #ww[]=0+0, time : 36 ms

g2  o = 2 --> 67#: [0], sum=0, #ww[]=0+0, time : 40 ms

g2  o = 3 --> 67#: [0], sum=0, #ww[]=0+0, time : 59 ms

g2  o = 4 --> 67#: [115944, 35509268, 3179873998, 125583670102, 2637787778670, 3
2858421731008, 260386310356342, 1376628189856192, 5021527508286396, 129487025568
99024, 24003356347583998, 32287127962193086, 31577657952747346, 2237069783240445
2, 11402771548032348, 4151040285099538, 1067277714467546, 188990280411110, 21871
162367308, 1497340488324, 43110144000], sum=146715201110016000, #ww[]=346+762963
, time : 1h, 48min, 30,354 ms


25  g2 = [0, 0, 115944, 35509268, 3179873998, 125583670102, 2637787778670, 32858
421731008, 260386310356342, 1376628189856192, 5021527508286396, 1294870255689902
4, 24003356347583998, 32287127962193086, 31577657952747346, 22370697832404452, 1
1402771548032348, 4151040285099538, 1067277714467546, 188990280411110, 218711623
67308, 1497340488324, 43110144000, 0, 0]    146715201110016000

time: 1h, 48min, 30,588 ms


vc  -->  67# : [36332566, 6755354658, 432632043754, 13747221901462, 256763023574
826, 3116495868026784, 26217835727367166, 159375259161246210, 718261238441747784
, 2432527778334313264, 6217199252918951212, 11964276578057082694, 17222187694193
184304, 18373843004373703136, 14370929572658525308, 8145622439935577894, 3312127
276138281828, 961440013415819506, 200273895076384720, 30329644505506132, 3320650
881197732, 241885270053060, 8691508224000, 0]      84141570156134400000


time: 23h, 56min, 13,101 ms

У Вас пока никаких новостей? Неужто асм бунтует

[Dmitriy40]

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

Всё никак не соберусь ещё раз проверить, рост скорости от расщепления это тоже везение?

По идее - да, я же выше об этом сказал. Поэтому кстати он и не такой большой, всего раза в полтора. Без расщепления формируется самый короткий список уникальных элементов и потом он сворачивается в vc[]. При расщеплении формируются много списков, но каждый из них хуже "свёрнут" - если объединить (без исключения дублей, просто сумма) их все, то суммарный объём будет больше чем без расщепления, ведь при этом не объединяются элементы из разных списков (одинаковые элементы во второй таблице для разных элементов первой таблицы), а значит и сворачивание в vc[] будет делать больше работы. Теоретически. А практически - короткие таблицы (что первую, что вторую) обрабатывать быстрее (по многим причинам), вот и появляется выигрыш скорости, несмотря на реально больший объём работы.

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

А ведь это хронологически первый способ экономить память.

Ну ... Первоначально памяти вообще не требовалось, был глубокий перебор. Вплоть до той программы с Calc(). Память стала требоваться для программы с ww[]. Но да, способ экономии первый, даже в той моей теме с вопросом оценки размера ww[] он в голову не пришёл.

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

У Вас пока никаких новостей? Неужто асм бунтует

Новостей нет, пока этим вопросом не занимался, другое считается (до завтра). Да и вообще занят был (в частности с Демисом боролись сначала с ошибкой у Томаша в ассимиляторе (код боинка на сервере) приводящей к огромной туче неправильных цепочек TPT (чуть не весь апрель), потом с ошибочными цепочками в БД от прошлого лета, потом с начала мая с дублями в боинке, только вчера побороли). И сначала проверю Вашу мысль про третью таблицу. И свою про оптимизацию сразу нескольких последних итераций вместо одной (это несложно). А асм ... С ним непросто всё, готовые решения с Map() мне не нравятся (даже если они вообще есть), а писать своё быстрое долго. Вообще говоря код почти есть (использовал его для оценки размеров ww[] для 41#-43#), надо только его подправить (например все счётчики расширить вдвое до 128 бит, отдельный гемор) и улучшить и сделать деление общих таблиц по k и решить вопрос с коллизиями (не получается от них избавиться). Как говорил кода где-то 2/3 необходимого и треть (а может и половину) надо дописывать. Но сомневаюсь что удастся посчитать до 113#, хотя третья таблица может сильно помочь если размеры второй будут неадекватными.

[Yadryara]

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

По идее - да, я же выше об этом сказал.

А мы точно об одном и том же говорим? Выше Вы сказали про разбиение, а я — про расщепление. То есть говорил о замене одного паттерна на несколько более длинных.

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

Да и вообще занят был

Я так и подумал.

[Dmitriy40]

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

А мы точно об одном и том же говорим? Выше Вы сказали про разбиение, а я — про расщепление. То есть говорил о замене одного паттерна на несколько более длинных.

Ой нет, о разном. Всё в голове смешалось (да и слова похожи даже по смыслу).
Про рост скорости от расщепления я ничего утверждать не могу, думаю это зависит от конкретного паттерна (и исходного, и получаемых), там же вон даже много их не проходит по модулям. Заранее непонятно насколько быстрее будут считаться более длинные паттерны и пересилит ли это увеличение их количества.
Кстати это тоже метод экономии памяти (раз вся ww[] не влезает посчитаем их несколько для разных паттернов и объединим в общий vc[]). Экономия одного шага при этом влияет на скорость, не на память.

[Yadryara]

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

Кстати это тоже метод экономии памяти (раз вся ww[] не влезает посчитаем их несколько для разных паттернов и объединим в общий vc[]).

Почему же кстати, я ведь про этот способ и говорил:

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

А ведь это хронологически первый способ экономить память.

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

да и слова похожи даже по смыслу

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

[Dmitriy40]

Проверил свою мысль о двух и более последних итерациях, не считать их через Map, а сразу сворачивать в vc[]. Выходит замедление в 1.5-2 раза везде где проверил.
Можно сделать вывод что операция даже с огромной Map() всё равно дешевле десятка более простых операций с vc[]. Потому последнюю итерацию выгоднее считать сразу в vc[] (это по любому придётся делать), остальные же нет.

Плюс проверил мысль про три таблицы. Точнее не совсем про три, просто прикинул размеры таблицы если её считать после предыдущих. В среднем выходит что на каждые 5 простых надо полмиллиона (200-700тыс) размер таблицы (на 6 простых - 3-4млн). Практически независимо с какого простого начинать. И вот это беда! Не происходит насыщение размера, как было бы с одной большой таблицей - потому что варианты от разных элементов предыдущей таблицы (таблиц) не объединяются хоть и идентичны. А это означает что вместо линейного прохода по простым снова попадаем на вложенный перебор, только уже не по простым, а по таблицам, что не многим легче.

В память влезает больше десятка миллионов элементов, значит можно каждую следующую таблицу считать по 6 простых. А именно $37\#\to61\#\to89\#\to109\#\to113\#$ (последнюю итерацию выгоднее считать сразу в vc[]), 4 вложенных таблицы. И раз насыщения около 89# не происходит, то перебрать придётся порядка $3\cdot10^6 (24+24+28+34+40+42+\\+3\cdot10^6 (48+52+54+60+64+70+\\+3\cdot10^6 (78+82+84+88+90)))\appox\\ \approx 27\cdot10^{18}\cdot422\approx10^{22}$ операций с Map() и потом ещё порядка $3\cdot10^{19}$ раз пройти по таблице длиной полмиллиона и свернуть её в vc[]. Как-то слишком уж перебор. Это без расщепления.

Что может дать расщепление. Оно уменьшает вычисления на один шаг, т.е. фактически можно считать каждую таблицу на шаг дальше, не 6 простых, а 7. А если под x64, то и 8 (порядка 2ГБ на каждую таблицу размером порядка 30млн). По 8 простых до 109# можно добраться так (показываю только целевые простые, с учётом что реально считаться будет лишь до предыдущего простого, и только самый последний расчёт, 109#, предыдущие на порядок быстрее): $41\#\to73\#\to109\#$, 3 таблицы, перебор порядка $3\cdot10^7 (24+28+34+40+42+48+52+54+\\+3\cdot10^7 (60+64+70+78+82+84+88+90))\approx\\ \appox9\cdot10^{14}\cdot616\approx5.5\cdot10^{17}$ плюс 9e14 проходов по таблице длиной 3e7 для получения vc[]. Если принять скорость работы с таблицами как 1e8/c, то на 6e17 надо 6e9 секунд или 200 лет в один поток. Всё равно нереально, даже если вдруг скорость будет на порядок выше.

Надо делать расщепление второго порядка, чтобы вторая и третья таблицы считались не по 8 простым, а по 9, тогда вычисление 113# будет вида $31\#\to71\#\to109\#$ и перебор порядка $3\cdot10^5 (20+24+24+28+34+40+42+48+52+\\+2\cdot10^8 (54+60+64+70+78+82+84+88+90))\approx\\ \approx4\cdot10^{16}$, на порядок меньше, 14 лет в одном потоке, вот блин. Походу надо расщепление третьего порядка, уж год в одном потоке терпимо, хотя точность оценки конечно очень так себе.