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?
10
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]
3
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.
3
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.