快速模数10 in c

Question

我正在寻找一个快速的模10算法,因为我需要加速我的程序,它在循环中进行许多模运算.

我查看了这个页面,比较了一些替代方案.据我所知,T3是最快的.我的问题是,x % y看起来如何使用T3技术？

为简单起见,我在这里复制了T3技术,以防链接出现故障.

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

关于评论,如果这不比常规mod快,我寻找的模数至少比使用模数快2倍%.我看过许多使用2的功能的例子,但由于10不是,我怎么能让它工作？

编辑:

对于我的程序,假设我有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

这是您可以编写的最快的modulo-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

注意缺少除法/模数指令,神秘的常量,最初用于复杂数组索引的指令的使用等.不用说,编译器知道很多技巧,使你的程序尽可能快.你很少会在这样的任务上击败它.