14

为什么 mod ( %) 操作比乘法 ( ) 的成本高出2*倍多一点？

请更具体地说明 CPU 如何执行除法运算并返回 MOD 运算的结果。

在以下示例中，每个线程运行一秒钟。测试是在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.
}
4

5 回答 5

11

MOD 是除法运算，而不是乘法运算。除法比乘法更昂贵。

有关 MOD 操作的更多信息，请点击此处：http ://en.wikipedia.org/wiki/Modulo_operation

于 2010-11-05T19:32:23.113 回答
5

AMD 和 Intel x86 处理器的指令延迟和吞吐量

CPU 上的一项操作本质上是较慢的 :)

于 2010-11-05T19:54:06.050 回答
5

除法算法（处理器通过门中实现的算法执行除法和乘法）比乘法更昂贵。事实上，一些复杂度较高的除法算法都以乘法为基本步骤。

即使您使用在学校学习的幼稚算法。它们都具有相同的渐近复杂度，但除法的常数更大（您必须找出数字，这不是微不足道的，因此您可能会搞砸并必须修复混乱）。

于 2010-11-05T20:07:50.143 回答
1

是的，mod 比乘法更昂贵，因为它是通过除法实现的。（CPU 通常在除法时返回商和余数。）但是你的两个线程都使用乘法。复制/粘贴错误？

于 2010-11-05T19:34:40.617 回答
0

mod 与除法本质上是相同的过程（出于这个原因，某些系统提供了“divmod”）。

二进制长乘法和二进制长除法的最大区别在于，长除法要求您在每次减法后执行溢出测试，而长乘法在初始屏蔽过程后无条件地执行加法。

这意味着你可以很容易地重新排列和并行化长乘法中的加法，但你不能对长除法做同样的事情。我在https://stackoverflow.com/a/53346554/5083516上写了一个更长的答案

于 2019-03-01T16:17:24.777 回答