Is MOD operation more CPU intensive than multiplic

问题:

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.

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

回答1:

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).

回答2:

MOD is a division operation, not a multiplication operation. Division is more expensive than multiplication.

More information about the MOD operation here: http://en.wikipedia.org/wiki/Modulo_operation

回答3:

Instruction latencies and throughput for AMD and Intel x86 processors

One operation is just inherently slower at the CPU :)

回答4:

Yes, mod is more expensive than multiplication, as it is implemented through division. (CPUs generally return both quotient and remainder on division.) But both of your threads use multiplication. copy/paste error?