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

[Yadryara]

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

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

Ну так 0 210 в этот перечень входит. А для него 13 первых констант известно.

[Yadryara]

wrest
Так у вас есть хотя бы 20 первых констант для паттерна [0, 210] ?

Вот пример сходимости для этого паттерна, но для гораздо большего интервала:

0 — 157#

0 —    3.53752 e61
Primes 2.51398 e59

Average gap 141

2-210-1   Constant

7.54879 e57      1
-3.31195 e57     2
4.24080 e57      3
8.58844 e56      4
1.95481 e57      5
1.68091 e57      6
1.73584 e57      7
1.72676 e57      8
1.72802 e57      9
1.72787 e57     10
1.72788 e57     11
1.72788 e57     12
1.72788 e57     13

Видите: 11 первых констант уже дают 6 верных цифр.

Но интересны другие праймориалы:

0 — 61#

0 —    1.17288 e23
Primes 2.25126 e21

Average gap 52

1.   2-210-1

1.82642 e20      1
-5.27591 e20     2
8.07869 e20      3
-8.09663 e20     4
6.08818 e20      5
-3.50926 e20     6
1.70435 e20      7
-6.32034 e19     8
2.48691 e19      9
-3.46759 e18    10
4.40137 e18     11
2.49884 e18     12
2.90209 e18     13

Сходимость пока ещё слабая, но количество кортежей уже примерно понятно: 2800-2900 квадриллионов.

А здесь ситуация ещё хуже:

0 — 59#

0 —    1.92276 e21
Primes 4.00690 e19

Average gap 48

2-210-1   Constant

3.52962 e18      1
-1.13745 e19     2
1.90591 e19      3
-2.09753 e19     4
1.71581 e19      5
-1.08695 e19     6
5.67177 e18      7
-2.38258 e18     8
9.16877 e17      9
-2.36931 e17    10
1.11374 e17     11
1.98124 e16     12
4.09176 e16     13

Почти уверен что 20 констант закрыли бы вопрос по этому паттерну.

[wrest]

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

Так у вас есть хотя бы 20 первых констант для паттерна [0, 210] ?

От Монте-Карло есть, 99 0 210:

(Оффтоп)

[1412601623084355438043174147222260416512, 33845264928878966315732786767069611819008, 392595307140113823324084749080243828948992, 2937123796583041856844434850023647651823616, 15928852270104098380021230976533840145678336, 66733200845887384037806940611502189693632512, 224740855703099433266098058288640641764163584, 625133951314493322236340515959304984918491136, 1464458902515198536811552815635772153721257984, 2931649409975286924717270690317813678080000000, 5071302086294065200404224566263072156540731392, 7646751256185755205267756174343464743656751104, 10119613907057586863594877189615647551114969088, 11817932664941710307582034280668484393481797632, 12231429182103734439340166269001748591046295552, 11257289364462330850985611722149217206689333248, 9237058994941238613965018253214464454541967360, 6770265316312580402657105989720632163683008512, 4438328433922574753287541769072398791834861568, 2604416901019300251241256882392086042430668800, 1368352458548734681808786902613580015185428480, 643570741345986582444415746418332387940237312, 270783373882697620707551593708479273773301760, 101811213007136720765918360221710891935072256, 34153714200640130824774911090406330843791360, 10201372246019735339597134514105511592329216, 2706026115394623544757358349465294215315456, 635405863772432263630319139102899595902976, 131535376831688758666694433617574973407232, 23878684282573086652833872409903927132160, 3774533595295901908868106596961166032896, 514332949278012115630953373614559199232, 59530798392701871824270332492165152768, 5722107325521936476615518853510725632, 440672377134149263590265226136649728, 25596341410288516513815236645486592, 1000121949143723488724523633606656, 19776422723180973220765133438976]

Но гарантий нет.

Посмотрите на примере 0 252 (я обновил данные после замечания), тут должно быть не хуже

[Yadryara]

Спасибо. Пересчитал сразу в константы, точность ещё упала, подробнее напишу позже.

Но всё равно обе сошлись, и Монтя и Карла. На этот раз счёт был именно по 20 константам от wresta:

0 — 61#

0 —    1.17288 e23
Primes 2.25126 e21

Average gap 52

2-210-1   Constant

1.82642 e20      1
-5.27592 e20     2
8.07872 e20      3
-8.09668 e20     4
6.08823 e20      5
-3.50930 e20     6
1.70438 e20      7
-6.32049 e19     8
2.48697 e19      9
-3.46783 e18    10
4.40144 e18     11
2.49881 e18     12
2.90209 e18     13
2.82675 e18     14
2.83921 e18     15
2.83738 e18     16
2.83762 e18     17
2.83759 e18     18
2.83759 e18     19
2.83759 e18     20

0 — 59#

0 —    1.92276 e21
Primes 4.00690 e19

Average gap 48

2-210-1   Constant

3.52962 e18      1
-1.13745 e19     2
1.90592 e19      3
-2.09754 e19     4
1.71582 e19      5
-1.08696 e19     6
5.67186 e18      7
-2.38263 e18     8
9.16902 e17      9
-2.36941 e17    10
1.11377 e17     11
1.98113 e16     12
4.09178 e16     13
3.66283 e16     14
3.74002 e16     15
3.72768 e16     16
3.72944 e16     17
3.72921 e16     18
3.72924 e16     19
3.72924 e16     20

[wrest]

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

От Монте-Карло есть, 99 0 210:

Вот немного улучшенные оценки для 0 210

(Оффтоп)

[1412601654484538004985192904869730582528, 33845431647663917479334286981621945991168, 392598779977931834736296499096863314542592, 2937157884972223507752605265309134267351040, 15929058966903634908507405108460323457728512, 66734045750213418807738279617025293319929856, 224743167605999066176878718055379904187334656, 625137320726482379192044414859971098191069184, 1464455092310590085718643732841733742751907840, 2931607239977985968431748709822882204673376256, 5071145896040416516787366422419680239143616512, 7646347111850023826450456204071859101005512704, 10118786775388847120260051117185219275494785024, 11816528202133548205621696332806618864141991936, 12229401727748031631818659990790313498501971968, 11254765177403555102856804336391379717707530240, 9234324482010946244665319763025233254291603456, 6767673709153420671927597792162356673862696960, 4436173482260458565336028699699262610783338496, 2602843046671490468971548052758391800916344832, 1367342905263875639636004918959223618232385536, 643003657409633230321576605500300635295186944, 270507118204762856360389026810254484104544256, 101696153623125200360036346713638389434810368, 34113204478736778850797428792685350692585472, 10189023297999354608056027069969087630147584, 2702074073350449081711171590360441294946304, 633461337394414246087085698520022161293312, 130250353878191987463513367903950520451072, 23128833424278681025085534066596674273280, 3452949067699202318393932302822441746432, 420090124033676242606632013694368743424, 41059197446043482140486255769601179648, 3249023692946127718031712394651107328, 209476599285191122293967597961478144, 10922104294863354540625286330843136, 447772314201573655309332531642368, 13419091148851424289823291080704, 197554737345233193361926520832, 3696322266437255629306331136]
[0.0042, 0.0042, 0.0043, 0.0044, 0.0046, 0.0048, 0.0052, 0.0056, 0.0061, 0.0067, 0.0076, 0.0086, 0.0099, 0.0115, 0.0137, 0.0165, 0.0202, 0.0252, 0.0321, 0.0416, 0.0552, 0.0750, 0.1043, 0.1486, 0.2165, 0.3222, 0.4877, 0.7461, 1.1426, 1.7309, 2.5600, 3.6576, 5.0367, 6.8603, 9.7399, 14.3015, 19.7488, 25.3869, 74.4129, 100.0000]

Второй вектор - оценки относительных погрешностей (среднеквадратичные, в процентах) чтобы было ясно о какой точности речь.
Это 10^9 семплов (полных проходов потвсем простым), хвосты попадают редко потому там дисперсия высокая.

[Yadryara]

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

хвосты попадают редко потому там дисперсия высокая.

Да это понятно. Я так и понял что у вас 38 чисел а не 42, потому что редкие не находятся. А сейчас 40 чисел. Но нужны как видим, первые 20, а то и меньше. И как раз начиная с 21-го числа СКО уходит выше 0.05%.

Я ещё буду перепроверять плотность для этого паттерна другим способом. Для очистки совести.

Скорее всего можно выдохнуть и монтекарлить уже тройки [0, 210, 420].

[Yadryara]

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

Я ещё буду перепроверять плотность для этого паттерна другим способом.

Сначала вычисляю среднюю плотность на отрезке в миллиард натуральных чисел на основании полученного и показанного выше результата в интервале 0 — 59#. Затем, ориентируясь на известную высоту в 35-36% этого интервала, сразу ищу кортежи в одном миллиарде:

3.72924e16 * 1e9 / 1.92276e21 ~ 19395

? w=n=0; sta = 0.35*1.92276e21; forprime(p=sta, sta + 10^9, if(p-w==210, n++); w=p; ); n
%7 = 19554
? w=n=0; sta = 0.36*1.92276e21; forprime(p=sta, sta + 10^9, if(p-w==210, n++); w=p; ); n
%8 = 19264

Здоровское совпадение.

Затем делаю то же самое для интервала 0 — 61#:

2.83759e18 * 1e9 / 1.17288e23 ~ 24193

?  w=n=0; sta = 0.35*1.17288e23; forprime(p=sta, sta + 10^9, if(p-w==210, n++); w=p; ); n
%9 = 24049
?  w=n=0; sta = 0.36*1.17288e23; forprime(p=sta, sta + 10^9, if(p-w==210, n++); w=p; ); n
%10 = 24016

Небольшой недобор.

[Yadryara]

И... тишина. Насколько я помню, Дмитрию этот точечный метод не нравился — предпочитал пройтись по всему диапазону, надёргивая группы кортежей по кусочкам с самых разных высот. Например вот так:

{sn=0;for(i=0,99, w=n=0; sta = i/100*1.92276e21; forprime(p=sta, sta + 1e7, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn))}

Но тогда должен получиться результат с недостатком.

Можно подсчитать вот так:

{sn=0;for(i=1,100, w=n=0; sta = i/100*1.92276e21; forprime(p=sta - 1e7, sta, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn))}

Но тогда должен получиться результат с избытком.

Так и есть, вот они два результата запусков:

19275
19452

И напрашиваются опять эти 35% :

{sn=0;for(i=0,99, w=n=0; sta = (i/100+0.0035)*1.92276e21; forprime(p=sta, sta + 1e7, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn))}

Но результат плохой: 19601

Чё-то не то. Возможно, всё-таки флуктуации мешают. Взял интервал вдвое больше:

{sn=0;for(i=0,99, w=n=0; sta = i/100*1.92276e21; forprime(p=sta, sta + 2e7, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\2))}

{sn=0;for(i=1,100, w=n=0; sta = i/100*1.92276e21; forprime(p=sta - 2e7, sta, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\2))}

{sn=0;for(i=0,99, w=n=0; sta = (i/100+0.0035)*1.92276e21; forprime(p=sta, sta + 2e7, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\2))}

Результаты:

19255
19462

19452

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

Увеличил интервал в 10 раз, до 100 миллионов:

{sn=0;for(i=0,99, w=n=0; sta = i/100*1.92276e21; forprime(p=sta, sta + 1e8, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\10))}

{sn=0;for(i=1,100, w=n=0; sta = i/100*1.92276e21; forprime(p=sta - 1e8, sta, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\10))}

{sn=0;for(i=0,99, w=n=0; sta = (i/100+0.0035)*1.92276e21; forprime(p=sta, sta + 1e8, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\10))}

19308
19485

19391

Ага! Попался голубчик! Напомню что средняя плотность, поcчитанная по прогнозу по HL1, с учётом Монте-Карло wresta была 19395 кортежей на миллиард.

Ну теперь посчитаю так же интервал 0 — 61#.

[wrest]

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

И... тишина.

Здесь же про ускорение говорим. Монте-Карло это ускорение (за счёт точности), а вы опять про кортежи и сколько их :)

[Yadryara]

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

Здесь же про ускорение говорим. Монте-Карло это ускорение (за счёт точности), а вы опять про кортежи и сколько их :)

Ну а что мне опять по темам скакать?

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

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

Т-а-а-к. Интересная задача всё-таки вырисовывается.

Она заключается не в поиске кортежа CPAP-7-210, а в оценке количества кортежей CPAP-x-210 для тех или иных интервалов, коль скоро посчитать эту оценку по HL1 представляется практически невозможным.

Но... там и ТС давненько не появляется и вообще народ молчит — я там целую страницу сам с собой разговаривал. Куда это годится.

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

wrest а что по поводу паттерна [0, 210, 420] ? Руки не дошли или не получается? Если не получается, выкладывайте наработки, подумаем вместе.

[Dmitriy40]

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

Ну а что мне опять по темам скакать?

Да - для этого и придуманы темы, чтобы не сваливать всё в одну кучу, а распределять по смыслу в разные (и более обозримые) кучки.
А так приходится всем остальным скакать по темам чтобы проследить один вопрос (типа поиска кортежей или оценки их количества/вероятностей), который Вы размазываете по разным темам. И во многие темы просто не придёт в голову заглянуть, ведь вопрос о вероятностях кортежей не связан с вопросом об ускорении программ.

[Yadryara]

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

Ну теперь посчитаю так же интервал 0 — 61#.

В два часа уложился. Средняя плотность на ярд была оценена вот так:

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

2.83759e18 * 1e9 / 1.17288e23 ~ 24193

И я сразу брал 100 млн:

sn=0;for(i=0,99, w=n=0; sta = i/100*1.17288e23; forprime(p=sta, sta + 1e8, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\10))

{sn=0;for(i=1,100, w=n=0; sta = i/100*1.17288e23; forprime(p=sta - 1e8, sta, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\10))}

{sn=0;for(i=0,99, w=n=0; sta = (i/100+0.0035)*1.17288e23; forprime(p=sta, sta + 1e8, if(p-w==210, n++); w=p; ); sn+=n; print(i, "   ", sn\10))}

24057
24265

24206

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

Видимо, вопрос с паттерном [0, 210] можно закрыть. 20 констант известно и теперь можно почитать ожидаемое количество кортежей для самых разных интервалов, разве что кроме самых маленьких.

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

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

ведь вопрос о вероятностях кортежей не связан с вопросом об ускорении программ.

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

[wrest]

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

а что по поводу паттерна [0, 210, 420] ? Руки не дошли или не получается?

Ну там надо посмотреть. Большие диаметры - большие структуры данных для промежуточного результата -> падение скорости.

[Dmitriy40]

(Оффтоп)

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

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

Ну тогда давайте будем обсуждать расчёт мат.ожиданий кортежей в теме физики твёрдого тела или в теме про квантовую механику - ведь чтобы что-то посчитать надо иметь компьютер, а он состоит из полупроводников, которые изучаются в ФТТ и КМ. Абсурд же.
Не надо путать цели и методы их достижения и разработку/улучшение этих методов.
Кортежи и вероятности это одно, а программы и их ускорение это другое.

[wrest]

Yadryara
0 210 420 готовятся.
Куда выкладывать? Я путаюсь в ваших кортежных темах.
Через какое-то время будет готова и сама программа (пока дописываю хелп, копирайт и т.п.), её тоже готов отдать.