快速模3或除法算法？

Question

是否有一个类似于2的幂的快速算法，可以用于3，即n%3。也许有一些算法基于这样一个事实：如果数字的各位数字之和可被3整除，则该数字也可被3整除。

这引出了下一个问题：如何快速相加数字的各位数字？例如：37-> 3+7 -> 10。我正在寻找一些不含条件语句的方法，因为这些 tend 倾向于抑制向量化。

谢谢

- Anycorn

---

在这种情况下，添加数字是行不通的，因为你必须先将数字转换为十进制数，这比仅仅进行除法运算需要花费 更多 的时间。 - Georg Schölly

你实际上想要实现什么？除非这只是一些理论上的好奇心，否则我怀疑你所面临的这个具体问题可能不是真实世界应用的瓶颈... - Bruno Reis

它既具实际意义，又具有理论意义。问题源于尝试在多个嵌套的循环中将笛卡尔中心分配给线程（CUDA特定但不重要）。我已经用另一种方式解决了这个问题，但仍然想知道是否有其他方法。这是一个真正的瓶颈，因为整数除法和模运算比我试图并行化的实际浮点运算要昂贵得多。 - Anycorn

@Georg Schölly：为什么要使用十进制？你也可以在二进制中进行类似的操作，例如，十进制数13 = 0xB = 二进制数"1101"，模3余1，因为-1 + 1 - 0 + 1 = 1。这是被接受答案的基础，尽管我怀疑这不是最快的方法。 - maaartinus

Answer 1

4 % 3 == 1，因此(4^k * a + b) % 3 == (a + b) % 3。 您可以使用这个事实来计算32位x的x%3：

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要快吗？如果是这样，那么速度提升可能不会太大。

- Keith Randall

Answer 2

这个comp.compilers项目针对计算模3有一个具体的建议。

另一种选择，特别是如果被除数的最大值很小，就是将其乘以3的倒数作为定点值，精度足够处理最大尺寸的被除数来计算商，然后从被除数中减去3*商得到余数。所有这些乘法都可以用固定的移位和加法序列实现。指令的数量取决于倒数的位模式。当被除数的最大值较小时，这种方法效果很好。

关于数字相加...如果您想要添加十进制数字，则最终会执行类似于将数字转换为十进制的操作，其中包含除以10的操作。如果您愿意将数字以二进制形式相加，可以通过简单的右移和加循环来完成。各种巧妙的技巧可以用来在N位块中执行此操作，以进一步提高速度。

- Ira Baxter

Answer 3

如果你正在处理大整数，一个非常快速的方法是意识到所有的事实。

    bases 10 +/- multiple-of-3
i.e. 
    4,7,10,13,16,19,22…. etc

你所要做的就是数数字，然后取模 % 3。类似这样：

** note :  x ^ y is power, not bit-wise XOR,
          x ** y being the python equivalent
          
function mod3(__,_) { 
   #
   # can handle bases 
   #   { 4, 7,10,13,16,19,
   #       22,25,28,31,34 } w/o conversion
   # 
   # assuming base digits :
   #
   #    0-9A-X for any base,
   # or 0-9a-f for     base-16
   
   return \
   (length(__)<=+((_+=++_+_)+_^_)\
       && (__~"^[0-9]+$")  )\
   ? (substr(__,_~_,_+_*_+_)+\
        substr(__,++_*_--))%+_\
   :\
    (substr("","",gsub(\
   "[_\3-0369-=CFILORUXcf-~]+","",__))\
       +                  length(__) \
    + gsub("[258BbEeHKNQTW]","",__))%+_
}

这不是最快的方法，但它是更灵活的方法之一。

- RARE Kpop Manifesto

Answer 4

如果您对1字节整数除法感到满意，这里有一个技巧。您可以将其扩展到2字节、4字节等。

除法本质上是0.3333的乘法。如果您想模拟浮点运算，那么您需要找到最接近256（十进制）边界的近似值。这个值是85，因为85/256=0.332。所以如果您将您的值乘以85，您应该会在高8位中得到一个接近结果的值。

快速将值乘以85很容易。n*85=n*64+n*16+n*4+n。现在所有这些因子都是2的幂次方，因此您可以通过移位计算n*4，然后使用这个值来计算n*16等。因此您最多只需要5次移位和4次加法。

如前所述，这将给您带来近似值。要知道它有多好，您需要使用以下规则检查下一个值的低位。

n ... is the 16 bit number you want to divide
approx = HI(n*85)
if LO(n*85)>LO((n+1)*85)THEN approx++

这样就可以了。

示例1：

3 / 3 =?
3 * 85 = 00000000 11111111 (approx=0)
4 * 85 = 00000001 01010100 (LO(3*85)>LO(4*85)=>approx=1)
result approx=1

例子2：

254 / 3
254 * 85 = 01010100 01010110 (approx=84)
255 * 85 = 01010100 10101011 (LO(254*85)<LO(255*85), don't increase)
result approx=84

- Tomaz Stih

Answer 5

对于你的第一个问题不太确定，但是对于第二个问题，你可以利用%运算符和整数除法：

int num = 12345;
int sum = 0;
while (num) {
    sum += num % 10;
    num /= 10;
}

这段代码之所以有效，是因为 12345 % 10 = 5，12345 / 10 = 1234，并且一直重复这个过程，直到 num == 0。

- Austin Hyde

---

是的，那个解决方案显而易见。 然而，在我的平台上，除法和取模运算非常耗费时间，大约需要数百个周期。 我更感兴趣的是不涉及这些操作的解决方案。 我必须说，这只是一个纯粹出于好奇的问题。 - Anycorn