3 ms·

Article: "Well a little thought shows that C = A % B is equivalent to C = A - B * (A / B). In other words the modulus operator is functionally equivalent to thr

Article: "Well a little thought shows that C = A % B is equivalent to C = A - B * (A / B). In other words the modulus operator is functionally equivalent to three operations." The integer divide instruction returns both the quotient and the remainder on the processors I know of. I can't see what sense it makes to have a modulo operator that is more expensive than a division operator.

pmjordan 16y ago
Many processors don't have an (integer) division instruction, however, particularly those in the embedded world. That said, I share DarkShikari's concerns.
- tspiteri 16y ago
  I am not saying that division is not expensive, or that the modulo operator is not just as expensive. I am only pointing out that the modulo operator is not more expensive that division.
  - pmjordan 16y ago
    Agreed, if there is a dedicated instruction available[1], and if the expression can't be reduced to multiplications/shifts/addition due to division by a constant. None of the 3 architectures mentioned in the article have a division instruction, and the denominators are constant. So this is probably the least of the problems with this article, considering the audience is embedded programmers whose code probably never runs on x86, POWER or SPARC processors. Where you're not using the division instruction, modulo can actually be faster than division itself. The extreme case are powers of 2 of course; on x86, a right shift is vastly more expensive than a bitwise AND, for example. Other denominators don't produce quite so drastic differences. In any case, once you've done the division, the remainder is practically free; the article is basically an illustration of how bad the compilers in question are at spotting this fact. (though not mentioning which compilers and with which flags are affected makes it pretty useless) [1] It's technically conceivable that a superscalar, microcoded processor might actually detect whether the quotient, the remainder or both are actually used later in the code during the dependency check, and produce 3 different sets of microcode for these situations. I'd be surprised if any actually did this, though.
    - tspiteri 16y ago
      ... if the expression can't be reduced to multiplications/shifts/addition due to division by a constant. Ah, I missed that. Even on normal processors, for the following: int div60(int i) { return i / 60; } int mod60(int i) { return i % 60; } gcc uses one multiplication and some shifts/additions for div60() and two multiplications and some shifts/additions for mod60().
    - caf 16y ago
      In any case, once you've done the division, the remainder is practically free; the article is basically an illustration of how bad the compilers in question are at spotting this fact. This is probably the rationale behind the standard div() function, that calculates division and modulus together - it should make it easier for less sophisticated compilers to take advantage of this.

pmjordan 16y ago

Many processors don't have an (integer) division instruction, however, particularly those in the embedded world. That said, I share DarkShikari's concerns.

tspiteri 16y ago
I am not saying that division is not expensive, or that the modulo operator is not just as expensive. I am only pointing out that the modulo operator is not more expensive that division.
- pmjordan 16y ago
  Agreed, if there is a dedicated instruction available[1], and if the expression can't be reduced to multiplications/shifts/addition due to division by a constant. None of the 3 architectures mentioned in the article have a division instruction, and the denominators are constant. So this is probably the least of the problems with this article, considering the audience is embedded programmers whose code probably never runs on x86, POWER or SPARC processors. Where you're not using the division instruction, modulo can actually be faster than division itself. The extreme case are powers of 2 of course; on x86, a right shift is vastly more expensive than a bitwise AND, for example. Other denominators don't produce quite so drastic differences. In any case, once you've done the division, the remainder is practically free; the article is basically an illustration of how bad the compilers in question are at spotting this fact. (though not mentioning which compilers and with which flags are affected makes it pretty useless) [1] It's technically conceivable that a superscalar, microcoded processor might actually detect whether the quotient, the remainder or both are actually used later in the code during the dependency check, and produce 3 different sets of microcode for these situations. I'd be surprised if any actually did this, though.
  - tspiteri 16y ago
    ... if the expression can't be reduced to multiplications/shifts/addition due to division by a constant. Ah, I missed that. Even on normal processors, for the following: int div60(int i) { return i / 60; } int mod60(int i) { return i % 60; } gcc uses one multiplication and some shifts/additions for div60() and two multiplications and some shifts/additions for mod60().
  - caf 16y ago
    In any case, once you've done the division, the remainder is practically free; the article is basically an illustration of how bad the compilers in question are at spotting this fact. This is probably the rationale behind the standard div() function, that calculates division and modulus together - it should make it easier for less sophisticated compilers to take advantage of this.