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?
Improve this question
10
  • 1
    In my code I almost always need modulo not the remainder. No idea why remainder is so popular.
    – CodesInChaos
    Jan 30, 2014 at 22:13
  • 8
    Related What's the difference? Remainder vs Modulus - Eric Lippert’s Blog (by one of the C# designers, but I believe he joined team after this decision was made)
    – CodesInChaos
    Jan 30, 2014 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, 2014 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, 2014 at 22:19
  • 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, 2014 at 11:45

3 Answers 3

Reset to default
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]

Improve this answer
3
  • 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, 2014 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 (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, 2014 at 5:04
  • @user40989: I said I'd never used it. See edit!
    – david.pfx
    Feb 11, 2014 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.

Improve this answer
3
  • 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, 2014 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, 2014 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, 2014 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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.