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

[Yadryara]

wrest, я за то, чтобы выкладывать сюда.

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

который Вы размазываете по разным темам.

Я уже спрашивал недавно, вы специально выбираете в отношении меня такие не вполне благозвучные глаголы? Почему не сказать "распределяете"?

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

Не надо путать цели и методы их достижения и разработку/улучшение этих методов.

Не понял к чему это сказано, но это конечно оффтоп. Так что обсуждать здесь не буду.

Теперь дошли руки до идеи двукратного ускорения. Как назло, интересующие нынче паттерны CPAP-x-210 (я посмотрел пока только два первых), не поддаются простой процедуре уполовинивания.

НО. Оказывается я в позапрошлом году разработал ещё и поправку к основной. Есть надежда, что она универсальная. И ускорение — да, есть и пока не очень отличается от двукратного:

Это вывод для старой программы на PARI:

v = [0, 210]

C0 = 4.225
C1=855.271
C2=83679.269
C3=5271393.279
C4=240311097.230
C5=8448219702.517

[1, 104, 4131, 98804, 1608195, 19245540, 0, 0, 0, 0, 0]

6min, 13,257 ms

Вывод для новой программы отличается только временем счёта: 3min, 11,752 ms.

Ну вот теперь надо как-то с помощью ИИ попробовать переделать вашу асмовскую прогу, чтобы ускорить.

[wrest]

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

я за то, чтобы выкладывать сюда.

Ясно. Но я согласен с Dmitriy40

Соответственно, тема вот эта: «кортежи последовательных простых. ключ к 19-252» - Dmitriy40, верно?

[Dmitriy40]

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

Соответственно, тема вот эта: «кортежи последовательных простых. ключ к 19-252» - Dmitriy40, верно?

Нет, судя по названию там про 19-252 (правда потом там и другое вроде обсуждалось), а он найден и теперь кортежи совсем другие.
Я бы подумал про «Симметричные кортежи из последовательных простых чисел», но более новое обсуждение есть и в «Кортежи из простых чисел» (выделенной отсюда же), в ней кстати и аналогичные таблицы уже есть, и вообще она (кроме самого начала) как раз про такие кортежи, т.е. логично продолжать именно в ней.

[Yadryara]

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

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

Конечно логичней во второй, в новой теме, если уж не хотите здесь. И Дмитрий ещё не отметил, что ТС той первой большой темы не раз была против чтоб мы писали в ней.

[Dmitriy40]

(Кто там против чего)

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

ТС той первой большой темы не раз была против чтоб мы писали в ней.

На что было разъяснение модераторов что тема не является собственностью ТС (вот здесь приведена цитата администратора Toucan, ну что быстро нашёл) и в любой теме писать может кто угодно (если не нарушает Правила форума).
Так что против она или за - не колышит.
CPAP на 100% соответствуют термину "симметричные кортежи из последовательных простых чисел" и потому они точно в тематике той темы.

[Yadryara]

Что-то я опять утомился с ИИ пытаться. Вот дал ему медленную программу. 5 циклов без рекурсии.

(PARI)

{print; t0=getwalltime();

v=[0, 210];
print("v = ",v);print;


BC=vector(#v+10,k,
prodeulerrat(( p^k - k*p^(k-1) )/(p-1)^k, 1, nextprime(k+1)) );

MC=vector(#v+10,k, x=1.0;
forprime(p=3,k,x/=p*(1-1.0/p)^k); forprime(p=k+1,v[#v]/2,x/=p-k);x );

CC=vector(#v+10,k, 2^(k-1) * MC[k] * BC[k]);

a=setminus(vector(v[#v]/2,i,i*2),v);
C1=C2=C3=C4=C5=C6=C7=C8=C9=C10=0; nn=vector(10);

v0=vector(v[#v]/2,p,
if(p>2&&isprime(p),setminus(vector(p,i,i-1),Set(-v%p)),[]));

m0=vector(#v0,p, t=0;foreach(v0[p],x, t=bitor(t,2^x););t);

C0=CC[#v]; forprime(p=3,#m0, C0*=hammingweight(m0[p]); );
printf("C0 = %0.3f\n",C0);


for(i1=1,#a,
   forprime(p=3,#v+1, if(m0[p]==2^(-a[i1]%p), next(2)); );
   m1=m0; t=CC[#v+1];
forprime(p=3,#m1, m1[p]=bitnegimply(m1[p],2^(-a[i1]%p));
t*=hammingweight(m1[p]); ); C1 += t; nn[1]++;

   for(i2=1,i1-1,
      forprime(p=3,#v+2, if(m1[p]==2^(-a[i2]%p), next(2)); );
      m2=m1; t=CC[#v+2];
forprime(p=3,#m2, m2[p]=bitnegimply(m2[p],2^(-a[i2]%p));
t*=hammingweight(m2[p]); ); C2 += t; nn[2]++;

      for(i3=1,i2-1,
         forprime(p=3,#v+3, if(m2[p]==2^(-a[i3]%p), next(2)); );
         m3=m2; t=CC[#v+3];
forprime(p=3,#m3, m3[p]=bitnegimply(m3[p],2^(-a[i3]%p));
t*=hammingweight(m3[p]); ); C3 += t; nn[3]++;

         for(i4=1,i3-1,
            forprime(p=3,#v+4, if(m3[p]==2^(-a[i4]%p), next(2)); );
            m4=m3; t=CC[#v+4];
forprime(p=3,#m4, m4[p]=bitnegimply(m4[p],2^(-a[i4]%p)); 
t*=hammingweight(m4[p]); ); C4 += t; nn[4]++;

for(i5=1,i4-1,
forprime(p=3,#v+5, if(m4[p]==2^(-a[i5]%p), next(2)); );
m5=m4; t=CC[#v+5];
forprime(p=3,#m5, m5[p]=bitnegimply(m5[p],2^(-a[i5]%p));
t*=hammingweight(m5[p]); ); C5 += t; nn[5]++;

)))));


printf("C1 = %0.3f\n",C1);
printf("C2 = %0.3f\n",C2);
printf("C3 = %0.3f\n",C3);
printf("C4 = %0.3f\n",C4);
printf("C5 = %0.3f\n",C5);

/*
printf("C6=%0.3f\n",C6);
printf("C7=%0.3f\n",C7);
printf("C8=%0.3f\n",C8);
printf("C9=%0.3f\n",C9);
*/

print;
\\print(binomial(48)[1..10]);print();
\\obr=[1, 48, 667, 4766, 21826, 71186, 174310, 328658, 482192, 551548, 0];
\\print;
\\print(obr);
print(concat(1,nn));
print();


print();print(strtime(getwalltime()-t0));

print;
} quit;

Затем дал уже свой вариант, с двукратным уменьшением перебора, тоже 5 циклов и ещё 4 цикла в Поправке:

(PARI)

for(i1=1,#a/2,
   forprime(p=3,#v+1, if(m0[p]==2^(-a[i1]%p), next(2)); );
   m1=m0; t=CC[#v+1];
forprime(p=3,#m1, m1[p]=bitnegimply(m1[p],2^(-a[i1]%p));
t*=hammingweight(m1[p]); ); C1 +=t*2; nn[1]++;

   for(i2=i1+1,#a-i1,
      forprime(p=3,#v+2, if(m1[p]==2^(-a[i2]%p), next(2)); );
      m2=m1; t=CC[#v+2];
forprime(p=3,#m2, m2[p]=bitnegimply(m2[p],2^(-a[i2]%p));
t*=hammingweight(m2[p]); ); C2 +=t*2; nn[2]++;


      for(i3=i2+1,#a-i1,
         forprime(p=3,#v+3, if(m2[p]==2^(-a[i3]%p), next(2)); );
         m3=m2; t=CC[#v+3];
forprime(p=3,#m3, m3[p]=bitnegimply(m3[p],2^(-a[i3]%p));
t*=hammingweight(m3[p]); ); C3 +=t*2; nn[3]++;

         for(i4=i3+1,#a-i1,
\\ovc++;
            forprime(p=3,#v+4, if(m3[p]==2^(-a[i4]%p), next(2)); );
            m4=m3; t=CC[#v+4];
forprime(p=3,#m4, m4[p]=bitnegimply(m4[p],2^(-a[i4]%p));
t*=hammingweight(m4[p]); ); C4 +=t*2; nn[4]++;

for(i5=i4+1,#a-i1,
forprime(p=3,#v+5, if(m4[p]==2^(-a[i5]%p), next(2)); );
m5=m4; t=CC[#v+5];
forprime(p=3,#m5, m5[p]=bitnegimply(m5[p],2^(-a[i5]%p));
t*=hammingweight(m5[p]); ); C5 += t*2; nn[5]++;

)))));


nn*=2;


\\ Popravka

for(i1=1,#a/2,
   forprime(p=3,#v+1, if(m0[p]==2^(-a[i1]%p), next(2)); );
   m1=m0; t=CC[#v+1];
forprime(p=3,#m1, m1[p]=bitnegimply(m1[p],2^(-a[i1]%p));
t*=hammingweight(m1[p]); );

   i2=#a+1-i1;
      forprime(p=3,#v+2, if(m1[p]==2^(-a[i2]%p), next(2)); );
      m2=m1; t=CC[#v+2];
forprime(p=3,#m2, m2[p]=bitnegimply(m2[p],2^(-a[i2]%p));
t*=hammingweight(m2[p]); ); C2 +=t; nn[2]++;

      for(i3=i1+1,#a-i1,
         forprime(p=3,#v+3, if(m2[p]==2^(-a[i3]%p), next(2)); );
         m3=m2; t=CC[#v+3];
forprime(p=3,#m3, m3[p]=bitnegimply(m3[p],2^(-a[i3]%p));
t*=hammingweight(m3[p]); ); C3 += t; nn[3]++;

         for(i4=i3+1,#a-i1,
            forprime(p=3,#v+4, if(m3[p]==2^(-a[i4]%p), next(2)); );
            m4=m3; t=CC[#v+4];
forprime(p=3,#m4, m4[p]=bitnegimply(m4[p],2^(-a[i4]%p));
t*=hammingweight(m4[p]); ); C4 += t; nn[4]++;

for(i5=i4+1,#a-i1,
forprime(p=3,#v+5, if(m4[p]==2^(-a[i5]%p), next(2)); );
m5=m4; t=CC[#v+5];
forprime(p=3,#m5, m5[p]=bitnegimply(m5[p],2^(-a[i5]%p));
t*=hammingweight(m5[p]); ); C5 += t; nn[5]++;

))));

ИИ понятно за счёт чего перебор уменьшается почти вдвое, но он всё равно не может ускорить программу Дмитрия на асме ни на йоту!

[wrest]

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

но он всё равно не может ускорить программу Дмитрия на асме ни на йоту!

Видимо, она уже ускорена по самые помидоры?

[Yadryara]

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

Видимо, она уже ускорена по самые помидоры?

Нет, конечно не по самые. Вот фрагмент нашего разговора как раз об этом:

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

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

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

Потому что ненадёжен и когда снова сглючит неизвестно. Можно конечно проверять правильность первых 2-3 maxn, но нет гарантии что не сглючит на более заполненных паттернах (при больших maxn). И не понимаю как быстро убедиться что он не сглючил.
К тому же он лишь для симметричных паттернов, а текущий алгоритм может надёжно считать любые паттерны - что мне иногда надо.

[Dmitriy40]

Yadryara
А в C1 поправка что, не нужна? Тогда и t вычислять не нужно.

wrest
Да не, просто ИИ не смог перед командами fld faddp добавить команды fdup faddp fld faddp для прибавления удвоенного значения. Ну, код большой, поди найди там ещё эти команды ...
Ещё конечно пределы циклов в кажется трёх местах.
Это не считая "поправки".

[Yadryara]

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

А в C1 поправка что, не нужна?

Иногда нужна. Сейчас как раз с этим разбираюсь.

Это вроде бы эталон:

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

Паттерн      У р о в н и           з а г р я з н е н и я
             0     1     2     3     4     5     6     7
[0,  ]
    2        1
    4        1
    6        1     2
    8        1     2     1
   10        1     2     1
   12        1     5     6     2
   14        1     4     6     2
   16        1     4     6     4     1
   18        1     8     9    16     4
   20        1     6    15    20    11     2

Из этих паттернов, только для [0, 12] нужно поправить столбец 1 для быстрого способа, добавив 1.

Зато быстрый способ вроде правильно считает [0, 4], а медленная эталонная прога на нём вылетает по ошибке.

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

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

Из этих паттернов, только для [0, 12] нужно поправить столбец 1 для быстрого способа, добавив 1.

А ещё для [0, 24] и [0, 36] та же самая косметическая правка.