Пентадекатлон мечты

Yadryara · 29/04/13 8129 Богородский

Краткая биекция вида DH ( $Dmitriy \to Hugo$ ). Вторая часть. Самые большие шаги.

Да, математика наука точная. И мы пока сознательно рассматриваем только 1044 паттерна, предполагая что остальные можно исключить отдельным перебором квадратов простых. В теме об этом шла речь неоднократно. Многие паттерны уже исключены таким способом.

(Оффтоп)

Код:

LCM8116970400-145106937-4   b253
LCM8116970400-196965369-4   b165
LCM8116970400-196965369-5   b641
LCM8116970400-196965369-6   b1197
LCM8116970400-272337241-8   b2126
LCM8116970400-1019291769-4   b170
LCM8116970400-1019291769-5   b646
LCM8116970400-1019291769-6   b1202
LCM8116970400-1131705369-4   b207
LCM8116970400-1304674137-4   b301
LCM8116970400-1916990041-6   b1048
LCM8116970400-1954031769-4   b213
LCM8116970400-2122169017-8   b2026
LCM8116970400-2628513369-6   b1193
LCM8116970400-2721278745-6   b1107
LCM8116970400-2721278745-7   b1618
LCM8116970400-2721278745-8   b1866
LCM8116970400-2771526649-8   b1951
LCM8116970400-3108767449-8   b1910
LCM8116970400-3543605145-4   b77
LCM8116970400-3543605145-5   b584
LCM8116970400-3543605145-6   b1112
LCM8116970400-3543605145-7   b1623
LCM8116970400-3543605145-8   b1871
LCM8116970400-3751038841-8   b2077
LCM8116970400-3768432345-4   b110
LCM8116970400-3768432345-5   b608
LCM8116970400-3768432345-6   b1153
LCM8116970400-3843804217-8   b2054
LCM8116970400-4273166169-4   b175
LCM8116970400-4348538041-6   b1044
LCM8116970400-4348538041-7   b1544
LCM8116970400-4348538041-8   b2135
LCM8116970400-4365931545-4   b84
LCM8116970400-4573365241-4   b33
LCM8116970400-4573365241-5   b513
LCM8116970400-4573365241-6   b1008
LCM8116970400-4573365241-7   b1514
LCM8116970400-4573365241-8   b2083
LCM8116970400-5008202937-4   b249
LCM8116970400-5345443737-4   b292
LCM8116970400-5395691641-4   b38
LCM8116970400-5395691641-5   b518
LCM8116970400-5395691641-6   b1013
LCM8116970400-5488457017-6   b996
LCM8116970400-5994801369-4   b203
LCM8116970400-6162938617-8   b2016
LCM8116970400-6199980345-6   b1150
LCM8116970400-6812296249-8   b1941
LCM8116970400-6985265017-8   b2022
LCM8116970400-7097678617-6   b988
LCM8116970400-7097678617-7   b1496
LCM8116970400-7097678617-8   b2059
LCM8116970400-7844633145-4   b119
LCM8116970400-7920005017-6   b993
LCM8116970400-7920005017-7   b1501
LCM8116970400-7920005017-8   b2064
LCM8116970400-7971863449-8   b1906
LCM14642258400-98808345-4   b105
LCM14642258400-98808345-5   b606
LCM14642258400-379787769-4   b198
LCM14642258400-491117337-4   b280
LCM14642258400-940570137-4   b237
LCM14642258400-1600648249-8   b1989
LCM14642258400-1929090649-8   b1936
LCM14642258400-2011613017-6   b976
LCM14642258400-2011613017-7   b1486
LCM14642258400-2011613017-8   b2046
LCM14642258400-2040420217-8   b2003
LCM14642258400-2132623417-6   b980
LCM14642258400-2132623417-7   b1490
LCM14642258400-2132623417-8   b2050
LCM14642258400-2142774841-6   b1078
LCM14642258400-2142774841-7   b1561
LCM14642258400-2142774841-8   b2161
LCM14642258400-2161430617-8   b2008
LCM14642258400-2263785241-4   b26
LCM14642258400-2263785241-5   b548
LCM14642258400-2263785241-6   b1083
LCM14642258400-2263785241-7   b1566
LCM14642258400-2263785241-8   b2166
LCM14642258400-2321399641-8   b2113
LCM14642258400-2398005945-4   b101
LCM14642258400-2398005945-5   b602
LCM14642258400-2398005945-6   b1145
LCM14642258400-2519016345-4   b104
LCM14642258400-2519016345-5   b605
LCM14642258400-2519016345-6   b1148
LCM14642258400-2563420441-6   b1035
LCM14642258400-2697641145-4   b67
LCM14642258400-2697641145-5   b577
LCM14642258400-2697641145-6   b1104
LCM14642258400-2697641145-7   b1615
LCM14642258400-2697641145-8   b1863
LCM14642258400-2707792569-6   b1180
LCM14642258400-2799995769-4   b197
LCM14642258400-2949813369-4   b161
LCM14642258400-3899845849-8   b1982
LCM14642258400-4020856249-8   b1988
LCM14642258400-4228288249-8   b1932
LCM14642258400-4349298649-8   b1935
LCM14642258400-4552831417-6   b979
LCM14642258400-4552831417-7   b1489
LCM14642258400-4552831417-8   b2049
LCM14642258400-4562982841-7   b1560
LCM14642258400-4562982841-8   b2160
LCM14642258400-4805003641-4   b30
LCM14642258400-4805003641-5   b552
LCM14642258400-5099193369-4   b193
LCM14642258400-5370021369-4   b160
LCM14642258400-5370021369-5   b639
LCM14642258400-5452543737-4   b285
LCM14642258400-5573554137-4   b288
LCM14642258400-5780986137-4   b236
LCM14642258400-5901996537-4   b241
LCM14642258400-6852029017-6   b975
LCM14642258400-6852029017-7   b1485
LCM14642258400-6852029017-8   b2045
LCM14642258400-6983190841-8   b2157
LCM14642258400-7104201241-4   b23
LCM14642258400-7104201241-5   b545
LCM14642258400-7104201241-6   b1080
LCM14642258400-7104201241-7   b1563
LCM14642258400-7104201241-8   b2163
LCM14642258400-7122857017-8   b2012
LCM14642258400-7225211641-4   b27
LCM14642258400-7225211641-5   b549
LCM14642258400-7225211641-6   b1084
LCM14642258400-7238421945-4   b98
LCM14642258400-7238421945-5   b599
LCM14642258400-7238421945-6   b1142
LCM14642258400-7282826041-6   b1029
LCM14642258400-7282826041-7   b1531
LCM14642258400-7282826041-8   b2119
LCM14642258400-7359432345-4   b102
LCM14642258400-7359432345-5   b603
LCM14642258400-7359432345-6   b1146
LCM14642258400-7403836441-6   b1031
LCM14642258400-7403836441-7   b1533
LCM14642258400-7403836441-8   b2121
LCM14642258400-7417046745-6   b1097
LCM14642258400-7417046745-7   b1608
LCM14642258400-7417046745-8   b1856
LCM14642258400-7519401369-4   b190
LCM14642258400-7538057145-4   b64
LCM14642258400-7538057145-5   b574
LCM14642258400-7538057145-6   b1101
LCM14642258400-7538057145-7   b1612
LCM14642258400-7538057145-8   b1860
LCM14642258400-7659067545-4   b71
LCM14642258400-7790229369-4   b159
LCM14642258400-7790229369-5   b638
LCM14642258400-7790229369-6   b1191
LCM14642258400-8740261849-8   b1979
LCM14642258400-8861272249-8   b1986
LCM14642258400-9068704249-8   b1929
LCM14642258400-9189714649-8   b1934
LCM14642258400-9272237017-7   b1484
LCM14642258400-9272237017-8   b2044
LCM14642258400-9543065017-8   b2011
LCM14642258400-9837254745-7   b1607
LCM14642258400-9837254745-8   b1855
LCM14642258400-10079275545-4   b69
LCM14642258400-10079275545-5   b579
LCM14642258400-10089426969-4   b155
LCM14642258400-10089426969-5   b634
LCM14642258400-10089426969-6   b1187
LCM14642258400-10292959737-4   b284
LCM14642258400-10413970137-4   b287
LCM14642258400-10621402137-4   b235
LCM14642258400-10742412537-4   b240
LCM14642258400-11692445017-8   b2041
LCM14642258400-11842262617-8   b2007
LCM14642258400-11934465817-6   b983
LCM14642258400-11944617241-4   b22
LCM14642258400-11944617241-5   b544
LCM14642258400-11944617241-6   b1079
LCM14642258400-11944617241-7   b1562
LCM14642258400-11944617241-8   b2162
LCM14642258400-12078837945-6   b1139
LCM14642258400-12123242041-6   b1027
LCM14642258400-12123242041-7   b1529
LCM14642258400-12123242041-8   b2117
LCM14642258400-12244252441-6   b1030
LCM14642258400-12244252441-7   b1532
LCM14642258400-12244252441-8   b2120
LCM14642258400-12320858745-4   b106
LCM14642258400-12378473145-4   b63
LCM14642258400-12378473145-5   b573
LCM14642258400-12378473145-6   b1100
LCM14642258400-12378473145-7   b1611
LCM14642258400-12378473145-8   b1859
LCM14642258400-12480827769-4   b194
LCM14642258400-12499483545-4   b68
LCM14642258400-12499483545-5   b578
LCM14642258400-12499483545-6   b1105
LCM14642258400-12509634969-4   b152
LCM14642258400-12509634969-5   b631
LCM14642258400-12509634969-6   b1184
LCM14642258400-12601838169-4   b199
LCM14642258400-12630645369-4   b156
LCM14642258400-12630645369-5   b635
LCM14642258400-12630645369-6   b1188
LCM14642258400-12713167737-4   b283
LCM14642258400-13041610137-4   b234
LCM14642258400-13701688249-8   b1983
LCM14642258400-14151141049-8   b1937
LCM14642258400-14262470617-8   b2006
LCM14642258400-14543450041-7   b1528
LCM14642258400-14543450041-8   b2116
LCM56818792800-272337241-8   b2101
LCM56818792800-452392249-8   b1964
LCM56818792800-1019291769-4   b145
LCM56818792800-1019291769-5   b627
LCM56818792800-1019291769-6   b1177
LCM56818792800-1224470745-6   b1123
LCM56818792800-1224470745-7   b1634
LCM56818792800-1224470745-8   b1882
LCM56818792800-1304674137-4   b278
LCM56818792800-1916990041-4   b49
LCM56818792800-1916990041-5   b562
LCM56818792800-2029403641-4   b5
LCM56818792800-2029403641-5   b527
LCM56818792800-2029403641-6   b1062
LCM56818792800-2721278745-6   b1088
LCM56818792800-2721278745-7   b1599
LCM56818792800-2721278745-8   b1847
LCM56818792800-4273166169-4   b150
LCM56818792800-5488457017-6   b973
LCM56818792800-6985265017-8   b1997
LCM56818792800-7971863449-8   b1968
LCM56818792800-10033960441-6   b1025
LCM56818792800-10239139417-8   b2001
LCM56818792800-11225737849-8   b1972
LCM56818792800-11530768441-8   b2094
LCM56818792800-12482901945-4   b61
LCM56818792800-14784642841-8   b2098
LCM56818792800-20002373145-4   b87
LCM56818792800-20002373145-5   b591
LCM56818792800-20002373145-6   b1132
LCM56818792800-20727102649-8   b1954
LCM56818792800-20807306041-4   b14
LCM56818792800-20807306041-5   b536
LCM56818792800-20807306041-6   b1071
LCM56818792800-20807306041-7   b1556
LCM56818792800-20807306041-8   b2153
LCM56818792800-21579384537-4   b269
LCM56818792800-21759439545-4   b132
LCM56818792800-23980977049-8   b1959
LCM56818792800-24547876569-4   b140
LCM56818792800-24547876569-5   b622
LCM56818792800-24547876569-6   b1172
LCM56818792800-24753055545-6   b1117
LCM56818792800-24753055545-7   b1628
LCM56818792800-24753055545-8   b1876
LCM56818792800-26304942969-4   b188
LCM56818792800-28119343545-7   b1591
LCM56818792800-28119343545-8   b1840
LCM56818792800-28699449241-4   b45
LCM56818792800-28699449241-5   b558
LCM56818792800-30513849817-8   b1991
LCM56818792800-32065737241-4   b9
LCM56818792800-32065737241-5   b531
LCM56818792800-32065737241-6   b1066
LCM56818792800-32270916217-6   b970
LCM56818792800-32270916217-7   b1482
LCM56818792800-32270916217-8   b2039
LCM56818792800-32837815737-4   b261
LCM56818792800-35059353241-8   b2088
LCM56818792800-35239408249-8   b1927
LCM56818792800-36011486745-4   b54
LCM56818792800-36011486745-5   b567
LCM56818792800-36011486745-6   b1093
LCM56818792800-36011486745-7   b1604
LCM56818792800-36011486745-8   b1852
LCM56818792800-36091690137-4   b266
LCM56818792800-36816419641-6   b1021
LCM56818792800-36816419641-7   b1525
LCM56818792800-36816419641-8   b2110
LCM56818792800-42034149945-4   b122
LCM56818792800-44335890841-8   b2147
LCM56818792800-45288024345-4   b126
LCM56818792800-45593054937-4   b228
LCM56818792800-46579653369-4   b178
LCM56818792800-46784832345-6   b1129
LCM56818792800-48846929337-4   b232
LCM56818792800-49833527769-4   b182
LCM56818792800-51330335769-6   b1168
LCM56818792800-52545626617-8   b2029
LCM56818792800-54097514041-4   b19
LCM56818792800-54097514041-5   b541
LCM56818792800-54097514041-6   b1076
LCM56818792800-54789389145-6   b1120
LCM56818792800-54789389145-7   b1631
LCM56818792800-54789389145-8   b1879
LCM56818792800-54901802745-7   b1588
LCM56818792800-54901802745-8   b1837
LCM56818792800-55514118649-8   b1918
LCM56818792800-55594322041-4   b2
LCM56818792800-55594322041-5   b524
LCM56818792800-55594322041-6   b1059
LCM56818792800-55799501017-6   b965
LCM56818792800-55799501017-7   b1477
LCM56818792800-55799501017-8   b2034
LCM56818792800-56366400537-4   b256
LCM56818792800-56546455545-4   b96
LCM19488845930400-851262600217-6   b977
LCM19488845930400-851262600217-7   b1487
LCM19488845930400-851262600217-8   b2047
LCM19488845930400-1203228609241-6   b1036
LCM19488845930400-1905534012217-8   b2004
LCM19488845930400-1911031649145-4   b65
LCM19488845930400-1911031649145-5   b575
LCM19488845930400-1911031649145-6   b1102
LCM19488845930400-1911031649145-7   b1613
LCM19488845930400-1911031649145-8   b1861
LCM19488845930400-2442935753145-4   b107
LCM19488845930400-3344336911737-4   b242
LCM19488845930400-3464641686649-8   b1930
LCM19488845930400-3843675537241-6   b1032
LCM19488845930400-3843675537241-7   b1534
LCM19488845930400-3843675537241-8   b2122
LCM19488845930400-6010309134841-8   b2158
LCM19488845930400-6015806771769-4   b195
LCM19488845930400-6132156456217-8   b2042
LCM19488845930400-7070078183769-4   b153
LCM19488845930400-7070078183769-5   b632
LCM19488845930400-7070078183769-6   b1185
LCM19488845930400-8192145302617-8   b2013
LCM19488845930400-8625230767737-4   b238
LCM19488845930400-9656473497241-4   b28
LCM19488845930400-9656473497241-5   b550
LCM19488845930400-9656473497241-6   b1085
LCM19488845930400-9710525111769-6   b1181
LCM19488845930400-9737592953337-4   b281
LCM19488845930400-9751252977049-8   b1938
LCM19488845930400-9778320818617-6   b984
LCM19488845930400-9832372433145-6   b1098
LCM19488845930400-9832372433145-7   b1609
LCM19488845930400-9832372433145-8   b1857
LCM19488845930400-10863615162649-8   b1984
LCM19488845930400-11296700627769-4   b191
LCM19488845930400-12418767746617-6   b981
LCM19488845930400-12418767746617-7   b1491
LCM19488845930400-12418767746617-8   b2051
LCM19488845930400-13356689474169-4   b162
LCM19488845930400-13473039158617-8   b2009
LCM19488845930400-13478536795545-4   b72
LCM19488845930400-15645170393145-4   b99
LCM19488845930400-15645170393145-5   b600
LCM19488845930400-15645170393145-6   b1143
LCM19488845930400-16024204243737-4   b289
LCM19488845930400-16144509018649-8   b1980
LCM19488845930400-17045910177241-8   b2114
LCM19488845930400-17577814281241-4   b24
LCM19488845930400-17577814281241-5   b546
LCM19488845930400-17577814281241-6   b1081
LCM19488845930400-17577814281241-7   b1564
LCM19488845930400-17577814281241-8   b2164
LCM19488845930400-17583311918169-4   b200
LCM19488845930400-18285617321145-6   b1140
LCM19488845930400-18637583330169-4   b157
LCM19488845930400-18637583330169-5   b636
LCM19488845930400-18637583330169-6   b1189

Dmitriy40 · 20/08/14 11780 Россия, Москва

К вопросу о скорости проверки паттернов.

EUgeneUS в сообщении #1568985 писал(а):

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

Ну вот, наконец-то сверил скорости по Вашей проге и по Hugo.

Мне не очень понятно, что с чем Вы сравнивали :(
Вы не могли бы привести время счета для одного и того же компьютера, но для разных программ?

Вот проверка моей программой (не опубликована):

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

Хех, 50ч говорите ... Лог проверки его же моими ускорителями с однократным перебором простых (с сокращениями, время нарастающим итогом):

Код:

b1850: [45,2,1,12,49,50,363,32,1,18,5]
b1850-13 end, time: 4122.469s
b1850-17 end, time: 6144.172s
b1850-19:287834780609527920345: 12, 16, 12, 12, 12, 12, 12, 12, 12, 12, 12,192, 32, 16,  2,  valids=10, maxlen=9
b1850-19 end, time: 7646.955s
b1850-23:3476367315695605545945: 12,  8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 16, 16,  4,  valids=10, maxlen=9
b1850-23 end, time: 8606.041s
b1850-29:2916461522504711241945: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 96,128, 16, 24,  valids=10, maxlen=10
b1850-29 end, time: 9165.333s
b1850-61:2605102794736967832345: 12, 16, 12, 12, 12, 12, 12, 12, 12, 12, 12, 48, 16, 16, 64,  valids=10, maxlen=9
b1850-61 end, time: 11045.913s
b1850-83:3353090009360291707545: 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 48, 24,128, 16,  valids=10, maxlen=9
b1850-83 end, time: 11419.058s
b1850-27919 end, time: 13252.135s
b1850-27941 end, time: 13252.478s
b1850-27943 end, time: 13252.822s
AVX2: up to 27943:6088, time: 13252.822s
PARI: up to 15305333:986120, time: 15894.893s
ALL:  up to 6726727940:1864338, time: 16244.671s

Очевидно для нескольких первых простых надо было запускать и второй перебор, было бы быстрее.

И программой Hugo на том же компе и того же паттерна:

Код:

pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1850
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 17^2 2.3^2 5: 952047157 / 2371109213 (600.29s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 17^2 2.3^2 5: 1861722772 / 2371109213 (1200.58s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 19^2 2.3^2 5: 438241470 / 1898201004 (1800.88s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 19^2 2.3^2 5: 1342194516 / 1898201004 (2401.17s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 23^2 2.3^2 5: 378560006 / 1295369683 (3001.46s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 23^2 2.3^2 5: 1290452107 / 1295369683 (3601.75s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 31^2 2.3^2 5: 125463036 / 713059898 (4202.04s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 37^2 2.3^2 5: 339062307 / 500548255 (4802.33s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 43^2 2.3^2 5: 366898324 / 370606037 (5402.63s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 67^2 2.3^2 5: 555714 / 152651049 (6002.92s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 107^2 2.3^2 5: 16125364 / 59852437 (6603.21s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 571^2 2.3^2 5: 1991043 / 2101731 (7203.50s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 1159976219^2 2.3^2 5 (7803.79s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 2577410461^2 2.3^2 5 (8404.08s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 4009488529^2 2.3^2 5 (9004.38s)
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 5435345023^2 2.3^2 5 (9604.67s)
3^2.5 2 17^2 2^2.3 7^2 2.5^2 3.11^2 2^5 13^2 2.3^2 5: 890044862 / 2371109214 (10204.96s)
...
3^2.5 2 223^2 2^2.3 7^2 2.5^2 3.11^2 2^5 6287183029^2 2.3^2 5 (153674.71s)
3^2.5 2 227^2 2^2.3 7^2 2.5^2 3.11^2 2^5 903430279^2 2.3^2 5 (154275.00s)
3^2.5 2 227^2 2^2.3 7^2 2.5^2 3.11^2 2^5 2302029787^2 2.3^2 5 (154875.30s)

Как видно на текущий момент она ещё довольно далека от завершения, хотя уже работает почти в 10 раз дольше!
И никакое 20% ускорение новой программы Hugo эту разницу не съест.

Dmitriy40 · 20/08/14 11780 Россия, Москва

Хм, я что-то не понял:

Hugo on wiki писал(а):

Each pattern is listed with its batch number in an output line starting "203", like:

203 b2470: . 2.11^2 3 2^2.7 5 2.3 . 2^3 3^5 2.5^2 7^5 [sq=2]

Это что, в список паттернов для проверки у Hugo попали и цепочки с $2^3$ вместо $2^5$ ?! Но ведь таковых длиной 10+ точно нет, это доказали неоднократно несколько человек. А он их проверял что ли?! Они все у него в списке помечены "done", видимо и правда проверял ... :facepalm:

Huz · 05/06/22 293

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

Huz в сообщении #1569390 писал(а):

It is less obvious how to construct a CRT test that is valid, but I'll try that tomorrow.

It's just brazen to put the first prime not 13, but 10^7 (this is guaranteeing that all less will not check). Well, or skip all the primes less than 10^7 without any calculations. This is one additional "if(p<10^7) {goto next}" in the right place of the code. Second "if" need to skip checking result of CRT - to not delete code. That's all.
However, perhaps everything is not so simple, you know better.

The CRT calculation is part of the recursion: at each step of recursion, we combine the previous result with the new allocation.

I've written a new speed test that sets the "previous result" to 1138387546 (mod 1311710400) which represents the state after allocations of $(2, 11, 2^2 \cdot 3, 13^2, 2 \cdot 5^2, 3 \cdot 7^2, 2^5, 1, 2 \cdot 3^2, 5, 2^2)$ , and then iterate over primes (from 17) to mimic a new allocation of $p^2$ in the eighth place (ie at index 7):

Код:

    while (p < target) {
        mpz_ui_pow_ui(px, p, 2);
        update_chinese(&l_old, &l_new, 7, px);
        mpz_add(sum, sum, l_new.rq); /* use the result somehow */
        p = prime_iterator_next(&iter);
    }

I timed this with different targets, then removed the "update_chinese()" call and timed again. Results below are the difference, which represents the time attributable only to the update_chinese() call.

When run with a target of '18', so that it loops just once, it outputs 336936249946 to represent that fact that CRT combines 1138387546 (mod 1311710400) with -7 (mod $17^2$ ) to give 336936249946 (mod lcm(1311710400, $17^2$ )). I output the sum of all the answers so that if I make any changes I can check if it broke anything.

Код:

1000000: 16235264038720815639561432 (0.05s)
10000000: 13837258261742177685598342258 (0.47s)
100000000: 12086814316011038123389238704554 (4.17s)
1000000000: 10723217400891526137851861369785488 (37.19s)
10000000000: 9635614789026040696347755361233992330 (343.81s)

The actual update_chinese() function adds the extra power of 2 if needed, then sets things up to call the library chinese() function, which takes its parameters in a slightly odd form - the TODO comment reflects that it would be easier if chinese() took the parameters in a different form:

Код:

void update_chinese(t_level *old, t_level *new, uint vi, mpz_t px) {
    mpz_t zarray[4];
    mpz_t *pxp = PARAM_TO_PTR(px);
    mpz_set_si(Z(uc_minusvi), -(long)vi);

    /* v_0 == -i (mod 2^e) can be upgraded to v_0 = 2^e - i (mod 2^{e + 1}) */
    if (mpz_even_p(px)) {
        mpz_add(Z(uc_minusvi), Z(uc_minusvi), px);
        mpz_mul_2exp(Z(uc_px), px, 1);
        pxp = ZP(uc_px);
    }

    /* TODO: write a custom chinese() */
    memcpy(&zarray[0], old->rq, sizeof(mpz_t));
    memcpy(&zarray[1], Z(uc_minusvi), sizeof(mpz_t));
    memcpy(&zarray[2], old->aq, sizeof(mpz_t));
    memcpy(&zarray[3], *pxp, sizeof(mpz_t));
    if (chinese(new->rq, new->aq, &zarray[0], &zarray[2], 2))
        return;
    fprintf(stderr, "chinese failed");
    exit(1);
}

-- 09.11.2022, 17:39 --

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

Это что, в список паттернов для проверки у Hugo попали и цепочки с $2^3$ вместо $2^5$ ?! Но ведь таковых длиной 10+ точно нет, это доказали неоднократно несколько человек. А он их проверял что ли?! Они все у него в списке помечены "done", видимо и правда проверял ... :facepalm:

Yes, I check those too. I do this for completeness - they are very quick to check, it is faster to check them than to verify somebody else's code (or learn Russian). :)

Dmitriy40 · 20/08/14 11780 Россия, Москва

Huz
Thanks for the tests.
It turns out to iterate up to 6.7e9 it took 6.7*240=1610s to generate prime numbers, CRT added another 0.67*343=230s, in total 1840s and the remainder 2830s-1840s=990s was spent to checking chains.
If you change the prime number generator to an iterator, then the sum will decrease to 10+230+990 =1230s, instead of 2830s. I think it would be nice.
And the main brake will be the chain check.

Huz · 05/06/22 293

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

If you change the prime number generator to an iterator, then the sum will decrease to 10+230+990 =1230s, instead of 2830s. I think it would be nice.

Note that in a separate test of $D(12,9)$ , the iterator saved only 10% of the time in a full run. But maybe it was less because only smaller primes were needed.

I'm now running a $D(12,11)$ pattern (b1630) with the iterator, I'll see what that shows. I will also ask CorporalTermit if he has time to create another Windows build with the latest code. (But if anyone else has the capability to install Cygwin and make a build, it would be great not to have to ask him every time.)

Dmitriy40 · 20/08/14 11780 Россия, Москва

Huz в сообщении #1569535 писал(а):

But maybe it was less because only smaller primes were needed.

Exactly.

Huz в сообщении #1569535 писал(а):

I'm now running a $D(12,11)$ pattern (b1630) with the iterator, I'll see what that shows.

Fine. Check that two iterations of large primes will often be performed recursively, it is the presence of the second level that slows everything down dramatically.

Huz в сообщении #1569535 писал(а):

I will also ask CorporalTermit if he has time to create another Windows build with the latest code.

I think it is not necessary to issue releases every day, you can make all the desired improvements and only then compile the release, IMHO.

Huz · 05/06/22 293

New version of the code (with iterators) now available at https://github.com/hvds/divrep/releases/tag/20221109.

Цитата:

I think it is not necessary to issue releases every day, you can make all the desired improvements and only then compile the release, IMHO.

I don't plan a release for every change. But when there is a substantial speed improvement, it seems worth making that available as soon as possible.

-- 09.11.2022, 19:15 --

@Dmitriy40 I think another point where there may be time to save is in the heuristics to decide when to switch from recursion to linear search.

I visualize the cost of recursion versus linear search as (very roughly) like the graphs of $1 + 1/x^2$ and $10/x^2$ , with the intention being to switch to linear search close to the point the two graphs meet. I think there may be some time wasted there, I will look to see if that can be improved over the next day or two.

(Оффтоп)

In more detail: when recursing, I calculate the highest $p$ for which I should allocate $p^x$ (for a given $x$ ), which involves taking an $x$ 'th root. I use that as a proxy for "the cost of recursing at this level", and compare it against the number of iterations that a linear search would perform (which can be calculated with just a division, if there is no fixed square). I think if I were to calculate the number of iterations first, it might be possible to decide that a linear search should be done without needing the expensive $x$ 'th root calculation.

Dmitriy40 · 20/08/14 11780 Россия, Москва

Huz в сообщении #1569540 писал(а):

But when there is a substantial speed improvement, it seems worth making that available as soon as possible.

Sure.

Huz в сообщении #1569540 писал(а):

I think another point where there may be time to save is in the heuristics to decide when to switch from recursion to linear search.

Yes.
In my code, this moment is even more complicated by an order of magnitude, since the search is performed by two very different programs (PARI and asm), plus the latter has a tuning parameter that would be better changed depending on how many places in the pattern has 6 divisors (its speed strongly depends on this) and what interval should be checked... Darkness and nightmare. For several days I have not been able to come up with a method for more or less accurate estimation of the time required to run the next level of recursion or iterate linearly.

-- 09.11.2022, 23:14 --

Huz
Can I suggest a purely cosmetic change?
At least under windows, change the title of the console window to the current progress of the account, for example in the format "b1850-19", that is, the pattern number and the iterated number at the highest level of recursion. And change the title no more than once a second. I don't know how it is under *unix, I think exactly the same by calling the OS function, but under windows there is definitely the corresponding winapi function.
It is very convenient to monitor the progress of the calculation, especially when there are several of them at the same time.

Dmitriy40 · 20/08/14 11780 Россия, Москва

Huz в сообщении #1569540 писал(а):

New version of the code (with iterators) now available at https://github.com/hvds/divrep/releases/tag/20221109.

Compared on the same pattern the version 20221107:

Код:

pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1850
...
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 5435345023^2 2.3^2 5 (9604.67s)
3^2.5 2 17^2 2^2.3 7^2 2.5^2 3.11^2 2^5 13^2 2.3^2 5: 890044862 / 2371109214 (10204.96s)
...
3^2.5 2 17^2 2^2.3 7^2 2.5^2 3.11^2 2^5 5419966663^2 2.3^2 5 (16808.17s)
3^2.5 2 19^2 2^2.3 7^2 2.5^2 3.11^2 2^5 13^2 2.3^2 5: 370726763 / 1898201004 (17408.46s)

And version 20221109:

Код:

pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1850 *RT*
...
3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 1196227259^2 2.3^2 5 (6422.65s)
3^2.5 2 17^2 2^2.3 7^2 2.5^2 3.11^2 2^5 13^2 2.3^2 5: 309950771 / 2371109214 (7011.89s)
...
3^2.5 2 17^2 2^2.3 7^2 2.5^2 3.11^2 2^5 5023151249^2 2.3^2 5 (11594.42s)
3^2.5 2 19^2 2^2.3 7^2 2.5^2 3.11^2 2^5 13^2 2.3^2 5: 860819009 / 1898201004 (12183.02s)

The latest version is noticeably faster! Very good!

-- 10.11.2022, 03:08 --

Выше было сравнение паттерна b1850 по программе Hugo и моей давней:

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

Код:

b1850: [45,2,1,12,49,50,363,32,1,18,5]
b1850-13 end, time: 4122.469s
b1850-17 end, time: 6144.172s
b1850-19 end, time: 7646.955s
...
b1850-27943 end, time: 13252.822s
AVX2: up to 27943:6088, time: 13252.822s
PARI: up to 15305333:986120, time: 15894.893s
ALL:  up to 6726727940:1864338, time: 16244.671s

Так теперь немного её модифицировал (сделал перебор не по пустому месту как у Hugo, а по наиболее выгодному для меня):

Код:

b1850: [45,2,1,12,49,50,363,32,1,18,5]
b1850-13 end, time: 858.384s
b1850-17 end, time: 1277.091s
b1850-19 end, time: 1582.271s
...
b1850-27943 end, time: 3749.411s
AVX2: up to 27943:6088, time: 3749.411s
PARI: up to 15305333:986120, time: 5038.264s
ALL:  up to 1000000000:1853580, time: 5104.346s

Вот так вот, более трёх раз быстрее! Хотя весь код остался тем же. Потому что для ускорителей стало на одно проверяемое место больше и их скорость резко возросла. И тут уже вряд ли понадобился бы второй перебор.

Yadryara · 29/04/13 8129 Богородский

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

потребовал лишь наличия числа $32x$ и правильных 5-ти чисел вокруг,

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

это числа 32p-2,32p-1,32p,32p+1,32p+2, только они есть в любой десятке.

Ах вот оно что. Так это не 5, а 4 числа вокруг $32x$ . Ну или можно было сказать $32x$ и 4 числа вида $32x\pm1,2$ .

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

Как видно на текущий момент она ещё довольно далека от завершения, хотя уже работает почти в 10 раз дольше!

Сейчас уже завершено? Сколько времени заняло?

В сухом остатке, если судить по конкретному паттерну b1850, Hugo ускорил счёт примерно в полтора раза, Дмитрий — примерно в 3 раза. Итого счёт Дмитрия быстрее в 20 с лишним раз.

Yadryara · 29/04/13 8129 Богородский

EUgeneUS в сообщении #1569308 писал(а):

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

Надеюсь, не те же самые паттерны?

Да, будут перекрываться, к сожалению. Но на это есть причины.

Какие ещё причины, кроме той, что Вы не доверяете программам Дмитрия?

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

Ну а взаимопроверку-то как делать? Программа Hugo не выдала Вам ни одной цепочки, не так ли? Ну и как будем сверять?

Да, если бы нашлась непрерывная 11-ка, программа Hugo, видимо, сообщила бы об этом. И программы Дмитрия тоже не нашли ни одной такой цепочки. Вот единственная точка сверки.

Но ведь программы Дмитрия нашли весьма немало других, более коротких цепочек. Непрерывную 10-ку показывал выше. Но у Софокла ведь есть ещё и 9-ки, 8-ки, 7-ки... Как мы их сравним, если у Вас их нету?

Ну давайте хотя бы скорость сравним. Напомню, что Софокл считал и считает по старым 32 SSE-прогам Дмитрия. Вы же, согласно Hugo, обсчитали вот эти 10 паттернов?

Код:

LCM14642258400-2697641145-8   b1863   end, time:  1555.751s
LCM14642258400-2142774841-8   b2161   end, time:  3749.375s
LCM14642258400-2263785241-8   b2166   end, time:  4793.162s
LCM14642258400-3899845849-8   b1982   end, time:  5348.673s
LCM14642258400-4020856249-8   b1988   end, time:  5766.374s
LCM14642258400-4552831417-8   b2049   end, time:  6786.627s
LCM14642258400-4228288249-8   b1932   end, time: 14627.091s
LCM14642258400-4349298649-8   b1935   end, time: 14758.545s
LCM14642258400-2161430617-8   b2008   end, time: 16129.832s
LCM14642258400-2321399641-8   b2113   end, time: 52468.792s

EUgeneUS · 11/12/16 13852 уездный город Н

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

Какие ещё причины, кроме той, что Вы не доверяете программам Дмитрия?

Поймите, пожалуйста, дело не во мне, не в Дмитрии, не в доверии и даже не в программах.
Тем более, ранее сказал, что считаю текущий код Дмитрия (который работает на Софокле) свободным от критических ошибок.

Дело в предоставлении результатов и в принятии этих результатов.
Если по-простому. Результатом должно быть - новое известное значение в последовательности на OEIS.
Вот мы обсчитали все варианты (как мы думаем, что все) и говорим при подаче результата на OEIS "новых 11-к нет, найденная Хуго ранее - минимальная". "А с платформы говорят - это город Ленинград". И что дальше?

Когда предоставляли результаты по новым цепочкам, там было всё проще. Не важно как нашли цепочку (она могла просто присниться, как Кекуле формула бензола :mrgreen:

), её любой может быстро проверить. Поэтому было достаточно эту цепочку предъявить. А с минимальностью сильно сложнее....

-- 10.11.2022, 09:13 --

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

Ну давайте хотя бы скорость сравним. Напомню, что Софокл считал и считает по старым 32 SSE-прогам Дмитрия. Вы же, согласно Hugo, обсчитали вот эти 10 паттернов?

Первая партия с этим LCM считалась "старым" кодом. Время было 29-29 тысяч секунд на более быстром компе и 30-31 тысяча секунд на более медленном. Но я кроме одинакового LCM выбирал и количество проверяемых мест одинаковое. Поэтому разброс на одном компе оказался небольшим.
Вторая партия считалась кодом от 7 ноября. И там разброс был уже больше: от 17 тысяч секунд до 28 тысяч секунд. В зависмости от компа, и видимо в зависмости от числа проверяемых чисел.
Точные времена могу собрать из логов вечером, если нужно.

-- 10.11.2022, 09:25 --

Huz
I noticed that you have counted the pattern b1629. As far as I understand, this is the first calculated pattern with $LCM=3880800$ . Could you tell us the time for which the calculation was completed?

Dmitriy40 · 20/08/14 11780 Россия, Москва

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

Сейчас уже завершено? Сколько времени заняло?

На данный момент ещё нет, но теперь уже близка к завершению, верхний перебор перешёл к простым 950+, ещё час-два и всё (но я пока убегаю). Уже считает 197500с.

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

В сухом остатке, если судить по конкретному паттерну b1850, Hugo ускорил счёт примерно в полтора раза, Дмитрий — примерно в 3 раза. Итого счёт Дмитрия быстрее в 20 с лишним раз.

Ускорение версии 20221109 больше, за счёт ускорения внутренних переборов она уже где-то вдвое быстрее версии 20221107:

Код:

20221107:
305 3^2.5 2 83^2 2^2.3 7^2 2.5^2 3.11^2 2^5 151802029^2 2.3^2 5 (77437.65s)
20221109:
305 3^2.5 2 83^2 2^2.3 7^2 2.5^2 3.11^2 2^5 13^2 2.3^2 5: 56819800 / 99470250 (36339.76s)

Свой же код я не менял, только указал другую позицию в паттерне для перебора (7 проверяемых мест вместо имеющихся 6-ти, что и увеличило скорость ускорителей втрое).