快速模3或除法算法？

是否有快速算法，类似于2的幂，其可以与3一起使用，即n％3。也许有些事情，如果数字的总和可以被三整除，那么这个数字也是可以被整除的。快速模3或除法算法？

这导致下一个问题。在数字中添加数字的快速方法是什么？即37 - > 3 +7 - > 10 我要寻找的东西，没有条件语句那些倾向于抑制量化

感谢

2009-11-08 Anycorn

在这种情况下添加数字将不起作用，因为您必须先将数字转换为十进制数字，而不是仅仅分割多一点的时间。 – 2009-11-08 18:01:42

你究竟在做什么？除非有一些理论上的好奇心，否则我怀疑这个具体的问题可能是真实世界应用的瓶颈...... – 2009-11-08 18:01:54

它既实用又理论。这个问题来自于尝试在线程之间分配多个嵌套在笛卡尔中心上的循环（Cuda具体但并不重要）。我已经用另一种方式解决了这个问题，但仍然想知道是否有办法。这是一个真正的瓶颈，因为整数除法和模数比我试图进行的实际浮点运算要昂贵得多。 – Anycorn 2009-11-08 18:18:36

4 % 3 == 1，所以(4^k * a + b) % 3 == (a + b) % 3。你可以利用这一点来评估X％3的32位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？如果是这样，它可能不是太多。

来源

2009-11-08 18:22:39

这真的比'x％3'快吗？请参阅https://godbolt.org/g/aRbqrW – plasmacel 2017-07-27 20:06:06

不知道你的第一个问题，但对于你的第二个，你可以采取优势%运营商和整数除法：

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

这工作，因为12345 % 10 = 5，12345/10 = 1234和继续下去，直到num == 0

来源

2009-11-08 18:14:57

+1尼斯＃2。解。 – 2009-11-08 18:21:15

是的，这是显而易见的解决方案。然而，在我的平台上进行分区和模数的操作非常昂贵，大约有几百个循环。我更感兴趣的东西，不涉及那些。我不得不说这是一个纯粹的好奇心问题。 – Anycorn 2009-11-08 18:28:49

comp.compilers item这具有用于计算模3.

的替代，特别是如果被除数的maximium大小是适度的具体建议，是3的倒数作为固定点值相乘，以足够的精确位来处理最大大小的分红来计算商，然后从分红中减去3 *商以得到余数。所有这些乘法都可以用一个固定的移位和相加序列来实现。指令的数量将取决于倒数的位模式。当股息最小的时候，这种做法非常有效。

关于加数字的号码...如果你想添加的小数位数，你会最终会做什么相当于数转换到十进制，这10分包括某处。如果你愿意在base2中加入数字，你可以通过简单的右移和添加循环来完成。可以使用各种聪明的技巧以N位数据块的形式做到这一点，以加快速度。

来源

2009-11-08 18:55:35

快速模3或除法算法？

回答

相关问题