在C中获得mod 10的最快方法

问题描述 投票:0回答:2

在我的程序中,操作n % 10非常有用。我知道,当我们有n% m时,模块的运算可以快得多,其中m为2的幂,因为它可以由n & (m-1 )代替,但是如果操作数为10,有没有更快的方法来计算模数?在某些情况下,n是uint8_t,在其他情况下,n是uint32_t。

c performance optimization module
2个回答
0
投票

但是如果操作数为10,有什么更快的方法来计算模数?

有了一个好的编译器,没有。编译器已经发出了不错的代码。您可以使用编译器探索不同的优化设置。

OTOH,如果您知道编译器无法使用n % 10采取的某些限制,例如值始终为正数或子范围,则可以对编译器进行优化。

这种micro-optimisation通常不能有效利用程序员的时间。


0
投票

由于大多数现代处理器比乘法运算快得多,所以通常可以通过用一个或两个乘法和其他一些快速运算代替除法来加快除法和模运算,在这些运算中,被乘数是已知的小常数。 (例如移位和加法)。

[为此,需要在编译时根据分红来计算一些幻数;幸运的是,大多数现代编译器都知道如何执行此操作,因此您无需采取任何措施即可利用。就像@chuxan excellent answer中建议的那样,只需让您的编译器为您完成繁重的工作即可。

您可以使用无符号类型来帮助编译器;对于某些红利,有符号除法和模数很难替换。

模量优化的基本轮廓如下:

如果您具有精确的算术,则可以将x % p替换为p * ((x * (1/p)) % 1)。对于常数p,可以在编译时预先计算1/p%1操作仅包含舍弃小数部分,这只是右移。因此,用两个乘法替换除法,并且如果p仅设置了几个位,则p的乘法可能会进一步优化为几个左移。

我们可以利用定点算术来执行该计算,这是因为大多数处理器会为整数乘法生成双倍大小的结果。因为我们不在乎内部乘法的整数部分,并且知道外部乘法的结果必须小于p,所以我们只需要为计算的整数部分保留ceil(log2 p)位,其余部分保留分数。这可能会给我们足够的精度,以正确处理x的可能值范围,特别是如果x的范围有限(例如uint8_t甚至uint16_t)。关键是找到使1/p表示误差最小的固定点位置。

对于p的许多小值,这可行。对于其他方法,存在另一种(但较慢)的解决方案,其中包括使用乘以逆的乘法来估计q = x/p,然后计算x - q * p。如果可以保证q的估计是正确的或在已知方向上偏离一个,则我们只需要通过有条件地加或减p来校正最终的计算即可;无需在许多现代CPU上分支就可以实现。 (错误的方向是已知的,因为它仅取决于我们为除数的倒数选择的近似值是太小还是太大。)


x % 10非常具体的情况下,其中xuint_8,使用256字节的查找表,您可能会比上面做得更好。只有当您在大量值上进行紧密循环的模运算时,这才是值得的,即使那样,您仍要仔细剖析以验证它是否有所改进。

我怀疑那是否是您这段时间的最佳花费;您的应用程序中可能会有更多富有成效的优化机会。

© www.soinside.com 2019 - 2024. All rights reserved.