问题描述
有没有快速算法,类似于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 -> 10I 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或除法算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!