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

[Dmitriy40]

wrest
Спасибо.
Круто.
Я знал что более простой код может обогнать, главное нормальный язык (в данном случае С).

[Yadryara]

Пошёл пока в старый 2.15.4

Это какая-то фантастика:

1000000/189   1min, 32,875 ms
1000000/200         14,550 ms

[Dmitriy40]

Уменьшите интервал до 100тыс и выведите список найденных n (их будет по 19-20шт) и сравните два списка, они должны быть очень похожи. Я этого кажется так и не сделал.

[Yadryara]

factor:

6467627468614808795443546523718456286724685969
10855657655909537144302664881818184651275425169
17837782644434335974597318078551943146856055569
17953860816473813836607079365105605973730933969
19384879862288562657193820285109061930342577169
19573908347981309215091139060050204557506410769
43326346950683953152819762794766111859136666769
45041367532041930418402718087800070937627953169
49421139193262703820557584654761594041768621969
52556626259340931919271848023566857910792017169
70629034151179006957076184297672702774829409169
86848779360426522284226702093107834220207674769
95685861066562423865926354821606252040116895569
96086399581149238781082566691809207170005309969
100372574613531856120589246292537737322831847569
112355237139836375180308359023454780996710105169
123328524257101956309507808393035626176024202769
129427445762717684450597756148600210988861193169
131176876869383807327448427238043358652394439569

100000/19

8,912 ms

forprime:

6467627468614808795443546523718456286724685969
10855657655909537144302664881818184651275425169
17837782644434335974597318078551943146856055569
17953860816473813836607079365105605973730933969
19384879862288562657193820285109061930342577169
19573908347981309215091139060050204557506410769
43326346950683953152819762794766111859136666769
45041367532041930418402718087800070937627953169
49421139193262703820557584654761594041768621969
52556626259340931919271848023566857910792017169
58000830170093676229974723226119281245563981969
70629034151179006957076184297672702774829409169
86848779360426522284226702093107834220207674769
95685861066562423865926354821606252040116895569
96086399581149238781082566691809207170005309969
100372574613531856120589246292537737322831847569
112355237139836375180308359023454780996710105169
123328524257101956309507808393035626176024202769
131176876869383807327448427238043358652394439569

100000/19

1,435 ms

Появляется 580... , но исчезает 1294...

[Yadryara]

Менял разное, быстрее не стало. Ну вот один из вариантов.

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

\\Начало проверки конкретной цепочки 

nfac = vector(#v); \\ Кол-во факторов пока нулевое

ch = vector(#v,d,n+d-1);  \\ Частное пока равно цепочке-кандидату

forprime(p=59,2^20,

d=(n+#v-1)%p; if(d>=#v, next); d=#v-d; nfac[d]++; ch[d] \= p;

if(nfac[d] >nu[d]-1                                , next(2)); \\ Перебор
if(nfac[d]==nu[d]-1 && !ispseudoprime(ch[d]/v[d],1), next(2)); \\ Ровно  и составное
if(nfac[d] <nu[d]-1 &&  ispseudoprime(ch[d]/v[d],1), next(2)); \\ Меньше и простое
);
   kcep++;
   print(n);
);

[wrest]

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

Я знал что более простой код может обогнать, главное нормальный язык (в данном случае С).

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

[Yadryara]

Ещё можно весь nu[] сразу на единичку понизить, но это совсем копейки.

И непонятно что дальше делать. То ли пытаться рабочую программу исправлять. То ли эту тестовую затачивать под многопоточность.