Быстрая по модулю 10 в с

Question

Я ищу быстрый алгоритм по модулю 10, потому что мне нужно ускорить мою программу, которая выполняет много операций по модулю в циклах.

Я проверил эту страницу , которая сравнивает некоторые альтернативы. Насколько я правильно понимаю, Т3 был самым быстрым из всех. У меня вопрос, как бы x % y выглядело бы, используя технику Т3?

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

for (int x = 0; x < max; x++)
{
        if (y > (threshold - 1))
        {
               y = 0; //reset
               total += x;
        }
        y += 1;
}

Что касается комментариев, если это на самом деле не быстрее, чем обычный мод, я ищу по крайней мере в 2 раза быстрее по модулю, чем при использовании %. Я видел много примеров с использованием степени двойки, но поскольку 10 нет, как я могу заставить его работать?

Edit:

Для моей программы, скажем, у меня есть 2 для циклов, где n=1 000 000 и m=1000.

выглядит так:

for (i = 1; i <= n; i++) {
        D[(i%10)*m] = i;
        for (j = 1; j <= m; j++) {
           ...
        }
}

Answer 1

Это будет работать для значений (с несколькими словами) больше, чем машинное слово (но при условии двоичного компьютера ...):

---

#include <stdio.h>

unsigned long mod10(unsigned long val)
{
unsigned res=0;

res =val &0xf;
while (res>=10) { res -= 10; }

for(val >>= 4; val; val >>= 4){
        res += 6 * (val&0xf);
        while (res >= 10) { res -= 10; }
        }

return res;
}

int main (int argc, char **argv)
{
unsigned long val;
unsigned res;

sscanf(argv[1], "%lu", &val);

res = mod10(val);
printf("%lu -->%u\n", val,res);

return 0;
}

---

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

---

static unsigned long mod10_1(unsigned long val)
{
unsigned char res=0; //just to show that we don't need a big accumulator

res =val &0xf; // res can never be > 15
if (res>=10) { res -= 10; }

for(val >>= 4; val; val >>= 4){
        res += (val&0xf)<<2 | (val&0xf) <<1;
        res= mod10_1(res); // the recursive call
        }

return res;
}

---

И результат для mod10_1 выглядит как mul / div свободным и почти без ветвей:

---

mod10_1:
.LFB25:
    .cfi_startproc
    movl    %edi, %eax
    andl    $15, %eax
    leal    -10(%rax), %edx
    cmpb    $10, %al
    cmovnb  %edx, %eax
    movq    %rdi, %rdx
    shrq    $4, %rdx
    testq   %rdx, %rdx
    je      .L12
    pushq   %r12
    .cfi_def_cfa_offset 16
    .cfi_offset 12, -16
    pushq   %rbp
    .cfi_def_cfa_offset 24
    .cfi_offset 6, -24
    pushq   %rbx
    .cfi_def_cfa_offset 32
    .cfi_offset 3, -32
.L4:
    movl    %edx, %ecx
    andl    $15, %ecx
    leal    (%rcx,%rcx,2), %ecx
    leal    (%rax,%rcx,2), %eax
    movl    %eax, %ecx
    movzbl  %al, %esi
    andl    $15, %ecx
    leal    -10(%rcx), %r9d
    cmpb    $9, %cl
    cmovbe  %ecx, %r9d
    shrq    $4, %rsi
    leal    (%rsi,%rsi,2), %ecx
    leal    (%r9,%rcx,2), %ecx
    movl    %ecx, %edi
    movzbl  %cl, %ecx
    andl    $15, %edi
    testq   %rsi, %rsi
    setne   %r10b
    cmpb    $9, %dil
    leal    -10(%rdi), %eax
    seta    %sil
    testb   %r10b, %sil
    cmove   %edi, %eax
    shrq    $4, %rcx
    andl    $1, %r10d
    leal    (%rcx,%rcx,2), %r8d
    movl    %r10d, %r11d
    leal    (%rax,%r8,2), %r8d
    movl    %r8d, %edi
    andl    $15, %edi
    testq   %rcx, %rcx
    setne   %sil
    leal    -10(%rdi), %ecx
    andl    %esi, %r11d
    cmpb    $9, %dil
    seta    %bl
    testb   %r11b, %bl
    cmovne  %ecx, %edi
    andl    $1, %r11d
    andl    $240, %r8d
    leal    6(%rdi), %ebx
    setne   %cl
    movl    %r11d, %r8d
    andl    %ecx, %r8d
    leal    -4(%rdi), %ebp
    cmpb    $9, %bl
    seta    %r12b
    testb   %r8b, %r12b
    cmovne  %ebp, %ebx
    andl    $1, %r8d
    cmovne  %ebx, %edi
    xorl    $1, %ecx
    andl    %r11d, %ecx
    orb     %r8b, %cl
    cmovne  %edi, %eax
    xorl    $1, %esi
    andl    %r10d, %esi
    orb     %sil, %cl
    cmove   %r9d, %eax
    shrq    $4, %rdx
    testq   %rdx, %rdx
    jne     .L4
    popq    %rbx
    .cfi_restore 3
    .cfi_def_cfa_offset 24
    popq    %rbp
    .cfi_restore 6
    .cfi_def_cfa_offset 16
    movzbl  %al, %eax
    popq    %r12
    .cfi_restore 12
    .cfi_def_cfa_offset 8
    ret
.L12:
    movzbl  %al, %eax
    ret
    .cfi_endproc
.LFE25:
    .size   mod10_1, .-mod10_1
    .p2align 4,,15
    .globl  mod10
    .type   mod10, @function

Answer 2

Вы, вероятно, не можете победить компилятор.

Отладочная сборка

//     int foo = x % 10;
010341C5  mov         eax,dword ptr [x]  
010341C8  cdq  
010341C9  mov         ecx,0Ah  
010341CE  idiv        eax,ecx  
010341D0  mov         dword ptr [foo],edx  

Розничная сборка (где-то там работает ниндзя ...)

//    int foo = x % 10;
00BD100E  mov         eax,66666667h  
00BD1013  imul        esi  
00BD1015  sar         edx,2  
00BD1018  mov         ecx,edx  
00BD101A  shr         ecx,1Fh  
00BD101D  add         ecx,edx  
00BD101F  lea         eax,[ecx+ecx*4]  
00BD1022  add         eax,eax  
00BD1024  sub         esi,eax

Answer 3

Вот самая быстрая функция по модулю-10, которую вы можете написать:

unsigned mod10(unsigned x)
{
    return x % 10;
}

А вот как это выглядит после компиляции:

movsxd rax, edi
imul rcx, rax, 1717986919
mov rdx, rcx
shr rdx, 63
sar rcx, 34
add ecx, edx
add ecx, ecx
lea ecx, [rcx + 4*rcx]
sub eax, ecx
ret

Обратите внимание на отсутствие инструкций деления / модуля, загадочные константы, использование инструкции, которая изначально предназначалась для индексации сложных массивов, и т. Д. Излишне говорить, что компилятор знает множество хитростей, позволяющих сделать вашу программу настолько быстрой, насколько это возможно. возможный. Ты редко победишь его на таких задачах.

Answer 4

Код не является прямой заменой по модулю, он заменяет по модулю в этой ситуации . Вы можете написать свой mod по аналогии (для a, b> 0):

int mod(int a, int b) {
    while (a >= b) a -= b;
    return a;
}

... но сомнительно ли это быстрее, чем % .