logo标签列表

MOD运算比乘法运算更加占用CPU资源吗？

c++cpu-architecturemultiplicationdivision
14

为什么模运算(%)比乘法(*)昂贵，其代价超过了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.
}
2
这两个代码示例是相同的。 - Robert Harvey
版本带有 + 的在哪里？^^ - user166390
给这个问题打-1分？给踩的人解释/评论一下吗？ - Rajan
1
尽管像这种情况下的常数除法可以转换为乘法，但它仍然比单个除法指令复杂得多，因此速度要慢得多。 - phuclv
这段代码没有使用 a 的结果。如果使用优化编译，则两个循环均不会执行任何工作。如果未使用优化，则这不是一个非常有意义的基准测试。 - Peter Cordes
显示剩余2条评论
5个回答
11
2
罗伯特：同样的情况也适用于除法——即除法是一种MOD运算，而MOD比乘法更昂贵。我想了解更多关于CPU层面为什么除法/取模比乘法更昂贵的细节。这个答案重复了我的问题。 - Leonid
1
这是正确的答案，显然OP没有认真比较mod和div。在互联网的某个角落里，应该有关于sparc处理器内部的信息。 - Hans Passant
1
如果“正确答案”除了说明显而易见的内容，什么也没有说，那么问题肯定是有问题的。在此之后，我改进了问题，并要求提供有关 CPU 使用情况的更多详细信息。 - Leonid
6
5

算法（处理器通过门实现的算法执行除法和乘法）对于除法来说比乘法更加昂贵。事实上，一些具有良好复杂度的除法算法使用乘法作为基本步骤。

即使您使用在学校中学到的朴素算法，它们的渐近复杂度相同，但是除法的常数更大（您必须找出数字，这并不容易，因此可能会出错并且需要修正错误）。

3

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

二进制长乘法和二进制长除法之间的主要区别在于，长除法要求您在每次减法后执行溢出测试，而长乘法在初始掩码处理后无条件执行加法。

这意味着您可以轻松地重新排列和并行化长乘法中的加法，但对于长除法则不能。我在https://dev59.com/omUo5IYBdhLWcg3wzSIq#53346554中写了一个更详细的回答。

1

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接