14

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.
}
Wai Ha Lee
  • 8,598
  • 83
  • 57
  • 92
Leonid
  • 22,360
  • 25
  • 67
  • 91
  • 2
    Both code examples are the same. – Robert Harvey Nov 05 '10 at 19:33
  • Where is the version with `+`? ^^ –  Nov 05 '10 at 19:51
  • Compare multiplication algorithms (http://en.wikipedia.org/wiki/Binary_multiplier) with integer division algorithms (http://en.wikipedia.org/wiki/Division_(digital)). I don't know what the sparc implements for division. Maybe the non-restoring algorithm. – indiv Nov 05 '10 at 20:21
  • -1 score for this question? Can the downvoters explain / comment? – Rajan Aug 04 '11 at 00:03
  • Does this answer your question? [Why is division more expensive than multiplication?](https://stackoverflow.com/questions/15745819/why-is-division-more-expensive-than-multiplication) – phuclv Apr 08 '20 at 05:38
  • 1
    although division by a constant like this case [can be converted to multiplication](https://stackoverflow.com/q/41183935/995714) but it's still far more complex than a single division instruction, hence much slower – phuclv Apr 08 '20 at 05:40
  • 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. – Peter Cordes Feb 04 '21 at 18:55

5 Answers5

11

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

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501
  • 2
    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. – Leonid Nov 05 '10 at 19:41
  • 1
    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. – Hans Passant Nov 05 '10 at 21:11
  • 1
    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. – Leonid Nov 05 '10 at 21:33
6

Instruction latencies and throughput for AMD and Intel x86 processors

One operation is just inherently slower at the CPU :)

5

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

AProgrammer
  • 51,233
  • 8
  • 91
  • 143
3

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://stackoverflow.com/a/53346554/5083516

plugwash
  • 9,724
  • 2
  • 38
  • 51
1

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?

zvrba
  • 24,186
  • 3
  • 55
  • 65