高效模3操作？ [英] Efficient Modulo 3 operation?

问题描述

可能重复：结果
  快速模3除法算法？

每个人都知道模运算可以对性能有巨大的缺陷。有谁知道X％3操作一个很好的选择吗？我知道，一个存在X％2，但我真的需要用于模3之一，因为我想在三个缓冲器之间交替循环。

Everyone knows that modulo arithmetic can be a huge drawback on performance. Does anyone know of a good alternative for x%3 operations? I know that one exists for x%2, but I really need one for modulo 3 since I want to alternate between three buffers in a for loop.

谢谢！

推荐答案

好，而不是通常的衡量的东西在实际的答案 - 因为那些东西其实是真正的趣味数学。虽然编译器可能也可能做到这一点，以及（至少在现代的优化C ++编译器，javac的肯定不会和我有不知道如果JVM做到这一点） - 所以最好先检查一下，如果它是不是已经在做的工作你。

Well instead of the usual "measure it" stuff an actual answer - because that stuff is actually real fun math. Although the compiler could and probably does this as well (at least modern optimizing c++ compilers, javac certainly won't and I've got no idea if the JVM does this) - so better check if it isn't already doing the work for you.

但仍然是有趣的了解优化背后的理论：因为我们需要一个乘法的32位越高的话，我会使用汇编。以下是沃伦的书上的位操作：

But still fun to know the theory behind the optimization: I'll use assembly because we need the higher 32bit word of a multiplication. The following is from Warren's book on bit twiddling:

n为整数输入我们想要从模：

n is the input integer we want the modulo from:

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

Here q contains the divisor of n / 3 so we just compute the remainder as usual: r = n - q*3

数学是有趣的部分 - 乳胶会相当棒的：

The math is the interesting part - latex would be rather cool here:

Q =楼（（2 ^ 32 + 2）/ 3 *（N / 2 ^ 32））=地板（N / 3 + 2 * N /（3 * 2 ^ 32））

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

现在当n = 2 ^ 31-1（最大的n个可能签署32位整数）的误差项小于1/3（非负），这使得它很容易证明的结果确实是正确的。对于n = -2 ^ 31，我们通过上面1有修正，如果你是简化你会看到误差项总是大于-1/3，这意味着它适用于负数为好。

Now for n = 2^31-1 (largest n possible for signed 32bit integers) the error term is less than 1/3 (and non negative) which makes it quite easy to show that the result is indeed correct. For n = -2^31 we have the correction by 1 above and if you simplify that you'll see that the error term is always larger than -1/3 which means it holds for negative numbers as well.

我留下有兴趣的误差项界的证明 - 这并不难

I leave the proof with the error term bounds for the interested - it's not that hard.

这篇关于高效模3操作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！