Clojure has two functions for finding the remainder in integer division: rem and mod. Turns out, many other languages also have remainder and modulus functions.

Why? What the heck? What's the difference?

At first blush, these functions seem the same:

 (rem 5 3)
 => 2
 
 (mod 5 3)
 => 2
 
 (rem -5 -3)
 => -2
 
(mod -5 -3)
=> -2

This sameness only holds when the arguments are both positive or both negative.

Check this out:

 ;; negative numerator, positive divisor
 (rem -5 3)
 => -2
 
 (mod -5 3)
 => 1
 
 ;; positive numerator, negative divisor
 (rem 5 -3)
=> 2

(mod 5 -3)
=> -1

If one of the arguments is negative, we get different results from rem and mod. Not only that, we get different results within rem and mod depending on whether its the numerator or divisor that is negative.

Why are there two functions? Why isn't there just one way to calculate a remainder like I learned in school? When do you want to use one over the other?

I thought these questions would be easy to answer. There are certainly a lot of answers but not many were complete.

The first level answers

These are the two most common and useful answers I found:

1. mod is different because it returns a remainder that reflects the sign of the divisor.

2. mod floors the quotient toward negative infinity while rem truncates the quotient toward zero.

The first explanation is true and it answers my second question, "When do you want to use rem over mod?" by saying, "Use mod when you want the remainder to have the same sign as the divisor."

This explanation implies that the reason there are two different functions is because you might want the results to be different in these certain cases.

As far as explanations go, it falls flat. What's the motivation? Humans made this! What were they thinking? Is there a Hollywood heist movie behind this - computer programmer replaces rem with mod to siphon off remainders of the stock market?

I disqualify the first explanation because it doesn't satisfy my "why" questions.

The second explanation provides a little more information about the decision (flooring vs truncating) that results in the first explanation.

I'm still not satisfied with "why" we have two ways to calculate the remainder but first, I want to take a quick detour into integer division and the concepts of flooring and truncating.

Integer division: what's happening inside rem and mod

When I first learned about rem and mod, I was surprised that there are multiple ways to calculate a remainder.

I am much more surprised that I was surprised. I have a math degree, shouldn't I know this? I spent years in elementary school carrying out division and manipulating fractions - why didn't I notice then? Did I forget that I knew this once? I really don't know.

Are rem and mod based on the the division algorithms we learn in school? What did we learn in school?

I learned a simplified version of integer division.

The convention is to return the value of x that satisfies the congruence and lies between 0 and m. (source)

 ;; division: -5/3 = 5/-3 -1.66
 
 ;; - / + negative numerator, positive divisor
 
 ;; integer division: -5 = (3 * -1) + (-2)
 (rem -5 3)
 => -2
 
 ;; integer division: -5 = (3 * -2) + 1
;; -2 is closer to negative infinity than the -1 quotient provided by `rem`
(mod -5 3)
=> 1

;; + / - positive numerator, negative divisor

;; integer division: 5 = (-3 * -1) + 2
(rem 5 -3)
=> 2

;; integer division: 5 = (-3 * -2) + (-1)
;; -2 is closer to negative infinity than the -1 quotient provided by `rem`
(mod 5 -3)
=> -1

Use case: bucketing values

Remainders are a way for us to identify groups of numbers.

 (mod 3 -3)
 => 0
 
 (mod 2 -3)
 => -1
 
 (mod 1 -3)
 => -2
 
(mod 0 -3)
=> 0

(mod -1 -3)
=> -1

You can see a pattern emerge in the remainders. Because we're dividing by -3, our remainder can only ever be between 0 and -3. We can group {0, 3} together because they both have remainder 0 when divided by -3, same with {-1, 2}.

Doesn't rem do the same thing?

 (rem 3 -3)
 => 0
 
 (rem 2 -3)
 => 2
 
 (rem 1 -3)
 => 1
 
(rem 0 -3)
=> 0

(rem -1 -3)
=> -1

(rem -2 -3)
=> -2

Nope! Because rem is flooring to zero, it starts a new cycle of remainders when it passes 0. -1 and 2 are no longer in the same group.

Why would we want to group numbers based on their remainders?

Use case: limiting a function range

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 rem and mod 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 don't remember learning multiple ways to calculate a remainder in school 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 the 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.

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

Following this algorithm, we can generate other valid solutions.

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

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

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

(-1 * -3) + 2 = 5

Negative remainders

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

or

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 but…

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.

How do you choose a solution?

In the above scenario, my preferred remainder 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.

What if we flip the signs of our numbers?

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

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

Frankly, I don't know how to explain what the above equations mean in real-world terms. We'll come to a better example of a negative divisor in minute.

Choosing a Solution Again

Which solution should I choose?

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

That means I use either

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

or

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

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.

The mathematicians prefer that I ask my friends for 2 iPhones each so that I have one extra.

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.

 ;; positive numerator, positive divisor
 (rem 5 3)
 => 2
 
 (mod 5 3)
 => 2
 
 ;; negative numerator, positive divisor
 (rem -5 3)
=> -2

(mod -5 3)
=> 1

;; positive numerator, negative divisor
(rem 5 -3)
=> 2

(mod 5 -3)
=> -1

;; negative numerator, negative divisor
(rem -5 -3)
=> -2

(mod -5 -3)
=> -2

;; also note the zero cases
(rem -5 0)
=> java.lang.ArithmeticException: / by zero

(mod -5 0)
=> java.lang.ArithmeticException: Divide by zero

;; 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.

 (source rem)
 (defn rem
   "remainder of dividing numerator by denominator."
   {:added "1.0"
    :static true
    :inline (fn [x y] `(. clojure.lang.Numbers (remainder ~x ~y)))}
   [num div]
     (. clojure.lang.Numbers (remainder num div)))
 => nil

(source mod)
(defn mod
  "Modulus of num and div. Truncates toward negative infinity."
  {:added "1.0"
   :static true}
  [num div]
  (let [m (rem num div)]
    (if (or (zero? m) (= (pos? num) (pos? div)))
      m
      (+ m div))))
=> 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.

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

mod considers three cases. Here are the first two:

• 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

Thirdly, the else case. After eliminating the first two cases, we have a non-zero remainder and the numerator and divisor have opposing signs.

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

 ;; negative numerator, positive divisor
 (rem -5 3)
 => -2
 
 (mod -5 3)
 ;; (+ (rem -5 3) 3)
 ;; (+ -2 3)
 => 1
 
;; positive numerator, negative divisor
(rem 5 -3)
=> 2

(mod 5 -3)
;; (+ (rem 5 -3) -3)
;; (+ 2 -3)
=> -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.