高效（循环）算法计算模25？
我有一个代码，我在其中计算x％25。x总是取正值但其动态范围很大。
我发现这个计算轴％25的特殊代码片段需要大周期。 我需要优化它。
由于表可能存在大的内存大小，因此排除了预先计算的查找表。
作为第二种方法我编码下面的片段（C代码） –
mod(a, b) { int r = a; while(r >= b) { r = r - b; } return r; } 1.）如何针对周期进一步优化此代码（将其压缩到最大值）？
2.）是否有任何完全不同的优化方式来实现x％25（我知道它不是一个常见的操作，但仍然，寻找人们可能在他们的经验中使用的聪明输入，这可能会让我感到厌烦。）。
谢谢。
-广告
编辑：
我认为在C中使用本机模运算符％，内部使用除法运算（/），这对我正在使用的处理器来说代价很高。（没有div指令）。 因此，尝试查看自定义实现是否可以使用％运算符击败固有计算。
-广告
我建议阅读Hacker’s Delight 。 它描述了常数除数的非常快的余数算法。 他们几乎肯定会击败一般算法。
更新：这是一些示例代码…它可能可以重做以避免临时长时间。
unsigned mod25(unsigned n) { unsigned reciprocal = 1374389535; // 2^35 / 25 unsigned div25 = ((unsigned long long)n * reciprocal) >> 35; return n - div25 * 25; }
这是我提出的另一个解决方案：
int mod25(int x){ /* 25 * (all powers of 2 <= INT_MAX), descending */ if (x >= 1677721600) x -= 1677721600; if (x >= 838860800) x -= 838860800; if (x >= 419430400) x -= 419430400; if (x >= 209715200) x -= 209715200; if (x >= 104857600) x -= 104857600; if (x >= 52428800) x -= 52428800; if (x >= 26214400) x -= 26214400; if (x >= 13107200) x -= 13107200; if (x >= 6553600) x -= 6553600; if (x >= 3276800) x -= 3276800; if (x >= 1638400) x -= 1638400; if (x >= 819200) x -= 819200; if (x >= 409600) x -= 409600; if (x >= 204800) x -= 204800; if (x >= 102400) x -= 102400; if (x >= 51200) x -= 51200; if (x >= 25600) x -= 25600; if (x >= 12800) x -= 12800; if (x >= 6400) x -= 6400; if (x >= 3200) x -= 3200; if (x >= 1600) x -= 1600; if (x >= 800) x -= 800; if (x >= 400) x -= 400; if (x >= 200) x -= 200; if (x >= 100) x -= 100; if (x >= 50) x -= 50; if (x >= 25) x -= 25; return x; }
这不使用除法或乘法，只有27次比较，最多27次减法。
要说服自己这样做有点困难，但确实如此（至少对于x的非负值）。
上面的代码实际上是这个展开的版本：
int mod25(int x){ int divisor; for(int divisor = 1677721600; divisor >= 25; divisor >>= 1) { if (x >= divisor) x -= divisor; } return x; }
通过展开它，我们避免进行循环比较，也避免了更大代码的代价。 你甚至可以使用Duff的设备部分展开它，如果你觉得如此倾向，但总共只有27次迭代，而且每次迭代的代码都很少，我倾向于一直展开它。
以下是它的工作原理：每个非负整数x可以表示为（n * 25）+ k，其中n是非负整数，k是0到24之间的整数。k也恰好是我们想要的结果，所以，如果我们可以计算x – （n * 25），我们就会得到答案。 不过，我们希望能够在不知道n的情况下做到这一点。
想想二进制中的n。 如果我们可以关闭我们得到的1位中的每一位。一种方法是从2的大功率开始并向下工作，只有当n的当前值大于2时才减去2的每个幂。或等于2的幂。
由于我们正在处理（n * 25），我们实际上需要2次25的递减次幂。因为k严格小于25，并且我们考虑的最小除数是25，所以即使我们处理时也是如此（n * 25）+ k。
所以每次比较+减法都将n的一位归零，最后我们留下k，余数。
既然你想要模数常数，你可以通过使用倒数乘法来击败它。 本文展示了如何以这种方式除以常数，并最终如何从中得到余数。
这是我能想到的最好的：
int mod25(int x) { while((x = (x & 31) + 7 * (x >> 5)) >= 25) x -= 25; return x; }
它近似x % 25 ， x % 32 + 7 * (x/32) 。 该值将超过25的倍数，这允许递归。
性能似乎是足够的：值x = 2147483647 （又名INT_MAX ）需要11次迭代。
我受到了Pax的回答的启发，并制作了一个更通用的算法。
int mod(int a, int b) { int s = b; while (s <= a) { s <<= 1; } int r = a; while (r >= b) { s >>= 1; if (s <= r) { r -= s; } } return r; }
这从a减去两倍的b幂，直到找到结果。
编辑：添加if条件，使其正常工作。
例如，如果这是100％7，它首先计算出7 * 2 * 2 * 2 * 2 = 112.然后它将112（ s ）除以2并从100（ r ）中减去（当s <= r ）并不断地执行此操作，直到找到模数。 因此，
s = 112 / 2 = 56, r = 100 - 56 = 44 s = 56 / 2 = 28, r = 44 - 28 = 16 s = 28 / 2 = 14, r = 16 - 14 = 2
因此，100％7 = 2
哦，我的<选择的神性>。 我无法相信其中的一些答案。
首先，重复减法，即使是Pax的版本，也永远不会是最佳的。 考虑以下：
20 % 25
使用重复减法很容易和快速，但是：
65535 % 25
将会非常缓慢，600多次迭代。 这是16位数的平均300次迭代。 至于32位数，好吧，甚至不去那里。
最快的方法是使用长除法。 见尼基的回答。
但是，这就是编译器无论如何都会产生的，至少，人们希望它是编译器生成的东西。 最好检查一下您是否使用编译器来获取利基处理器。
加快这一速度的最好方法是首先不要模数。 为什么需要获得模数，并且可以重新考虑代码/算法以避免模数，或者至少使模数变得微不足道。
循环的问题在于它是O（n） – 对于大的r值来说它会非常慢。 我建议这样的事情：
for (int s = MAX_SHIFT; s>=0; s--) if (r > (b<
但我怀疑你的编译器正在做比这更昂贵的事情。
在许多处理器上，整数乘法比整数除法快。 这篇博客文章展示了如何用常数整数乘法替换常数整数除法。 通过重新排列数学，你可以得到余数而不是商。 但请注意，如果您使用的是中等复杂的编译器，那么这已经为您完成了。 你只需编写x % 25 ，编译器将完成剩下的工作。 您应该检查生成的代码汇编代码，validation编译器是否已经完成此操作，然后再在C中进行此优化。此外，您应该测量（分析）前后的性能，以确保您真正做得更快。
对于使用本机指令进行合理大型操作数的循环，循环将慢得多。
编辑：另见本文 。
如果C编译器的目标是没有除法指令的CPU，则可以按如下方式修改代码：
mod(a, b) { int s = b + b + b + b; int r = a; while(r >= s) { r -= s; } while(r >= b) { r -= b; } return r; }
这通过减去四个而不是一个的块的值来工作，直到最后一个然后它切换到减去一个的块。
这应该使您的代码运行速度快四倍（假设4*b不在整数范围之外）。 你甚至可以在4*b之前插入更多的循环（比如一个8*b循环）以获得更高的速度。
除此之外，手动编码汇编程序可能会有所帮助，但我认为如果没有它，你会从上面的代码中获得相当大的提升。
如果您了解有关使用mod调用的方式的更多详细信息，则可以针对特定情况对其进行优化。 例如，如果您只想知道16位整数的模25，则以下代码将比具有可变分母的简单循环快得多。
int mod25 (int a) { // a has maximum value of 2^15-1 = 32767 while (a >= 15625) a-= 15625; // at most 2 times. while (a >= 625) a-= 625; // at most 24 times. while (a >= 25) a-= 25; // at most 24 times. return a; }
运行测试，我发现在模数代码和%运算符的使用之间出现明显的差异（2秒对0秒）之前，你必须进行1000万次迭代。 直到那时，它们都是0秒，虽然它是在快速机器上运行（对于mod25更好）和div指令（对于%运算符更好），因此您需要在自己的硬件上对其进行基准测试。
这与您在不使代码不可读的情况下获得的速度一样快（尽管如果您愿意添加大量解释其工作原理的评论，那么即使这样也不应该阻止您）。
对于任何分母，更一般的解决方案是首先使分母（速度的位移）加倍，以使随后的减法最小化。 然后，当分子减少到增加的分母以下时，将分母减半并继续前进（直到分母在开始时回归）。
int mod (int n, int d) { /* dx is the adjusted denom, don't let it overflow though. */ int dx = d; while (((dx << 1) >>1) == dx) dx <<= 1; /* This loop processes the dx values until they get too small. */ while (dx >= d) { /* This loop subtracts the large dx value. */ while (n >= dx) n -= dx; dx >>= 1; } return n; }
这实际上与上面mod25的优化版本mod25 ，同时提供了更通用的解决方案。
请介绍一些常识。
如果您可以编写比编译器更快地计算x％25的C代码，那么编译器将使用更快的方法。
原始海报做了这个奇妙的假设，即编译器会使用除法。 我在过去十年中没有使用过的编译器就是这样做的。 它是一个乘以接近（2 ^ 32/25）的常数加上一些麻烦，你将无法用手改进。
有一种远程的可能性，您可以生成比编译器更快的代码，以确定是否x％25 == 0，因为您实际上并不需要能够正确计算x％25的代码，只有正确计算x％25的代码如果x％25！= 0，它为0并且不产生0。节省可能是亚纳秒。
“如何针对各种常数c最佳地计算x％c”是一个很好的谜题。 编译器编写者喜欢很好的谜题。 而且他们比你更善于解决这样的好谜题。 特别是因为他们只需要一台适用于一台机器的解决方案，您必须生成一般解决方案。
如果您不喜欢%运算符：
int mod(int a, int b) { int integral = a / b; return a - (b*integral); }
如果你知道b将是2的幂，你可以使用按位AND而不是模运算符。 但是， modulo的维基百科页面似乎表明任何C编译器都会注意到这一点，并且无论如何都要优化模数。
可能不是最快但效率相当的。 我没有时间测试，但使用（2的幂）* 25的查找表，最大范围/ 2。 然后做一个循环。 例如，高达3199的范围需要7次迭代。
static int pow[] = {25, 50, 100, 200, 400, 800, 1600}; int mod25(int x) { int i = sizeof pow /sizeof pow[0]; while (i--) { if (x >= pow[i]) x -= pow[i]; } return x; }
如果你有一个非常大的范围，但较低的值更常见，那么可能值得使用二进制斩波来找到起点。
int mod25(int x) { static int divisors[] = {2147483625, 244140625, 9765625, 390625, 15625, 625, 25}; int i; for (i = 0; i < sizeof(divisors)/sizeof(int); i++) { int divisor = divisors[i]; while (x >= divisor) { x -= divisor; } } return x; }
工作原理：我们希望将x减去25的大倍数，以尽可能快地减少该值。 当除数太大时，我们切换到25的较小倍数。如果除数已经降到25，那么我们就完成了。
你可以尝试尝试不同的除数。 你只想确保：
- 他们正在下降
- 它们都是25的倍数
- 最后一个值是25
在上面的代码中，我使用25的最大签名32位倍数加上25的幂，这似乎是合理的，但我不得不承认我不确定它是否是最优的。
（顺便说一句：如果你的编译器不进行常量折叠 – 这将是非常令人惊讶的 – 那么你可能想用硬编码常量替换i的上限。）
为什么你不能只使用运算符% ？ 如果这是C代码，并且数字是普通的“native” int ：s，那么到目前为止应该是最快的方式。
你有什么理由不能使用C的内置模数运算符吗？
int a = x % 25;
编辑后;
如果你的rpocessor没有内置的模数支持，那么我仍然会使用％运算符，原因很简单，你的编译器会知道有问题的处理器没有本机％函数，并且可能会产生asm代码以最佳地模拟它。
这样说吧 – 如果你能想出一个优于编译器使用内置运算符产生的变量算法，而不是特定情况（例如简单地取模数100等2个最低位数），我就会着迷。
怎么样：
int y = 0, x = (x & 0x7f); while (x > 25) { x -= 25; y++; }
更新：这是非常错误的:)但是这个想法就在那里。
我觉得很奇怪，操作x % 25需要很长时间（如果你使用内置的%运算符，那就是）。 大多数现代处理器都应该在一条指令中完成。 我会查找此代码需要很长时间的其他原因。
编辑：这是一个算法，至少可以给出一些想法：
256 = 6（mod 25）
这意味着如果我们将数字x写为字节x3 x2 x1 x0我们得到x = 6^3*x3 + 6^2*x2 + 6*x1 + x0 （mod 25）
这给出了一个减小x大小的算法：
int x0 = x & 0xFF, x1 = (x>>8) & 0xFF, x2 = (x>>16) & 0xFF, x3 = (x>>24) & 0xFF; int y = x4; y = (y << 2) + (y << 1) + x3; y = (y << 2) + (y << 1) + x2; y = (y << 2) + (y << 1) + x1; y = (y << 2) + (y << 1) + x0;
（这里(y << 2) + (y << 1) = 4*y + 2*y = 6*y ）
在此之后， y将具有与x mod 25相同的余数。迭代此1,2或3次将使y为17,11或9位数。 其中一个尺寸可能足够小，可以制作查找表。
我严重怀疑这会比内置%运算符更快。
如果您将数字保存为BCD或数字字节数组，这将非常简单。 不幸的是，我不知道你用这些数字在你的程序中做了什么。 有时，看看你如何表示你的数据而不仅仅是摒弃算法是值得的。
这是一个想法
static int table0[256]; static int table1[256]; static int table2[256]; static int table3[256]; // ran just once to initialize the tables void initialMod25Tables() { for (int i = 0; i < 256; ++i) { table0[i] = i % 25; } for (int i = 0; i < 256; ++i) { table1[i] = (i << 8) % 25; } for (int i = 0; i < 256; ++i) { table2[i] = (i << 16) % 25; } for (int i = 0; i < 256; ++i) { table3[i] = (i << 24) % 25; } } int mod25(int x) { int y = table0[x & 0xFF]; x >>= 8; y += table1[x & 0xFF]; x >>= 8; y += table2[x & 0xFF]; x >>= 8; y += table3[x & 0xFF]; y = table0[y]; return y; }
如果你只考虑数字25你可以使用25除以整数的事实当且仅当整数的最后两位数是00,25,50或75时。所以为了得到模数你考虑最后两位数和然后减去最接近的00,25,50或75。