## January 10, 2005

### I Say Modulo, You Say Modulus

There is an expression you sometimes hear around Microsoft, which goes something like "The API is finished, modulo the executive review" or "the work will take 3 weeks, modulo another reorg."

In this context, "modulo" is being used to mean "if you strip out all that other unpredicatble stuff, this is the right number". It's a geek reference to the function in C (and various other languages) that looks like

`a % b`.

For example, 13 % 5 is 3, and 100 % 3 is 1.

My father points out that in mathematics, the word "modulo" is used only in the phrase "X is congruent to Y modulo Z". That is, it is comparing the result of the operation on two values. So while a mathematician would agree that 13 is congruent to 3 modulo 5, they would also say that 13 is congruent to 8 modulo 5, and 13 is congruent to 103 modulo 5, etc. The word "modulus" refers to "the thing you are taking away", which is 5 in this example. There isn't a term (that he knows of) for the "smallest positive number that this number is congruent to" (3 in the examples above), which is what the % function in C is calculating.

What I really mean is there isn't a term like "modulend" or "modulisor"; there is a mathematicial term for what % is calculating, and that term is "remainder". The meaning of X % Y is really "the remainder when X is divided by Y" (I'm ignoring negative numbers in all of this). It's actually a bit strange that a) the symbol % was chosen and b) the term "modulus" or "modulo" was used.

% of course has a meaning, percent, and many calculators have a % button that calculates percent. But you really don't need a separate % symbol in a programming language, since you can do it with division and multiplying by 100 (you don't need it on a calculator either, for the same reason, but I guess calculator designers thought their users would be less mathematically apt than progamming language designers). And the % symbol does recall division (intentionally, of course), so it makes some sense. I don't know if C was the first language to use %; I think some other languages use the word "mod", but no language I know of uses "remainder" or any short form of that.

As for the term used, my 1978 edition of Kernighan and Ritchie (the original C bible) calls it "modulus" in the index, and uses "remainder" to describe it in the text. Many other people use modulo (I checked Find the Bug; I used "modulo", when I talked about it at all (I seem to have forgotten to define it in the chapter on C); it's one of those things I wrote without really thinking about it, that is probably at this moment offending a language purist). Both terms would sound wrong to a mathematician, although it's not a terrible co-option of the term (there's a story about a mathematician who is looking at some source code, sees the statement "a = a + 1", realizes that is mathematically impossible, and immediately abandons any attempt to become a programmer; but most mathematicians are not that stereotypically literal).

The modulo/modulus operator always makes me think of a cartoon. Imagine the Roadrunner is running on stilts, being chased by the Coyote. The Coyote is riding on a machine that swings an axe horizontally about five feet off the ground. Each time it swings, it lops off 5 feet of stilts, and the Roadrunner drops 5 feet. But when the stilts get short enough, the axe goes over the Roadrunner's head. That's my visual reference for "mod 5".

This is basically what people are referring to at Microsoft when they use the term "modulo" as I first quoted it. They mean, if you lop off all that other stuff, you are left with what I told you. Technically it would only be correct if the unexpected overhead was larger than the original project; if your project was 17 days and the API review was 3 days, then doing a modulo operation would leave you with 2 days...but if the overhead comes in blocks of 20 days, say, then that use of "modulo" precisely matches the way the word is used in computer science -- although not the way it is used in mathematics.

Posted by AdamBa at January 10, 2005 03:02 PM

TrackBack URL for this entry:
http://proudlyserving.com/cgi-bin/mt-tb.cgi/132

An interesting case is when you consider negative numbers participating in the division -- remainders are not well defined in this case.

Knuth defines modulus as the amount by which the number exceeds the largest integer multiple of the divisor that is not greater than that number.

In other words,

x % y = x - y * floor(x/y)

where the division can give fractional results (not integer division), and floor(x) is the largest integer value less than or equal to x.

Therefore

7 % 5 = 2,
-13 % 4 = 3, and
13 % -4 = -3.

Sadly however, programming languages in general have been inconsistent in this respect. They would have done well to follow Knuth's advice.

--Kaushik

Posted by: Kaushik at January 12, 2005 12:33 AM