快速模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.

这导致了下一个问题。什么是快速的方式在一些增加数字？即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 *一+ 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屋！