Is MOD operation more CPU intensive than multiplication?

Question

Why is a mod (%) operation more expensive than a 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.
}

Navigable

Both code examples are the same. – Zacek

Where is the version with +? ^^ – Chaetognath

Compare multiplication algorithms (en.wikipedia.org/wiki/Binary_multiplier) with integer division algorithms (en.wikipedia.org/wiki/Division_(digital)). I don't know what the sparc implements for division. Maybe the non-restoring algorithm. – Quarters

-1 score for this question? Can the downvoters explain / comment? – Peptic

Does this answer your question? Why is division more expensive than multiplication? – Ganoid

although division by a constant like this case can be converted to multiplication but it's still far more complex than a single division instruction, hence much slower – Ganoid

This code doesn't use the result of a. If compiled with optimization, neither loop does any work. If without optimization, it's not a very meaningful benchmark. – Hectograph

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

Esta

Answer 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

Zacek

Robert: The same could be told about division - i.e. division is more expensive because it is a MOD operation, while MOD is more expensive than multiplication. I'd like to know more details at the CPU level why is division/mod more expensive than multiplication. This answer repeats my question. – Navigable

This is the correct answer, obviously the OP didn't take it seriously enough to compare mod to div. There ought to be dusty corner in the Internet somewhere that talks about sparc processor internals. – Tommietommy

The question must be bad then if the correct answer didn't say anything apart from stating what was obvious. Following that I improved the question and asked to provide more details on the CPU usage. – Navigable

Answer 3

Instruction latencies and throughput for AMD and Intel x86 processors

One operation is just inherently slower at the CPU :)

Chaetognath

Answer 4

mod is essentially the same process as division (some systems provide a "divmod" for this reason).

The big difference between binary long mulitplication and binary long division is that long division requires you to perform an overflow test after each subtraction, while long mutiplication performs the addition unconditionally after the initial masking process.

That means you can easilly rearrange and paralleise the addditions in long multiplication, but you can't do the same for long division. I wrote a longer answer about this at https://mcmap.net/q/101216/-why-is-division-more-expensive-than-multiplication

Mimas

Answer 5

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?

Turnaround