Fostok's blog

Are +, -, *, / Really O(1)? And Why Is Modulo (%) So Slow?
By Fostok, history, 10 months ago, In English

I have several questions in mind, like:

1. Is +, -, *, / Actually O(1)? It’s commonly said that these operations are O(1), but is that always true?

2. Is x % y Slower Than x-(x / y) * y? I’ve heard people say "modulo is slow", so why not just avoid % and use x-(x / y) * y instead?

I hope you understand my curiosity!

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
10 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

from what I know, all those operations are O(1), but addition and subtraction have an edge over them—not multiplication, division, or modulo. Here's why:

In C++, addition (+) and subtraction (-) are generally the fastest arithmetic operations, usually taking just one CPU cycle. Multiplication (*) is slightly slower, though still fast on modern CPUs. However, division (/) and modulo (%) are significantly more expensive, especially for integer types.

Modulo operations (a % b) are closely tied to division internally because the processor often needs to perform a division to compute the remainder. This makes modulo roughly as expensive as division—sometimes even slower depending on the CPU architecture.

This is would be a possible order of speed : addition ≈ subtraction < multiplication < division ≈ modulo

→ Reply
»
10 months ago, hide # |
 
Vote: I like it -153 Vote: I do not like it

I think that integer multiplication is kind of done like binary exponentiation, except the multiplication is addition. So I guess you could say that multiplication is $$$O(\log n)$$$. And then integer division $$$a / b$$$ is done by binary searching on the range $$$[0, a]$$$ with the goal of finding the maximum value $$$c$$$ such that $$$c \cdot b \le a$$$. So I guess you could say that integer division is technically $$$O(\log^2 n)$$$. And then the reason why the mod operator $$$n \% m$$$ is so slow is because the computer has to run a for loop from $$$0$$$ to $$$m - 1$$$ (inclusive) to check if the current val $$$i == n \% m$$$. So I guess that that would be $$$O(m)$$$.

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +42 Vote: I do not like it

    What? Modulo is just a division and a subtraction

    → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    How can a computer run a for loop from 0 to m-1 if m was large.. let's say 1e18?

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      There is a good lecture of striver on youtube on bit manipulation on this division and modulo operator time complexity. let's say if you want 21 / 3 then what you do in division is actually repeated subtraction, like 21 — 3 — 3 — 3 — 3 — 3 — 3 — 3 = 21 — 3 * 7 = 21 — 3 * (2^2 + 2^1 + 2^0) . Any number can be represented in form of binary, thus we generalise this to subtracting (2^i) repeatedly after multiplication with divisor, i from 0 till needed(log n). This means just you need to do is: Subtract 3*(2^i) such that 21 — 3*(Σ(2^i)) >= 0. Thus Σ(2^i) is our result of division operation, here as: 21 / 3 = 2^2 + 2^1 + 2^0 = 7 After doing this division operation, the leftoff remainder will be our result of modulo operation. The value left after this repeated subtraction is: 21 % 3 = 21 — 3 * 7 = 21 — 21 = 0

      → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it -25 Vote: I do not like it

      When you try to do $$$37 \cdot 12$$$ in your head, it might take you a few seconds, but an average computer can do such math almost instantly. This principle applies to other things. Like your code might take $$$10-15$$$ seconds to run a test on the order of $$$10^{9}$$$, but the average computer can do it in just a few nanoseconds.

      → Reply
»
10 months ago, hide # |
← Rev. 2  
Vote: I like it +12 Vote: I do not like it

All the 5 operators are O(1) because O(1) notation means a constant number of operations. So because 1 + 1 and INT_MAX + INT_MAX (1 and INT_MAX are both just 32 bits, the actual number doesn't really matter) take the same number of operations, addition is O(1) (and the same for -, *, /, %).

However, an O(1) operation may take longer to execute than another one:

  • + and - are fast;

  • * is a bit slower;

  • / and especially % are considerably slower.

→ Reply
»
10 months ago, hide # |
← Rev. 3  
Vote: I like it +105 Vote: I do not like it

Yes, they are $$$O(1)$$$. More accurate analysis of how much CPU cycles exactly they take would require you to carefully analyze throughput and latency of specific assembly instructions used, as well as specific optimizations that compiler apply to them. Those may also differ between CPUs.

Integer division is generally computed with a single instruction idiv, so a % b and a - (a / b) * b will compile to the same assembly code, and, barring some pretty specific cases, you're better off writing plainly what result you want and let compiler optimize for you, than trying to do compiler's job by manually arranging those instructions.

Also worthwhile to note that when the modulus is a compile-time constant, division is done via Barrett reduction, which is faster than runtime idiv call. Still, compiler would optimize both versions to use the same assembly. In the latter case, both are compiled to the equivalent of a - (a / b) * b, where a / b is done via Barrett reduction, so with constexpr modulus, a / b is actually slightly faster than a % b, by those same multiplication and subtraction.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

I have heard that if +, - takes 1 units time to run, then * takes 3 units, / and % takes 20 units.

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    that makes sense.. I've once submitted a code that requires me to mod on 1e9+7..

    when I submitted it using '%' operatino it got around 1000 ms but I tried to subtract the mod whenever the answer exceeds 1e9+7 and it got around 200ms or less. that was very confusing to me.

    → Reply