9

Going through Modulo operation (the avenue I entered while exploring the difference between rem and mod) I came across:

In mathematics the result of the modulo operation is the remainder of the Euclidean division. However, other conventions are possible. Computers and calculators have various ways of storing and representing numbers; thus their definition of the modulo operation depends on the programming language and/or the underlying hardware.

Questions:

  • Going through Euclidean division I found that remainnder of this operation is always positive (or 0). What limitation of the underlying computer hardware forces programming language designers to differ from mathematics?
  • Every programming language has it predefined, or undefined, rule according to which the result of the modulo operation gets it's sign. What rationale is adopted while making these rules? And if the underlying hardware is the concern then shouldn't rules change according to that, independent of programming language?
Doc Brown
  • 199,015
  • 33
  • 367
  • 565
Bleeding Fingers
  • 343
  • 1
  • 12
  • 1
    In my code I almost always need modulo not the remainder. No idea why remainder is so popular. – CodesInChaos Jan 30 '14 at 22:13
  • 8
    Related [What's the difference? Remainder vs Modulus - Eric Lippert’s Blog](http://blogs.msdn.com/b/ericlippert/archive/2011/12/05/what-s-the-difference-remainder-vs-modulus.aspx) (by one of the C# designers, but I believe he joined team after this decision was made) – CodesInChaos Jan 30 '14 at 22:14
  • 1
    If you continue reading the Wikipedia article (beyond the part you quoted), it explains what you quoted pretty well. What about that explanation are you confused about? – Robert Harvey Jan 30 '14 at 22:15
  • "Going through Euclidean division I found that remainnder of this operation is always positive (or 0). What limitation of the underlying computer hardware forces programming language designers to differ from mathematics?" None, generally. It's generally going to be an intentional decision one way or the other. – Servy Jan 30 '14 at 22:15
  • 1
    One related question is which of these operations directly map to CPU instructions. In c it's implementation defined, which fits with the c philosophy of directly mapping to the hardware on as many platforms as possible. So it doesn't specify stuff that might differ between CPUs. – CodesInChaos Jan 30 '14 at 22:19
  • @RobertHarvey I just did. It's not a confusion, just that I'm curious as to why don't programming language use the definition that is true to mathematics? Why using three different divisions rather than one (Euclidean)? What has the underlying hardware got to do with this, and if it has than why isn't the rule independent of programming-language? – Bleeding Fingers Jan 30 '14 at 22:31
  • Maybe because programmers aren't mathematicians? – Karl Bielefeldt Jan 31 '14 at 01:18
  • 5
    @BleedingFingers Programming often uses integer division that goes towards zero, e.g. `(-3)/2 == -1`. This definition can be useful. When you want `%` to be consistent with this division fulfilling `x == (x/y)*y + x % y` you end up with the definition of `%` used in C#. – CodesInChaos Jan 31 '14 at 11:45
  • @CodesInChaos plausible but is that one of the rationale? What has the underlying hardware got to do in this? – Bleeding Fingers Feb 03 '14 at 19:50
  • 1
    Some languages, like Haskell and derivates, have both div/mod and quot/rem. – Ingo Feb 11 '14 at 10:46

3 Answers3

7

The hardware of all modern computers is sufficiently powerful to implement mod operations of either sign with no (or trivial) performance impact. This is not the reason.

The common expectation of most computer languages is that (a div b) * b + (a mod b) = a. In other words, div and mod considered together divide a number into parts that can reliably be put back together again. This requirement is explicit in the C++ standard. The concept is closely related to indexing of multi-dimensional arrays. I have used it often.

From this it can be seen that div and mod will preserve the sign of a if b is positive (as it usually is).

Some languages provide a 'rem()' function that is related to mod and has some other mathematical justification. I have never needed to use this. See for example frem() in Gnu C. [edited]

david.pfx
  • 8,105
  • 2
  • 21
  • 44
  • I think that `rem(a,b)` is more likley to be `mod(a,b)` if it is positive or `mod(a,b) + b` if it is not. – user40989 Feb 10 '14 at 14:26
  • 3
    `(a div b) * b + (a mod b) = a` - this, so very much. In fact, contrary to how Wikipedia describes [extending it to negative numbers in Euclidean division](http://en.wikipedia.org/wiki/Euclidean_division#Intuitive_example) (especially "The remainder is the only one of the four numbers that can never be negative.") confuses me because I was _always_ taught that the remainder _can_ be negative in every math class at that level. – Izkata Feb 11 '14 at 05:04
  • @user40989: I said I'd never used it. See edit! – david.pfx Feb 11 '14 at 10:10
4

For programming typically you want X == (X/n)*n + X%n; therefore how modulo is defined depends on how integer division was defined.

With this in mind, you're really asking "What rationale is used when programming language designers decide how integer division works?"

There are actually about 7 choices:

  • round to negative infinity
  • round to positive infinity
  • round to zero
  • several versions of "round to nearest" (with differences in how something like 0.5 is rounded)

Now consider -( (-X) / n) == X/n. I'd want this to be true, as anything else seems inconsistent (it's true for floating point) and illogical (a likely cause of bugs and also a potentially missed optimisation). This makes the first 2 choices for integer division (rounding towards either infinity) undesirable.

All of the "round to nearest" choices are a pain in the neck for programming, especially when you're doing something like bitmaps (e.g. offset = index / 8; bitNumber = index%8;).

That leaves rounding towards zero as the "potentially most sane" choice, which implies that modulo returns a value with the same sign as the numerator (or zero).

Note: You'll also note that most CPUs (all CPUs that I'm aware of) do integer division in the same "round to zero" way. This is likely to be for the same reasons.

Brendan
  • 3,895
  • 21
  • 21
  • But truncating division has its own inconsistencies as well: It breaks `(a+b*c)/b == a % b` and `a >> n == a / 2 ** n`, for which floored division has sane behavior. – dan04 Feb 10 '14 at 21:53
  • Your first example doesn't make sense. Your second example is a mess for programmers: for positive a and positive n it's consistent, for negative a and positive n it depends on how shift right is defined (arithmetic vs. logical), and for negative n it's broken (e.g. `1 >> -2 == a / 2 ** (-2)`). – Brendan Feb 11 '14 at 13:34
  • The first example was a typo: I meant `(a + b * c) % b == a % b`, i.e., the `%` operator is divisor-periodic in the dividend, which is often important. For example, with floored division, `day_count % 7` gives you the day of the week, but with truncating division, this breaks for dates before the epoch. – dan04 Feb 11 '14 at 14:59
0

First, I'll repeat that a modulo b should be equal to a - b * (a div b), and if a language doesn't provide that, you are in an awful mathematical mess. That expression a - b * (a div b) is actually how many implementations calculate a modulo b.

There are some possible rationales. The first is that you want maximum speed, so a div b is defined as whatever the processor used will provide. If your processor has a "div" instruction then a div b is whatever that div instruction does (as long as it is something not totally insane).

The second is that you want some specific mathematical behaviour. Let's first assume b > 0. It is quite reasonable that you want the result of a div b to be rounded towards zero. So 4 div 5 = 0, 9 div 5 = 1, -4 div 5 = -0 = 0, -9 div 5 = -1. This gives you (-a) div b = - (a div b) and (-a) modulo b = - (a modulo b).

This is quite reasonable but not perfect; for example (a + b) div b = (a div b) + 1 doesn't hold, say if a = -1. With a fixed b > 0, there are usually (b) possible values for a such that a div b gives the same result, except there are 2b - 1 values a from -b+1 to b-1 where a div b equals 0. It also means that a modulo b will be negative if a is negative. We'd want a modulo b to be always a number in the range from 0 to b-1.

On the other hand, it is also quite reasonable to request that as you go through successive values of a, a modulo b should go through the values from 0 to b-1 then start with 0 again. And to request that (a + b) div b should be (a div b) + 1. To achieve that, you want the result of a div b to be rounded towards -infinity, so -1 div b = -1. Again, there are disadvantages. (-a) div b = -(a div b) doesn't hold. Repeatedly dividing by two or by any number b > 1 will not eventually give you a result of 0.

Since there are conflicts, languages will have to decide which set of advantages is more important to them and decide accordingly.

For negative b, most people can't get their head around what a div b and a modulo b should be in the first place, so a simple way is to define that a div b = (-a) div (-b) and a modulo b = (-a) modulo (-b) if b < 0, or whatever is the natural outcome of using the code for positive b.

gnasher729
  • 42,090
  • 4
  • 59
  • 119