10th April 2020
Recently I started a 30 day Coding Challenge on LeetCode and came across a use case for the modulo operation. I had seen it applied to the same problem before, but I had not really appreciated how versatile this operation is until then. I will explain what the use case was later on, but first I would like to go through some concepts related to division that most of us hopefully learnt in school.
What is the modulo?
The modulo operation gives the remainder of the division of an integer number by another. But what does this mean? Let's consider two numbers
>>> dividend = 12>>> divisor = 4
If we divide
divisor using the
/ operator in Python 3 we will get a rational number, or a floating-point number as it is better known in computer science:
>>> dividend / divisor3.0
If we want to work with integers we can use the
// operator which will return the quotient of the division.
>>> quotient = dividend // divisor>>> quotient3
The quotient is the number of times the divisor needs to be added up to get the dividend. Thus, if we multiply the divisor times the quotient we get the dividend as a result. However, this is only true for an exact division, in which the result can be expressed as an integer:
>>> dividend = 15>>> divisor = 5>>> quotient = dividend // divisor>>> quotient3>>> dividend == divisor * quotientTrue
For a division that returns a rational number, we will not be able to get the dividend by just multiply the divisor by the quotient:
>>> dividend = 15>>> divisor = 6>>> quotient = dividend // divisor>>> quotient2>>> dividend == divisor * quotientFalse
The missing value is the remainder, which is the amount that needs to be added to the divisor times the quotient to obtain the dividend. We can find the remainder by subtracting the divisor times quotient from the dividend.
>>> ...>>> remainder = dividend - divisor * quotient>>> remainder3
The equation in the code snippet above is equivalent to the one described by the Euclidean division theorem. We can rewrite the equation to obtain the dividend:
...>>> dividend == divisor * quotient + remainderTrue
Finally, the quotient and remainder can be computed by using the Division algorithm, which is beyond the scope of this post but I recommend to look into and promise it is straightforward.
Mod in programming
Most high-level programming languages have operators that we can use to obtain both the quotient and the remainder of a division. In Python 3, the
// operator we discussed before will give the quotient, and the mod operator
% will give the remainder. We can directly compute the remainder for the previous division example with the mod operator:
>>> ...>>> remainder = dividend % divisor>>> remainder3
The mod operation is convenient, as we can use it to obtain the remainder of a division instead of having to implement the Division algorithm from scratch. It is also important to notice that for exact divisions the result of a mod operation is
0 because there is no remainder. For example:
>>> dividend = 16>>> divisor = 4>>> dividend % divisor0
Now we are ready to dive into some of the practical applications of the mod operation. Below I will highlight some of the applications of this operation in software development. I am sure there are many more, but these will hopefully give you an idea on the types of problems you can solve by using it.
Check if a number is even or odd
This is an basic example that is widely used. A integer number is considered even if the result of a division of that number by 2 is an integer number. In other words the number is exactly divided by 2, or division by 2 has no remainder.
With that in mind, if you want to check whether a number is even or odd (a number that is not even), simply apply a "mod 2" operation to the number and check if the remainder is 0 for an even number or 1 for an odd number. Some examples of this property are shown below:
10 % 20 # 10 is an even number15 % 21 # 15 is an odd number
Dynamically render a grid layout
I used this approach a some years ago when working on a mobile application. The goal was to create an scrollable grid with 3 items per n rows to display images. You can think of your phone's photo library to get an idea of what I built. I used React Native as development framework along with a library called react-native-easy-grid that is built on top of Flexbox and provides a markup language to define responsive layout structures. As an example, a grid with 2 rows and 3 items per row can be rendered using the library as follows:
<Grid><Row><Col>Item 1</Col><Col>Item 2</Col><Col>Item 3</Col></Row><Row><Col>Item 1</Col><Col>Item 2</Col><Col>Item 3</Col></Row></Grid>
In order to create a grid and dynamically place elements in rows of 3 items each by using the language described above, with an array of items as an input, I needed to know when each row ended and the next one started. This was in order to correctly place closing and opening tags for Row elements.
By calculating "mod 3" of the index of an item in the original array, we can obtain the position of such item in its corresponding row. This property is illustrated in Figure 1 below. Figure 1. Grid showing each element index and row index
The index for each item "modulo 3" will give us the index or position of the item in its containing row. Notice that this works if we consider the first position in a row to be the 0th, which happens to be the standard in most programming languages for array indexing.
Extract 'n' last digits from a number
This was the use cas that made me think deeper about the modulo operation and inspired me to write this article. Fortunately, It does not require as much context as the previous example. This property allows us to get the last digits from a given integer number by applying a
mod n operation to the given number, where
n is equal to the powers of 10. The amount of zeroes in
n is equal to the number of digits we will get from the input number. In other words, by applying
mod 10 we will get the last digit of the number, with
mod 100 we will get the last two digits, and so on.
We can quickly verify this property with some code.
>>> 1234 % 104>>> 1234 % 10034>>> 1234 % 1000234>>> 1234 % 100001234
This is a simple yet efficient way of deconstructing numerical values without having to do operations such as parsing the number to an array and fetching the last n elements, which can be more computationally expensive.
We have done a quick revision on arithmetic. Remainders are a basic mathematical concept yet it finds its way into many real-world applications. There are more examples of this operation in real life, e.g. translating a 12-hour into a 24-hour clock time, however I hope the few examples I have shown convey how versatile this operation is and different scenarios where it can be used.
Update 30-07-2020: I have updated this article by correcting my use of mathematical terminology as it was a bit loose in some instances. I have also added clearer code snippets and provided links to relevant mathematical definitions. This update was partly motivated by my recent dive into Modular Arithmetic which is the branch of Number Theory that deals with remainders. I recommend you to follow the link through if you want to better understand the mathematical foundations of the modulo operation.