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

[Yadryara]

Пока не засекал. Интереснее, что если взять вот такие два сравнения по крошечным модулям:

{t0=getwalltime();print;
for(i=0,221*10^6-1,
if(i%13!=9 && i%17!=16, kpod++;
)); print(kpod);
print;print(strtime(getwalltime()-t0));print;
}quit;

и заменить в 3-й строке на длиннющую команду bittest по общему модулю

(Оффтоп)

if(bittest(0XDFFE7FF7BFBFDDFFEFFF77FBFBDFFCFFF6FFBF7DFFAFFF5FFBEFDFF, i%221), kpod++;

то всё равно с ней получается гораздо быстрее: 44 секунды против 58.

Время в программе для D(48,20) снизил до 300 секунд:

Интервал             Консоль               PARI         Last(cons)
10   млн            44.8 sec           49.4 sec           30.9 sec
100  млн      7min, 19.0 sec     7min, 26.1 sec     5min, 00.3 sec

Время работы старой программы, запущенной из консоли, на 46% больше.

[Dmitriy40]

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

то всё равно с ней получается гораздо быстрее: 44 секунды против 58.

Это да, быстрее, аж на четверть. Но экономия 14с - на 221млн проверок, на 100млн экономия сократится до 6.3с, из общих 300с, всего 2%.
И кстати заметьте, работа в цикле сократилась практически вдвое (одно деление вместо двух, остальные операции по идее существенно быстрее делений), а ускорение лишь на четверть, не вдвое.

-- 03.10.2025, 13:43 --

Я почему говорил что на разных языках оптимизации должны быть разными, например потому что замена деления на сложения/вычитания на асме (и вероятно С) значительное ускоряет, а на PARI замедляет:

? t0=getwalltime(); kpod=0; for(i=0,221*10^5-1, if(i%13!=9 && i%17!=16, kpod++); ); print(kpod,", time: ",strtime(getwalltime()-t0));
19200000, time: 5,854 ms
t0=getwalltime(); kpod=0; a=b=0; for(i=0,221*10^5-1, if(a!=9 && b!=16, kpod++); if(a++==13, a=0); if(b++==17, b=0); ); print(kpod,", time: ",strtime(getwalltime()-t0));
19200000, time: 12,471 ms

[Dmitriy40]

Для сравнения, тот же цикл на асме (тут только оболочка, вычисления покажу дальше в разных вариантах):

Используется синтаксис ASM

format PE64 console
include 'win64axp.inc'

.code
main:
frame
                invoke  GetTickCount            ;Запросим текущее время в мс
                mov     [time0],RAX
                invoke  GetStdHandle, STD_OUTPUT_HANDLE ;Получить handle консоли вывода
                mov     [hOut],RAX
                invoke  GetStdHandle, STD_ERROR_HANDLE  ;Получить handle консоли ошибок
                mov     [hErr],RAX
                mov     R15,0                   ;i
                mov     R14,0                   ;kpod
                mov     R13,0                   ;i%221
.cycle:

.next:          inc     R15
                mov     RAX,2210000000
                cmp     R15,RAX
                jc      .cycle
                invoke  GetTickCount            ;Запросим текущее время в мс
                add     RAX,1                   ;Нулевых интервалов времени работы недопускаем, лучше пусть будет погрешность
                sub     RAX,[time0]             ;Вычтем время старта, получим время работы в мс
                xor     RDX,RDX                 ;Старшее слово обнулим
                mov     RCX,1000                ;Будем делить EDX,EAX на 1000 (количество мс в секунде)
                div     RCX                     ;Поделим время на два числа, в секундах и мс
                mov     R9,RAX
                mov     R10,RDX
                cinvoke wsprintf, buf, .fmt1, R14, R9, R10
                invoke  WriteFile, dword [hErr], buf, RAX, temp, 0
                invoke  ExitProcess,0
endf
.fmt1:          db      '%I64u, time: %u.%03us',13,10,0
align 32
.mm:            dq      0xDFFAFFF5FFBEFDFF,0xBFBDFFCFFF6FFBF7,0x7BFBFDDFFEFFF77F,0xDFFE7FF

.data
align 32
time0:          rq      1
hOut:           rq      1
hErr:           rq      1
temp:           rq      1
buf:            rb      1000
.end main

В таком виде, вообще без вычислений в цикле, оно занимает 0.656с. Запускать из консоли без всяких параметров.
Обращаю особое внимание, тут и везде далее не 221млн итераций, а 2.21млрд!

Теперь добавляем между метками .cycle и .next первый вариант вычислений, с двумя делениями:

Используется синтаксис ASM

                mov     RAX,R15
                xor     RDX,RDX
                mov     RCX,13
                div     RCX
                cmp     RDX,9
                je      .next
                mov     RAX,R15
                xor     RDX,RDX
                mov     RCX,17
                div     RCX
                cmp     RDX,16
                je      .next
                inc     R14

Время будет 32.294s.

Меняем два деления на одно с bittest (вместо предыдущего текста добавляем этот):

Используется синтаксис ASM

                mov     RAX,R15
                xor     RDX,RDX
                mov     RCX,221
                div     RCX
                bt      [.mm],RDX
                jnc     .next
                inc     R14

Время становится 22.044с. Тоже не вдвое меньше.

Меняем деления на вычисление сразу остатка по модулю 221:

Используется синтаксис ASM

                inc     R13
                cmp     R13,221
                jc      @f
                mov     R13,0
@@:             lea     RAX,[R14+1]
                bt      [.mm],R13
                cmovc   R14,RAX

И время становится 6.834с.

А применение SSE/AVX2 позволит увеличить количество проверяемых модулей (до 16/32шт меньших 128 или до 8/16шт меньших 32768) вообще без битовой таблицы .mm и без удлинения кода.

[Yadryara]

Спасибо! Надо же без сучка и задоринки отработали все варианты кода:

0.             0, time:  0.517s
1.    1920000000, time: 26.329s
2.    1920000000, time: 12.735s
3.    1920000000, time:  2.126s

У меня эффект прям капитальный!

Теперь попытаюсь хоть чуть-чуть разобраться

[Yadryara]

Вроде бы понял, что из 4-х арифметических операций, деление (div) для проца самая медленная. И её нет в 3-м варианте. Но как сделано, не понял. Надо, видимо, потихоньку изучать команды.

[Dmitriy40]

Ещё вариант, промежуточный, 2.5, без делений, но с двумя остатками, надо дополнительно перед циклом обнулить R12 (в самом первом исходнике):

Используется синтаксис ASM

                inc     R12                     ;i%13
                cmp     R12,13
                jc      @f
                mov     R12,0
@@:             inc     R13                     ;i%17
                cmp     R13,17
                jc      @f
                mov     R13,0
@@:             cmp     R12,9
                je      .next
                cmp     R13,16
                je      .next
                inc     R14

Время всего 3.901с, быстрее третьего варианта! Потому что в том тормозят и bt и cmov.

-- 03.10.2025, 19:00 --

Ну и вариант на AVX2 проверки сразу всех модулей 5-53:

Используется синтаксис ASM

;Эту часть кода надо добавить перед меткой .cycle:
                vzeroupper
                vpxor           ymm0,ymm0,ymm0          ;Начальные значения остатков нулевые
                vpxor           ymm1,ymm1,ymm1          ;Начальные значения остатков нулевые
.cycle:
                lea     RAX,[R14+1]
                vpcmpeqb        ymm7,ymm0,[.noteq]      ;если i%p==no тогда FF, иначе 00
                vptest          ymm7,ymm7               ;все ли байты нулевые?
                cmovz   R14,RAX                         ;если да, т.е. все остатки допустимы, то обновим счётчик
                vpaddb          ymm0,ymm0,[.c1]         ;i++
                vpsubb          ymm7,ymm0,[.mods]       ;i-p
                vpminub         ymm0,ymm0,ymm7          ;(i++)%p

;Эту часть кода надо добавить сразу после метки .mm:
align 32
.c1:            db      32 dup(1)
.mods:          db      1,1,1,13,17,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1       ;На непроверяемых местах больше 1 не будет
.noteq:         db      7,7,7, 9,16,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7       ;И уж точно не будет там 7

В таком варианте, с проверкой только по модулям 13 и 17, отрабатывает за 2.513с.

Заменив константы инициализации на

Используется синтаксис ASM

.mods:          db      5,7,11,13,17,19,23,29,31,37,41,43,47,53,        1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1     ;На непроверяемых местах больше 1 не будет
.noteq:         db      3,0, 9, 9,16,13,20,22, 5,36,24, 8, 6,28,        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7     ;И уж точно не будет там 7

для обработки модулей 5-53, отрабатывает за те же 2.606с, зато оставляет вдвое меньше кандидатов, лишь 902257012 вместо 1920000000 во всех предыдущих вариантах.

Как видно осталось ещё 18 вакантных мест для проверки остатков по модулю, можно туда разместить например модули 59-79, каждого по три для контроля трёх запрещённых остатков, достаточно лишь заменить константы на:

Используется синтаксис ASM

.mods:          db      5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,59,59,61,61,61,67,67,67,71,71,71,73,73,73,79,79,79
.noteq:         db      3,0, 9, 9,16,13,20,22, 5,36,24, 8, 6,28,44,46,48,20,31,42,43,46,49,16,45,66,19,28,37, 3,18,50

получим то же время в 2.590с, однако осталось лишь 687198159 кандидатов из 2.21млрд.

Удвоив команды в цикле можно пофильтровать ещё по 9 модулям 83-127 (больше 128 для данного кода недопустимы) по трём запрещённым остаткам для каждого, что ещё немного улучшит фильтрацию:

Используется синтаксис ASM

                lea     RAX,[R14+1]
                vpcmpeqb        ymm7,ymm0,[.noteq]      ;если i%p==no тогда FF, иначе 00
                vpcmpeqb        ymm6,ymm1,[.noteq+32]   ;если i%p==no тогда FF, иначе 00
                vpor            ymm7,ymm7,ymm6
                vptest          ymm7,ymm7               ;все ли байты нулевые?
                cmovz   R14,RAX                         ;если да, т.е. все остатки допустимы, то обновим счётчик
                vpaddb          ymm0,ymm0,[.c1]         ;i++
                vpsubb          ymm7,ymm0,[.mods]       ;i-p
                vpminub         ymm0,ymm0,ymm7          ;(i++)%p
                vpaddb          ymm1,ymm1,[.c1]         ;i++
                vpsubb          ymm7,ymm1,[.mods+32]    ;i-p
                vpminub         ymm1,ymm1,ymm7          ;(i++)%p

;Это после метки .c1:
.mods:          db      5,7,11,13,17,19,23,29,31,37,41,43,47,53,        59,59,59, 61,61,61, 67,67,67, 71,71,71, 73,73,73, 79,79,79
                db      83,83,83, 89,89,89, 97,97,97, 101,101,101, 103,103,103, 107,107,107, 109,109,109, 113,113,113, 127,127,127,     1,1,1,1,1
.noteq:         db      3,0, 9, 9,16,13,20,22, 5,36,24, 8, 6,28,        44,46,48, 20,31,42, 43,46,49, 16,45,66, 19,28,37,  3,18,50
                db      16,57,78,  3,11,19, 55,59,63,  11, 39, 67,  13, 26, 71,  20, 75,101,  43, 90,105,   3, 44, 75,   2, 67, 98,     7,7,7,7,7

За время 3.355с оставит 524912534 кандидатов, менее четверти исходных, т.е. дальнейшим проверкам будет легче (они будут тупо реже запускаться).

Можно и ещё регистр остатков добавить, только команды с суффксом w (по 16 битов) вместо b (байтовые), в регистр влезает 5 модулей по три запрещённых остатка по каждому. Добавит ещё около секунды времени и ещё чуть улучшит фильтрацию (в $\prod\limits_{\substack{p\in P\\130<p<152}} \frac{p}{p-3} \approx=1.1135$ раза).

Напоминаю, все времена для 2.21млрд проверок, для 221млн времена надо делить на 10, а для 100млн делить на 22.

-- 03.10.2025, 19:00 --

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

Но как сделано, не понял.

Я рассчитывал что те уроки ассемблера не совсем забылись.
Смотрите:
inc R13 увеличивает текущее значение остатка по модулю 221, при этом он может стать и 221 тоже
cmp R13,221 как раз и проверяет не стал ли остаток равным 221 (это вычитание без сохранения результата, обновляет только флаги)
jc @f это обход следующей команды (условный переход на первую метку @@ ниже) если выставлен флаг переноса, т.е. число в R13 меньше 221 - т.е. нормальное по модулю 221
mov R13,0 обнуляет остаток по модулю 221 если он стал равным или больше 221
lea RAX,[R14+1] это замена двум командам mov RAX,R14 и inc RAX, просто так компактнее и так же быстро, это подготовка увеличенного значения счётчика R14 если таковое понадобится
bt [.mm],R13 это ровно bittest из PARI, в памяти по адресу .mm сидит битовый вектор, в R13 индекс (остаток по модулю 221, он не может быть больше 220), прочитанный бит возвращается в флаге переноса CF
cmovc R14,RAX это условное копирование, если флаг переноса CF=1, то RAX (где лежит подготовленное значение R14++, вот и пригодилось) копируется в R14 обновляя его на большее значение
всё.
Первые 4 команды дополнительно к основному счётчику i в R15 организуют дополнительный счётчик в R13 величины i%221.
Последние 3 команды реализуют операцию if(bittest(.mm, R13), R14++); в синтаксисе PARI.

-- 03.10.2025, 19:09 --

Заметьте, начиная с 2.5 и 3 вариантов, нигде в цикле не используется R15, т.е. вся работа идёт только по малым модулям, в арифметике по модулю. А значит совершенно не важно сколь большое i в R15, хоть 20 цифр в нём, главное правильно выставить начальное значение остатков по простым модулям до начала цикла и всё, потом будет работать как есть и с той же скоростью, без всяких модификаций, для абсолютно любого интервала (в пределах $2^{64}$, что легко решается увеличением разрядности i, тогда можно будет для счётчика количества итераций завести отдельный регистр, всё равно 1.8e19 итераций выполнить нереально, а столько в регистр влезает).

-- 03.10.2025, 19:21 --

И я кстати ошибся в 2.5 и 3 вариантах, надо сначала выполнить проверку, а потом уж увеличивать остаток. Сейчас начальный остаток не проверяется, зато проверяется 2210000000, чего не нужно.
Но на время не влияет, только на коэффициент фильтрации (максимум плюс-минус 2шт). Так что исправлять специально не буду (хотя достаточно инициализировать R12 и R13 значением -1 вместо 0), всё равно это лишь тесты.

-- 03.10.2025, 19:32 --

Ускорение у меня не совпадает с Вашим вероятно по причине запущенных фоновых процессов у меня, даже мышка дёрганно движется, хоть вроде половина ядер и свободна, но то ли винда, то ли диск, то ли кэш проца, то ли память переполнилась и пошёл своп, но кто-то явно гадит. А прерывать фоновые процессы я не хочу. Так что Ваши цифры должны быть точнее (и повторяемее) моих.

[Yadryara]

2.5 у меня проиграл 3-му. На всякий случай 2 раза запускал.

0.               0, time:  0.517s      
1.      1920000000, time: 26.329s     
2.      1920000000, time: 12.735s     
3.      1920000000, time:  2.126s     
3.     19200000000, time: 21.219s   
2.5    19200000000, time: 24.548-907s
4.     19200000000, time: 15.485s

Зачем нужно меньшее количество остатков получать, пока не понял.

[Dmitriy40]

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

Зачем нужно меньшее количество остатков получать, пока не понял.

А я этого не понял. Вы про объединение модулей? Да, когда используем bt/bittest битовую маску (огромное число) можно сделать достаточно большой, пока в память влезает (12ГБ это более 103млрд битов). Это 2 и 3 варианты, там же можно модуль и не 221 взять, а вплоть до сотни миллиардов ...
Но больше десятка мегабайт маску делать не слишком выгодно - не поместится в кэш L3 процессора и будет читаться из памяти, а это в десятки раз медленнее. И команда bt вместо десятка тактов может выполняться и сотни тактов (30-50нс, время произвольной выборки из памяти, а если будет ещё и промах страничных кэшей, то время станет ещё в разы больше, сотни нс и тысячи тактов).
А SSE/AVX не умеет работать с битовыми масками, во всяком случае длиннее 128 битов, да и с такими не быстро. Зато AVX позволяет проверять за ровно то же время 32 остатка (меньших 128, или 16 меньших 32768) вместо 1, что улучшает коэффициент фильтрации без замедления вычислений. Потому для SSE/AVX выгоднее много маленьких модулей чем мало больших.

[Yadryara]

Я имел в виду, что закончили пытаться ускорить нахождение 192 остатков по модулю 221? 4-й вариант признан самым быстрым и неулучшаемым? Да, 284-хкратное ускорение — это очень круто.

Но есть же ещё вариант спросить mihaild. Можете попробовать на графическом проце (забыл как он называется) ?

[Dmitriy40]

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

Я имел в виду, что закончили пытаться ускорить нахождение 192 остатков по модулю 221? 4-й вариант признан самым быстрым и неулучшаемым?

4-й вариант это с AVX. Нет, его тоже можно улучшить: например проверять одновременно 16 значений i+0...i+15, ведь из 32 мест заняты лишь 2, можно продублировать 16 раз, а цикл пойдёт с шагом 16. Это ускоряет 22.1млрд с 69с v3 и 26с v4 до 1.9с v5, почти в 14 раз быстрее v4. Код (только отличия от нулевого):

Используется синтаксис ASM

                vzeroupper
                vmovdqu         ymm0,[.c0]              ;Начальные значения остатков
.cycle:
                vpcmpeqb        ymm7,ymm0,[.noteq2]     ;если i%p==no тогда FF, иначе 00
                vpmovmskb       EBX,ymm7                ;В EAX биты из старшего бита каждого байта из ymm7
                mov     EAX,EBX
                shr     EAX,16
                or      EAX,EBX                         ;Объединяем по or старшую и младшую половину битовой маски (запрет по 13 и по 17)
                not     EAX                             ;Инвертируем, теперь 1 отвечает подходящим значениям
                and     EAX,0xFFFF                      ;Выделяем только младшие 16 битов
                popcnt  EAX,EAX                         ;Подсчитываем количество единичных битов, т.е. подходящих i
                add     R14,RAX                         ;Добавляем к счётчику
                vpaddb          ymm0,ymm0,[.c2]         ;i++
                vpsubb          ymm7,ymm0,[.mods2]      ;i-p
                vpminub         ymm0,ymm0,ymm7          ;(i++)%p
.next:          add     R15,16

;Это добавить после строки с меткой .fmt1
align 32
.c0:            db      2 dup(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)    ;Начальные значения остатков
.c2:            db      16 dup( 3), 16 dup(16)  ;Приращение остатков на каждую итерацию по 16 значений i, здесь первое число не 16, а 16%13=3
.mods2:         db      16 dup(13), 16 dup(17)  ;Модули
.noteq2:        db      16 dup( 9), 16 dup(16)  ;Запрещённые остатки

Но как видите здесь уже не осталось места другим проверкам, если делать проверку битов в EAX, это будет медленнее одной popcnt.

Потом можно частично развернуть цикл, ведь из 13-ти последовательных значений i недопустимо ровно одно, можно это реализовать вообще без проверок, чисто кодом, повторить его 12 раз вместо 13-ти. Тем более что мы в данном тесте точно знаем начальное значение i, а значит точно знаем какое повторение надо выкинуть. И даже если бы не знали, для любого начального остатка, это делается входом не в начало развернутого цикла, а куда-то в середину в зависимости от начальной величины остатка.
Можно и 221 раз развернуть, останется 192 повтора, причём одной команды inc R14. Которое разумеется оптимизируется до одного повтора команды add R14,192. Ускорение будет бешеным.
Это намёк что оптимизировать столь простой код (одна R14++) нет большого смысла, надо добавлять остальные проверки и оптимизировать уже с учётом их наличия.

Можно многопоточно сделать, в том числе и на GPU.

[Dmitriy40]

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

Это ускоряет 22.1млрд с 69с v3 и 26с v4 до 1.9с v5

Зацените, это ж 11млрд/с, втрое выше частоты моего процессора! Т.е. по три числа за такт (команду). В одном потоке. Вот что векторизация может. И это код без сильной оптимизации, буквально первый правильно заработавший.
И если бы коэффициент фильтрации был высок, хотя бы десятки, можно было бы использовать накопленную битовую маску (вместо popcnt) и кардинально реже запускать следующие проверки. А так, за 100 простых (а это обработка 18 AVX регистров остатков раз в 10-15 медленнее 4 варианта) он едва перевалил за 9.0.

[Yadryara]

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

Зацените, это ж 11млрд/с, втрое выше частоты моего процессора!

А у меня примерно такая же частота, а время ещё более фантастическое: в 3400 раз быстрее чем лучший запуск на PARI.

4.     19200000000, time: 15.485s
5.      1920000000, time:  0.095s
5.     19200000000, time:  1.016s
5.    192000000000, time: 10.251s

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

Можно многопоточно сделать, в том числе и на GPU.

А у кого из форумчан есть этот проц?

[Yadryara]

Ну вот, пожалуйста. Чайник в своём репертуаре

В самом быстром 5-м варианте проги решил перейти к более простому варианту: искать не 192 разрешённых остатка по модулю 221, а 24 разрешённых остатка по модулю 35. Вроде во всех строках, где играли старые числа, аккуратно исправил их на новые:

Используется синтаксис ASM

format PE64 console
include 'INCLUDE\win64axp.inc'

.code
main:
frame
                invoke  GetTickCount            ;Запросим текущее время в мс
                mov     [time0],RAX
                invoke  GetStdHandle, STD_OUTPUT_HANDLE ;Получить handle консоли вывода
                mov     [hOut],RAX
                invoke  GetStdHandle, STD_ERROR_HANDLE  ;Получить handle консоли ошибок
                mov     [hErr],RAX
                mov     R15,0                   ;i
                mov     R14,0                   ;kpod
                mov     R13,0                   ;i%221

                vzeroupper
                vmovdqu         ymm0,[.c0]              ;Начальные значения остатков
.cycle:
                vpcmpeqb        ymm7,ymm0,[.noteq2]     ;если i%p==no тогда FF, иначе 00
                vpmovmskb       EBX,ymm7                ;В EAX биты из старшего бита каждого байта из ymm7
                mov     EAX,EBX
                shr     EAX,16
                or      EAX,EBX                         ;Объединяем по or старшую и младшую половину битовой маски (запрет по 13 и по 17)
                not     EAX                             ;Инвертируем, теперь 1 отвечает подходящим значениям
                and     EAX,0xFFFF                      ;Выделяем только младшие 16 битов
                popcnt  EAX,EAX                         ;Подсчитываем количество единичных битов, т.е. подходящих i
                add     R14,RAX                         ;Добавляем к счётчику
                vpaddb          ymm0,ymm0,[.c2]         ;i++
                vpsubb          ymm7,ymm0,[.mods2]      ;i-p
                vpminub         ymm0,ymm0,ymm7          ;(i++)%p

.next:          add     R15,16

                                                        ;inc     R15

                mov     RAX,35000000000
                cmp     R15,RAX
                jc      .cycle
                invoke  GetTickCount            ;Запросим текущее время в мс
                add     RAX,1                   ;Нулевых интервалов времени работы не допускаем, лучше пусть будет погрешность
                sub     RAX,[time0]             ;Вычтем время старта, получим время работы в мс
                xor     RDX,RDX                 ;Старшее слово обнулим
                mov     RCX,1000                ;Будем делить EDX,EAX на 1000 (количество мс в секунде)
                div     RCX                     ;Поделим время на два числа, в секундах и мс
                mov     R9,RAX
                mov     R10,RDX
                cinvoke wsprintf, buf, .fmt1, R14, R9, R10
                invoke  WriteFile, dword [hErr], buf, RAX, temp, 0
                invoke  ExitProcess,0
endf
.fmt1:          db      '%I64u, time: %u.%03us',13,10,0
align 32
.c0:            db      2 dup(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)    ;Начальные значения остатков
.c2:            db      16 dup( 1), 16 dup( 2)  ;Приращение остатков на каждую итерацию по 16 значений i, здесь первое число не 16, а 16%5=1
.mods2:         db      16 dup( 5), 16 dup( 7)  ;Модули
.noteq2:        db      16 dup( 3), 16 dup( 0)  ;Запрещённые остатки

align 32
.mm:            dq      0x5EF5B9E76

.data
align 32
time0:          rq      1
hOut:           rq      1
hErr:           rq      1
temp:           rq      1
buf:            rb      1000
.end main
 

Возможно ещё сыграло роль то, что запрещённый остаток 16, а это степень двойки, специфическое число. Например, вот здесь

shr EAX,16

16 это потому что запрещённый остаток 16 или потому что 16 бит надо было указать. Если надо заменить, то на что, на 3 или на 0...

Или здесь

Цитата:

.c2: db 16 dup( 3), 16 dup(16) ;Приращение остатков на каждую итерацию по 16 значений i, здесь первое число не 16, а 16%13=3

И что надо сделать было? 16%5=1, то есть единичку 16 dup( 1), вместо 3-ки? Попробовал — не сходится.

А, кажется просёк. Надо сделать 16 dup( 3), 16 dup(2), потому что сама последняя 16-ка это 16%17. А надо взять 16%7.

Но всё равно, ошибка на 5:

24000000005,  time:  1.610s
240000000005, time: 16.235s

Надо вникать тщательнее. Буду асмовскую тему перечитывать.

[Dmitriy40]

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

Вроде во всех строках, где играли старые числа, аккуратно исправил их на новые:

Насколько вижу всё правильно, поменять надо лишь константы .c2, .mods2, .noteq2 (и .c0, см. ниже). Кстати значения в .noteq2 можно указывать любые, пока интервал 35млрд кратен общему модулю 35 разницы в количестве не будет, только в самих значениях i дающих вклад в результат.

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

Возможно ещё сыграло роль то, что запрещённый остаток 16, а это степень двойки, специфическое число. Например, вот здесь
shr EAX,16
16 это потому что запрещённый остаток 16 или потому что 16 бит надо было указать. Если надо заменить, то на что, на 3 или на 0...

Здесь это не остаток, а длина каждого из двух битового поля из регистра AVX и он же шаг проверки, тут менять не нужно.

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

Но всё равно, ошибка на 5:

Проблема в том, что .c0 тоже должна быть по модулям 13 и 17 или 5 и 7. Т.е. ошибка и у меня тоже, привык к шагам меньше модулей и забыл что 16>13, просто она не проявилась при данном .noteq2 (при некотором другом - проявилась бы).
Вам надо указать:
.c0: db 0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0, 0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1 ;[0..15]%5, [0..15]%7
и всё станет корректно.

Кроме того, если указывать длину интервала не кратно 16, например 35000, тоже будет ошибка, будет проверено больше чисел, до границы кратной 16 вверх. Это плата за векторизацию на 16 (проверке сразу 16 значений i). Если нужен точный результат - надо проверять до кратной 16 границы снизу, а остаток - не векторно (любым способом, таких i ведь не более 15 штук, это быстро даже с кучей делений).

[Yadryara]

Теперь попытался объединить три младших модуля. Должно быть 240 из 385. Но не сошлось, получилось 264:

Используется синтаксис ASM

format PE64 console
include 'INCLUDE\win64axp.inc'

.code
main:
frame
                invoke  GetTickCount            ;Запросим текущее время в мс
                mov     [time0],RAX
                invoke  GetStdHandle, STD_OUTPUT_HANDLE ;Получить handle консоли вывода
                mov     [hOut],RAX
                invoke  GetStdHandle, STD_ERROR_HANDLE  ;Получить handle консоли ошибок
                mov     [hErr],RAX
                mov     R15,0                   ;i
                mov     R14,0                   ;kpod
                mov     R13,0                   ;i%385

                vzeroupper
                vmovdqu         ymm0,[.c0]              ;Начальные значения остатков
.cycle:
                vpcmpeqb        ymm7,ymm0,[.noteq2]     ;если i%p==no тогда FF, иначе 00
                vpmovmskb       EBX,ymm7                ;В EAX биты из старшего бита каждого байта из ymm7
                mov     EAX,EBX
                shr     EAX,16
                or      EAX,EBX                         ;Объединяем по or старшую и младшую половину битовой маски (запрет по модулям)
                not     EAX                             ;Инвертируем, теперь 1 отвечает подходящим значениям
                and     EAX,0xFFFF                      ;Выделяем только младшие 16 битов
                popcnt  EAX,EAX                         ;Подсчитываем количество единичных битов, т.е. подходящих i
                add     R14,RAX                         ;Добавляем к счётчику
                vpaddb          ymm0,ymm0,[.c2]         ;i++
                vpsubb          ymm7,ymm0,[.mods2]      ;i-p
                vpminub         ymm0,ymm0,ymm7          ;(i++)%p

.next:          add     R15,16

                                                        ;inc     R15

                mov     RAX,38500000000
                cmp     R15,RAX
                jc      .cycle
                invoke  GetTickCount            ;Запросим текущее время в мс
                add     RAX,1                   ;Нулевых интервалов времени работы не допускаем, лучше пусть будет погрешность
                sub     RAX,[time0]             ;Вычтем время старта, получим время работы в мс
                xor     RDX,RDX                 ;Старшее слово обнулим
                mov     RCX,1000                ;Будем делить EDX,EAX на 1000 (количество мс в секунде)
                div     RCX                     ;Поделим время на два числа, в секундах и мс
                mov     R9,RAX
                mov     R10,RDX
                cinvoke wsprintf, buf, .fmt1, R14, R9, R10
                invoke  WriteFile, dword [hErr], buf, RAX, temp, 0
                invoke  ExitProcess,0
endf
.fmt1:          db      '%I64u, time: %u.%03us',13,10,0
align 32
.c0:            db      0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0, 0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1, 0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4 ;[0..15]%5, [0..15]%7, [0..15]%11
.c2:            db      16 dup( 1), 16 dup( 2), 16 dup( 5)  ;Приращ ост на каждую ит по 16 знач i, здесь 16%5=1, 16%7=2, 16%11=5
.mods2:         db      16 dup( 5), 16 dup( 7), 16 dup(11)  ;Модули
.noteq2:        db      16 dup( 3), 16 dup( 0), 16 dup( 9)  ;Запрещённые остатки

align 32
.mm:            dq      0x7ADCF3B56F4B9C76,0xB73CED79D6A795AE,0xCD3B1EF5B8E74BDA,0xC6D6BD4E79DA77AD,0x95EB5B1E66BDEB33,0x7BC6E59DAF72DCF3,0x1

.data
align 32
time0:          rq      1
hOut:           rq      1
hErr:           rq      1
temp:           rq      1
buf:            rb      1000
.end main