The Curious Case of Division Remainders
When we learned division in the early years of elementary school (especially "long division"), we discovered that numbers cannot always be divided perfectly. Sometimes there's a remainder. For instance, when dividing 6 by 4, we can fit only one 4 into 6, but that doesn't mean 6 divided by 4 is simply 1. There's still a remainder of 2, or, for the more precise among us, the result might be stated as 1.5. As it turns out, calculating the remainder—though it seems simple and obvious—can sometimes become unexpectedly complicated. So, let's analyze this operation: break it down into its fundamental parts and explore what might vary, and why, despite differing results, everything is still correct.
Before We Dive In...
This article is a translation of a post I originally wrote in Polish for my blog. If you speak Polish, you might prefer reading the original version here: https://swistak.codes/post/dziwny-przypadek-reszty-z-dzielenia.
The Programming Problem with the Remainder of Division
In the introduction, I described what a remainder of division is. However, to better understand why issues might arise, let's experience it firsthand. For our example, we'll perform four operations:
To clarify, is the operation used to calculate the remainder of division. We'll consider how this operation behaves in three programming languages: Dart, Python, and C (in two variations).
Dart
In the Dart programming language, we execute the following source code (available here on Replit):
void main() {
print('8 mod 5 = ${8 % 5}');
print('-8 mod 5 = ${-8 % 5}');
print('8 mod -5 = ${8 % -5}');
print('-8 mod -5 = ${-8 % -5}');
}
Results:
8 mod 5 = 3
-8 mod 5 = 2
8 mod -5 = 3
-8 mod -5 = 2
Python
Next, let's try the following code in Python (available here on Replit):
print('8 mod 5 = {}'.format(8 % 5))
print('-8 mod 5 = {}'.format(-8 % 5))
print('8 mod -5 = {}'.format(8 % -5))
print('-8 mod -5 = {}'.format(-8 % -5))
Results:
8 mod 5 = 3
-8 mod 5 = 2
8 mod -5 = -2
-8 mod -5 = -3
C
Finally, let's see how it works in the C programming language. In C, we can calculate the remainder of division in two ways, so we'll include both methods in our code (available here on Replit):
#include <stdio.h>
#include <math.h>
int main(void) {
printf("First method (operator %%):\n");
printf("8 mod 5 = %d\n", 8 % 5);
printf("-8 mod 5 = %d\n", -8 % 5);
printf("8 mod -5 = %d\n", 8 % -5);
printf("-8 mod -5 = %d\n", -8 % -5);
printf("Second method (remainder function):\n");
printf("8 mod 5 = %0.f\n", remainder(8, 5));
printf("-8 mod 5 = %0.f\n", remainder(-8, 5));
printf("8 mod -5 = %0.f\n", remainder(8, -5));
printf("-8 mod -5 = %0.f\n", remainder(-8, -5));
return 0;
}
Results for the first method:
8 mod 5 = 3
-8 mod 5 = -3
8 mod -5 = 3
-8 mod -5 = -3
Results for the second method:
8 mod 5 = -2
-8 mod 5 = 2
8 mod -5 = -2
-8 mod -5 = 2
What's Going On?
To summarize, in these three programming languages, it turned out that for the seemingly simple operation of calculating the remainder of division, we obtained the following results:
At first glance, this seems like a serious inconsistency: we keep getting either 3 and -2 or 2 and -3. Moreover, the results are distributed differently across the four cases. From a mathematical point of view, a function should always return the same result for given arguments. Here, however, the outcome depends on the programming language, leading to different results. Curious to know why—and which result is mathematically correct? Read on to find out.
Euclidean Definition
Let's start with how the remainder of division is commonly defined in mathematics. It is described in the theorem of division with remainder, also known as Euclidean division.
This theorem states that for integers and , where , there exist integers and such that:
is the absolute value of , which means, in simple terms, removing the sign from the number (positive stays positive, and negative becomes positive).
While this formula may not be familiar to you, you surely recognize its components by their names:
- — dividend (the number being divided),
- — divisor (the number we divide by),
- — quotient (the result of division, as an integer),
- — remainder of the division.
From this definition, we can immediately dismiss all negative results as incorrect. So, what is the formula for the remainder of division? The most common interpretation derived from the above definition is as follows:
is the floor function, which means rounding down—or, as many simplify it, truncating the fractional part and keeping only the integer part. This is where trouble starts with negative numbers. Why?
Logically, if we truncate the fractional part from (the result of dividing 8 by 5 when one of the numbers is negative), we should get . That’s why simplifying the floor function definition this way is poor and misleading. can be rounded either to or to . Rounding down always means rounding to the smaller number, which in this case is , contrary to what intuition might suggest. Hence, in the cases shown earlier, we are dealing with only two correct ways of calculating the remainder:
However, you may have noticed a discrepancy here. The formula given above also yields results of and . These results are, of course, incorrect because the remainder should always be positive. This is where the problem with the definition arises, leading to multiple interpretations when we want to calculate the remainder for every possible case.
If we assume that remainders can only be positive, we could conclude here by stating that, among all the programming languages shown above, only Dart correctly calculates the remainders of division. However, that would be too simple. So, let’s explore how programming languages implement the remainder operation and see how these errors arise.
Computational Implementations
In computer science, several algorithms for calculating the remainder of division are used, each of which is correct in its own way. This is because computational systems use a slightly simplified definition of division with remainder:
The condition that the remainder must be greater than or equal to zero is dropped; instead, only its absolute value must be less than the divisor. This distinction is important because, for a divisor of , a remainder of is perfectly valid (since the absolute value of is ).
Let’s now explore the implementations.
Truncated Division
In this type of division, we use the trunc
function (short for truncation) to perform rounding. It involves literally cutting off the fractional part, meaning and .
The formula for the remainder of division is as follows:
Let’s verify our test cases using this formula:
It’s important to remember that in this approach, the result of the modulo operation always has the same sign as the dividend, and the absolute value of the remainder is consistent. This method is by far the simplest to implement and computationally the easiest for the computer, because the integer division operation (which ignores the fractional part and remainder) works exactly as if the division were wrapped in the trunc
function.
This is precisely how the modulo operation is implemented in the C language. Similarly, many other languages, including C++, C#, Go, JavaScript, PHP, Swift, and Visual Basic, follow this approach.
Floor Division
When discussing Euclidean division, I demonstrated that the remainder of division can be calculated using division with the floor function. This is also the method suggested by Donald Knuth in his The Art of Computer Programming. Let’s recall the formula:
Importantly, following Knuth's approach, we do not require the remainder to be greater than or equal to zero. On the contrary, the author of The Art of Computer Programming explicitly states that:
- If , then ,
- If , then .
Let’s verify our test cases:
In this case, the result of the operation always takes the sign of the divisor. For this reason, it does not align with the mathematical definition. However, this method is widely used, primarily because the formula with the floor function is one of the most popular for calculating remainders.
Returning to the code snippets shown earlier, the most notable programming language that implements the modulo operation this way by default is Python. Additionally, this operation is defined similarly in Lua, Perl, R, Ruby, Scratch, TCL, and popular spreadsheet software.
Division with Rounding
Another definition is the one presented in the IEEE-754 standard (the standard for floating-point arithmetic). According to this definition, instead of the floor function, we use standard rounding to the nearest integer:
As you might guess, this method still encounters negative numbers, so it does not align with the mathematical definition. Nevertheless, let’s test our four cases:
Here, we deviate significantly from results that follow the mathematical definition, making this method the least commonly used. When it is used, it is typically as an alternative to the standard modulo operation, as demonstrated in the case of the C language. However, because this method is part of one of the most important standards in computer science, it is worth mentioning.
Euclidean Division According to R.T. Boute
All the previously mentioned methods calculate the remainder of division, but none of them do so in a mathematically correct way. According to the mathematical definition, the remainder of division should always be positive, which none of the presented formulas guarantee. This issue was resolved by R.T. Boute in his 1992 work (doi:10.1145/128861.128862).
We start with either of the two definitions—truncated or with the floor function—because for positive numbers, they always yield correct results. However, for the remaining cases, the behavior is defined as follows:
Alternatively, an equivalent formula can be applied:
Does this formula ensure results consistent with the mathematical definition? Let’s verify:
The results in each case are correct, so we have ultimately derived a formula consistent with the mathematical definition. However, among programming languages, this approach is not very common. Of the examples shown at the beginning of this article, Dart calculates in this way, as do languages like ABAP, Maple, or Pascal (not in all implementations).
Transforming the Truncated Form
Since the truncated form is the most common method for calculating the remainder of division in programming languages, we may want to transform this form into another, particularly the Euclidean form.
Algorithm E
Algorithm E allows us to transform the remainder of division calculated using the trunc
operation into a Euclidean-compliant result. The mathematical formula is as follows:
In code (JavaScript), we could represent this fairly simply as follows:
function mod(a, b) {
let r = a % b;
if (r < 0) {
if (b > 0) {
r = r + b;
} else {
r = r - b;
}
}
return r;
}
Let’s test its operation "on paper." If you need to recall the values we need to adjust, refer to the results from the C language. Here are the calculations:
As you can see, we were able to quickly correct the results obtained in the vast majority of programming languages, making them consistent with the mathematical definition of the remainder of division.
Algorithm F
The Euclidean form is the most important, but if, for some reason, you want to transform the truncated form into the result as in floor division, you can use Algorithm F. It is defined as follows:
The code for this algorithm in JavaScript is as follows:
function mod(a, b) {
let r = a % b;
if ((r > 0 && b < 0) || (r < 0 && b > 0)) {
r = r + b;
}
return r;
}
Let’s manually test this formula again:
If we recall the results returned by Python, everything matches. However, it’s worth noting that, in practice, the previous algorithm is likely to be more useful than this one.
Summary
As you may have noticed, an operation as seemingly simple and straightforward as calculating the remainder of division can be more complex than it first appears.
When implementing the modulo operation in algorithms, always check whether negative numbers might be involved and determine what results should be returned in such cases. In a previous article on calculating the day of the week, I highlighted this issue, but it’s a consideration that applies to many other algorithms and mathematical formulas as well.
References
- Knuth, D. E., „Integer Functions and Elementary Number Theory” The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition. Addison-Wesley, 2020, pp. 39-45
- Raymond T. Boute. 1992. The Euclidean definition of the functions div and mod. ACM Trans. Program. Lang. Syst. 14, 2 (April 1992), 127–144. doi:10.1145/128861.128862
- "IEEE Standard for Floating-Point Arithmetic," in IEEE Std 754-2019 (Revision of IEEE 754-2008), vol., no., pp.1-84, 22 July 2019, doi:10.1109/IEEESTD.2019.8766229.
- Leijen, Daan. "Division and modulus for computer scientists." (2003).