Web-Frickin'-Log - In Search of the True Modulus (an epic)

RSS Bot · May 27, 2008

So, at my office, we like to argue about programming concepts. Usually I bring them up as they relate to math, since I know more stupid little things about math than my co-workers, whereas they have a great deal more experience than me in just about everything else since they're all 30ish and have one foot in the grave. Anyway, here's a question (paraphrased) I posed to an interviewee:

In PHP and JavaScript (and probably other languages), the modulus operator is not implemented correctly. Mathematically speaking, it should always return a positive integer, regardless of the operand (or whatever the thing on the left is called). For example,
-5 % 7
should give us 2, but instead it gives us -5. Write a function that correctly calculates the modulus given an operand (or whatever the thing on the left is called) and a modulus (the thing on the right).

Sadly, the interviewee was... misfortunate, and couldn't solve this, even though I practically wrote the answer on the white board.

An answer (in PHP):

function truemod($num, $mod) {
 $return = $num % $mod;
 if ($return < 0) {
$return += $mod;
 }

 return $return;
}

The follow-up to this (what I thought was a decidedly easy) question was going to be, "now do it without a conditional."

An answer (in PHP):

function truemod($num, $mod) {
 return ($mod + ($num % $mod)) % $mod;
}

We didn't quite get that far, however, since the interviewee gave up instead of translating "-5 + 7" (what I wrote on the board as I was trying to prod him into an answer) into a function.

Anyway, I had run into this problem before, mainly when dealing with calendars, and had to hack my way to a solution. I brought it up to my coworkers, and what followed was a heated argument about whether "Tommy is wrong because -5 % 7 in Java is -5" (paraphrased). Since my coworker was slightly belligerent, and I found it kind of insulting, I gave him the mathematical answer, which is correct-ish, since I took group theory two and a half years ago and haven't used it since:

Consider Z₇, the group of integers modulu 7 (co-workers: "What's a group?"), i.e. [0,1,2,3,4,5,6]. Notice the lack of negative numbers (co-workers: "What about 7?"). An additive identity is an element in the group 0 such that
a + 0 = a
.

An additive inverse is an element in the group b such that
a + b = 0
(co-workers: *stunned silence*).

Now, since Z₇ is a group, that means it's closed under addition, and hence the sum of 5 and 3 must also be in the group. But since 5+3 = 8 is not in the group, we take the modulus of 8 to get 2 (co-workers: "I told you can only take the modulus of positive numbers..."). Z₇ is also closed under subtraction, so 3 - 5 must also be in the group, but it can't be -2, since -2 is not in the group. So we use the notion of additive inverses and discover that the additive inverse of 2 is 5, so 3 - 5 = -2 = 5 mod 7. Hence, -5 % 7 is 2.

(co-workers: "Tommy is full of crap").

However inaccurate that explanation was, they didn't really buy it, but I only wrote it up to be facetious, and wasn't really meant to be taken seriously.

We ended up finding "bug" reports for both Java and PHP where people were complaining that the modulus operator wasn't accurate: it was returning negative numbers when that's not possible (for the very reasons that I so eloquently stated above). We eventually discovered the reason:

Some languages truncate integer division toward zero, which means that, for example, 15/7 = 2 and -15/7 = -2. Java, PHP, JavaScript, C#, SQL and probably (I don't have a C compiler) C/C++ work this way. These are the languages in which -5 % 7 = -5. Other languages truncate toward negative infinity (i.e. they always take the floor), which means that 15/7 = 2 and -15/7 = -3. Perl, Python, Ruby, Lisp, Haskell and Lua all work this way. These are the languages in which -5 % 7 = 2.

In conclusion, it was a stimulating exercise. Can anybody give examples of other languages and their modulus operators?

Fun time!! Try it yourself! (No, I don't know Haskell; I learned enough of it in 10 minutes to install a compiler and run one command)

PHP:		  
<?php echo -5%7; ?>

JavaScript : (why do I need a space there to be able to write "JavaScript" as one word?)
alert(-5%7)

Java:
public class mod {
public static void main(String [] args) {
	System.out.println(-5%7);
}
}

C#:
class mod {
static void Main(string[] args) {
	System.Console.WriteLine(-5 % 7);
}
}

SQL:
SELECT -5%7

Ruby:
puts -5%7

Perl/Python:
print -5%7

Lua:
io.write(-5%7);

Lisp:
(mod -5 7)

Haskell:
-5 `mod` 7

http://www.atariage.com/forums/index.php?a...;showentry=4910