MOD操作比乘法更耗CPU？ [英] Is MOD operation more CPU intensive than multiplication?

问题描述

为什么 MOD 操作比乘法要多一个因子of 2 ？请更具体地了解CPU如何执行除法运算并返回MOD运算的结果。

Why is MOD operation more expensive than multiplication by a bit more than a factor of 2? Please be more specific about how CPU performs division operation and returns the result for MOD operation.

在下面的示例中，线程每次运行一秒。测试在 SPARC 处理器上执行。

In the following example the threads each run for a second. The test was performed on a SPARC processor.

// 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.
}

推荐答案

算法和在门中实现的算法的乘法）比用于乘法更昂贵。事实上，一些具有良好复杂性的算法使用乘法作为一个基本步骤。

Algorithms (processors execute the division and the multiplication by algorithms implemented in gates) for division are more costly than for multiplication. As a matter of fact, some algorithms for division which have a good complexity are using the multiplication as a basic step.

即使你使用的幼稚算法，学校。他们都有相同的渐近复杂性，但分裂的常数更大（你必须找出数字，这不是微不足道的，所以你可以搞砸，必须修复的混乱）。

Even if you use the naive algorithms that are learned in school. They both have the same asymptotic complexity, but the constant for the division is greater (you have to find out the digit and that is not trivial, so you can mess up and have to fix the mess).

这篇关于MOD操作比乘法更耗CPU？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！