高效的Modulo 3操作？

Question

可能重复:
快速模3或除法算法？

每个人都知道模运算可能是性能上的一个巨大缺点.有没有人知道x%3操作的好选择？我知道x%2存在一个,但我真的需要一个模3,因为我想在for循环中在三个缓冲区之间交替.

谢谢!

Answer 1

而不是通常的"衡量它"是一个真正的答案 - 因为那些东西实际上是真正有趣的数学.虽然编译器可以并且也可能这样做(至少现代优化c ++编译器,javac肯定不会,我不知道JVM是否这样做) - 所以最好检查它是否还没有完成工作您.

但是知道优化背后的理论仍然很有趣:我将使用汇编,因为我们需要乘法的32位字.以下内容来自沃伦关于比特小说的书:

n是我们想要模数的输入整数:

li M, 0x55555556   ; load magical number (2^32 + 2) / 3
mulhs q, M, n      ; q = higher word of M * n; i.e. q = floor(M*n / 2^32)
shri t, n, 31      ; add 1 to q if it is negative
add q, q, t

这里q包含n/3的除数,所以我们像往常一样计算余数: r = n - q*3

数学是有趣的部分 - 乳胶在这里会很酷:

q =楼层((2 ^ 32 + 2)/ 3*(n/2 ^ 32))=楼层(n/3 + 2*n /(3*2 ^ 32))

现在,对于n = 2 ^ 31-1(对于带符号的32位整数,最大n可能),误差项小于1/3(并且非负),这使得很容易证明结果确实是正确的.对于n = -2 ^ 31,我们有上面的校正1,如果你简化,你会发现误差项总是大于-1/3,这意味着它也适用于负数.

我留下了有关错误术语界限的证据 - 这并不难.

Answer 2

如果它是直接循环,则无需计算模数.保持第二个int var,每3步重置一次.

int i, bn = 0;

for(i=0; i<whatever; i++) {
  ...
  if(++bn == 3) bn = 0;
}

这不是一个过早的优化,它避免了不必要的计算.

编辑:在OP中声明他使用循环在缓冲区之间切换,所以我的解决方案看起来非常合适.至于downvote,如果是一个错误,没问题.

Answer 3

如果3在编译时已知,那么编译器将生成"技巧"以尽可能高效地完成.当除数在运行期间未知时,模数需要更长的时间.