c - c 中的快速模 10

Question

我正在寻找一种快速的模 10 算法，因为我需要加快我的程序的速度，该程序在循环中执行许多模运算。

我已经 checkout this page它比较了一些替代方案。据我正确理解，T3 是最快的。我的问题是，x % y 使用 T3 技术会怎样？

为了简单起见，我在此处复制了 T3 技术，以防链接中断。

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

关于评论，如果这不是真的比常规模组快，我正在寻找比使用 % 至少快 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

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

注意缺少除法/取模指令、神秘的常量、使用最初用于复杂数组索引的指令等。不用说，编译器知道很多技巧可以让你的程序像可能的。在这样的任务中，您很少能打败它。