MOD操作比乘法更加CPU密集吗？

Question

为什么MOD操作比multiplication一个多一点多贵factor of 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.
}

Answer 1

MOD是除法运算,而不是乘法运算.分区比乘法更贵.

有关MOD操作的更多信息,请访问:http://en.wikipedia.org/wiki/Modulo_operation

Answer 2

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

一个操作本质上在CPU处慢:)

Answer 3

用于除法的算法(处理器执行除法和门中实现的算法的乘法)比乘法更昂贵.事实上,一些具有良好复杂性的划分算法使用乘法作为基本步骤.

即使你使用在学校学到的天真算法.它们都具有相同的渐近复杂度,但是除法的常数更大(你必须找出数字并且这不是微不足道的,所以你可以搞砸并且必须解决这个问题).