MOD操作比乘法更耗CPU吗?
为什么MOD
的操作比multiplication
贵多了一点点factor of 2
?请更具体地说明CPU如何执行除法操作并返回MOD操作的结果。MOD操作比乘法更耗CPU吗?
在以下示例中,每个线程每秒运行一次。该测试在SPARC
处理器上执行。
// multiplication
void someThread() {
int a = 10234;
while (true) {
opers++;
a = a * a;
a++;
}
// opers ~ 26 * 10^6 in a sec.
}
// MOD
void someThread() {
int a = 10234;
while (true) {
opers++;
a = a % 10000007;
a++;
}
// opers ~ 12 * 10^6 in a sec.
}
算法(处理器上执行分割和由算法的乘法在门实现),用于分割比乘法更昂贵。事实上,一些具有良好复杂性的划分算法将乘法作为基本步骤。
即使您使用在学校学到的朴素算法。它们都具有相同的渐近复杂性,但分割的常量更大(您必须找出数字,这不是微不足道的,因此您可能会搞砸并必须修复混乱)。
MOD是除法运算,不是乘法运算。分部比乘法更昂贵。
对这里的MOD操作的更多信息:http://en.wikipedia.org/wiki/Modulo_operation
Downvoter:为什么? – 2010-11-05 19:35:10
罗伯特:同样可以告诉分工 - 即分工更昂贵,因为它是一个MOD操作,而MOD比乘法更贵。我想知道CPU级别的更多细节,为什么division/mod比multiplication更昂贵。这个答案重复了我的问题。 – Leonid 2010-11-05 19:41:46
这是正确的答案,很显然,OP没有认真对待mod与div的比较。在互联网的某个地方应该有尘土飞扬的角落,谈论sparc处理器内部。 – 2010-11-05 21:11:24
是,国防部比乘法更昂贵,因为它是通过划分来实现。 (CPU通常会在除法上返回商和余数)。但是,两个线程都使用乘法。复制/粘贴错误?
这两个代码示例都是相同的。 – 2010-11-05 19:33:09
解决了这个问题。 – Leonid 2010-11-05 19:35:22
带'+'的版本在哪里? ^^ – 2010-11-05 19:51:53