快速模3或除法算法? [英] Fast modulo 3 or division algorithm?

问题描述

有没有快速算法，类似于2的幂，可以和3一起使用，即n%3.也许是利用了这样一个事实:如果数字之和可以被三整除，那么这个数字也可以被整除.

is there a fast algorithm, similar to power of 2, which can be used with 3, i.e. n%3. Perhaps something that uses the fact that if sum of digits is divisible by three, then the number is also divisible.

这就引出了下一个问题.在数字中添加数字的快速方法是什么?IE.37 -> 3 +7 -> 10我正在寻找没有条件的东西，因为它们往往会抑制矢量化

This leads to a next question. What is the fast way to add digits in a number? I.e. 37 -> 3 +7 -> 10 I am looking for something that does not have conditionals as those tend to inhibit vectorization

谢谢

推荐答案

4 % 3 == 1, 所以 (4^k * a + b) % 3 == (a+ b) % 3.您可以使用这个事实来评估 x%3 是否为 32 位 x:

4 % 3 == 1, so (4^k * a + b) % 3 == (a + b) % 3. You can use this fact to evaluate x%3 for a 32-bit x:

x = (x >> 16) + (x & 0xffff);
x = (x >> 10) + (x & 0x3ff);
x = (x >> 6) + (x & 0x3f);
x = (x >> 4) + (x & 0xf);
x = (x >> 2) + (x & 0x3);
x = (x >> 2) + (x & 0x3);
x = (x >> 2) + (x & 0x3);
if (x == 3) x = 0;

(未经测试 - 您可能需要再减少一些.)这是否比您的硬件能够执行 x%3 更快?如果是的话，可能不会太多.

(Untested - you might need a few more reductions.) Is this faster than your hardware can do x%3? If it is, it probably isn't by much.

这篇关于快速模3或除法算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！