Leftovers: What's the difference between Clojure's rem(ainder) and mod(ulus) functions?

November 29, 2018

This morning, I happened across this basic Clojure exercise:

Using REPL documentation functions, find the documentation for the rem and mod functions. Compare the results of the provided expressions based on the documentation.

from: https://clojure.org/guides/learn/syntax

rem is "…the integer "left over" after dividing one integer by another to produce an integer quotient (integer division)."

mod stands for modulus or modulo operation which is defined as "… the operation that produces such a remainder when given a dividend and divisor."

Sounds like they do the same thing, so what's the difference?

Turns out this question is asked a lot in programming because functions for remainder and modulus vary between language. Language designers had to make a choice about how to implement these mathematical concepts.

I didn't remember there being a choice for how to calculate a remainder so I did some digging. The following is a summary of what I learned. I tried to keep it easy-to-understand and memorable so that I won't forget it a second time.

You can skip a refresher on integer division if you just want to know what the difference is between rem and mod in Clojure.

My main source of understanding came from an excellent run down by Eric Lippert on the Microsoft Developer blog from 2011.

Why do we divide things?

Division is dividing something up into equal parts. 10 pies divided amongst 4 people means each person can have 2.5 pies. That's great. We're all happy.

Sometimes the objects we're dividing aren't useful when we cut them into parts. Half a pie is still tasty but half an iPhone is not usable.

That's why we invented integer division - iPhones. (j/k)

If we have 5 iPhones and 3 people, how many iPhones can each person have so that each person has the same number of iPhones?

Remember, we want to make sure each person has an equal amount, to avoid fighting.

When we have more objects than people, then we have leftover iPhones, a remainder.

5 / 3 = 1 iPhone per person, with 2 leftover iPhones.

5 / 3 = 1, remainder 2.

We can flip this equation around to say:

(1 iPhone per person * 3 people) + 2 leftover iPhones = 5 iPhones.

(1 * 3) + 2 = 5

When we learn about these concepts in math class or when we're out in the world dividing up pies and iPhones, the leftover, or remainder, is always positive. We don't have negative pies or iPhones, or do we?

Wouldn't it also be true to say, that each person could have 2 iPhones but one person would have to give up one of their two iPhones?

(2 iPhones per person * 3 people) + (-1 iPhone) = 5 iPhones.

(2 * 3) + (-1) = 5

5 iPhones divided by 3 people = 2 iPhones per person, with one iPhone returned.

5 / 3 = 2, remainder -1.

This is conceptually possible (being short an iPhone) and mathematically correct.

I don't know about you, but I'd prefer to tell my friends they can each have one iPhone and hide the extras rather than tell them they are entitled to two as long as we agree that someone won't get their second.

There are endless other solutions that are less useful. For example, 5 / 3 = 20, remainder -55. I give each of you 20 iPhones but altogether you've got to give me 55 of them back? It works on paper…

Choosing a Solution

I've been talking about iPhones because I want to convince you that there are many possible solutions. We don't think about it much because we have a preference for certain solutions over others.

In my case, my preferred solution is:

positive (To maintain peace and keep things simple.)
small (I can't afford 60 iPhones even if I'm going to return 55.)

This matches what mathematicians use to define integer division.

The answer should be the least positive remainder.

What about negative numbers?

We can consider a negative iPhone is an iPhone owed, lent, or given away.

Imagine we can construct a mega iPhone from 5 iPhones. I'll call it a MEGAPhone. I need convince my friends to lend me their iPhones so I can create a MEGAPhone.

We could have:

1) -5 / 3 = -1, remainder -2

3 people contribute 1 iPhone each and we're still 2 iPhones short for our MEGAPhone.

Or maybe…

2) -5 / 3 = -2, remainder 1

3 people contribute 2 iPhones each for a total of 6 loaned iPhones, which is 1 iPhone more than we needed.

Or we can get creative:

3) -5 / 3 = -10, remainder 25

Each person contributes 10 iPhones. We have lots extra.

Choosing a Solution Again

Which solution do I prefer?

In this example, I'd rather not be short an iPhone because the MEGAPhone isn't a MEGAPhone with just 4 loaned iPhones.

So I prefer having a positive remainder.

But imagine I can only get 1 iPhone from each friend. Then I need to know, "How many iPhones do I need to provide personally?" In that case, I want to know that I am 2 iPhones short, remainder -2.

If we go back to the mathematicians, they further define integer division as returning the least absolute remainder.

So take the absolute value (an operation which turns negatives to positives) of the remainder. You want that to be as small as possible.

Why doesn't this sound like what I was taught in school?

To be honest, all I remember is carrying out long division on positive integers and having a remainder.

I can't recall anything about finding the least absolute remainder.

Do you remember learning that there are multiple ways to divide a number when you can play with the remainder? Or that you should take the absolute value of your remainder?

Let me know, I'm curious what you remember from school.

The difference between `rem` and `mod` in Clojure

I'll run a couple experiments to show the difference before I talk about it.

 1;; positive numerator, positive divisor
 2(rem 5 3)
 3=> 2
 4
 5(mod 5 3)
 6=> 2
 7
 8;; negative numerator, positive divisor
 9(rem -5 3)
10=> -2
11
12(mod -5 3)
13=> 1
14
15;; positive numerator, negative divisor
16(rem 5 -3)
17=> 2
18
19(mod 5 -3)
20=> -1
21
22;; negative numerator, negative divisor
23(rem -5 -3)
24=> -2
25
26(mod -5 -3)
27=> -2
28
29;; also note the zero cases
30(rem -5 0)
31=> java.lang.ArithmeticException: / by zero
32
33(mod -5 0)
34=> java.lang.ArithmeticException: Divide by zero
35
36;; I'm not sure yet why one error uses `/` and the other uses `Divide`, feel free to email me if you have an idea or the answer.

rem and mod act the same when the numerator and divisor are the same sign (negative or positive).

Why do they act differently when the numerator and divisor have opposing signs?

Let's investigate the source code.

 1(source rem)
 2(defn rem
 3  "remainder of dividing numerator by denominator."
 4  {:added "1.0"
 5   :static true
 6   :inline (fn [x y] `(. clojure.lang.Numbers (remainder ~x ~y)))}
 7  [num div]
 8    (. clojure.lang.Numbers (remainder num div)))
 9=> nil
10
11(source mod)
12(defn mod
13  "Modulus of num and div. Truncates toward negative infinity."
14  {:added "1.0"
15   :static true}
16  [num div]
17  (let [m (rem num div)]
18    (if (or (zero? m) (= (pos? num) (pos? div)))
19      m
20      (+ m div))))
21=> nil

Discussing the source of rem is beyond the scope of this article. The implementation of rem was set first, and mod was created to offer a different choice in case the definition of rem doesn't suit your purposes.

Let's look at how mod utilizes rem and what creates the difference.

1(let [m (rem num div)]
2    (if (or (zero? m) (= (pos? num) (pos? div)))
3      m
4      (+ m div))))

mod considers three cases:

the remainder is 0 => just return 0, end of story
the numerator and divisor are the same sign (either both positive or both negative) => return the remainder; act just like rem

Lastly, the else case. Based on elimination, the else case is when the remainder is non-zero and the numerator and divisor have opposing signs.

In this else case, (+ m div), add the divisor to the remainder.

 1;; negative numerator, positive divisor
 2(rem -5 3)
 3=> -2
 4
 5(mod -5 3)
 6;; (+ (rem -5 3) 3)
 7;; (+ -2 3)
 8=> 1
 9
10;; positive numerator, negative divisor
11(rem 5 -3)
12=> 2
13
14(mod 5 -3)
15;; (+ (rem 5 -3) -3)
16;; (+ 2 -3)
17=> -1

As a result, mod gives us a least absolute remainder.

I actually don't have a nice way to wrap this up. From what I can tell, mod aligns with Wikipedia and Wolfram Alpha, which must be the indisputably true way.

So, how did rem originate? Why can mod rely on this simple bit of addition to create a least absolute remainder from rem?

Stay tuned.

Nicki Vance