Saturday, 16 Oct 2021

# Modulo Operations in Programming With Negative Results

In programming, the modulo operation gives the remainder or signed remainder of a division, after one integer is divided by another integer. It is one of the most used operators in programming. This article discusses when and why the modulo operation yields a negative result.
Examples:
In C, 3 % 2 returns 1. However, -3 % 2 is -1 and 3 % -2 gives 1.
In Python, -3 % 2 is 1 and 3 % -2 is -1.
Hence, it’s evident that the same expression of -3 % 2 gives different results in different programming languages. This result is more related to mathematics rather than programming. The mathematics mentioned here will help in understanding the questions a little more easily. To understand why this happens, a little knowledge about Euclidean Division and a few points related to Modular Arithmetic is needed.
Euclidean Division: In arithmetic, Euclidean division or division with the remainder is the process of dividing one integer (the dividend) by another (the divisor), in such a way that it produces a quotient and a remainder smaller than the divisor.
Given two integers a and b ( where b ≠ 0 ), there exists unique integers q and r such that:
a = bq + r ( 0 ≤ r < |b| ) where, |b| denotes the absolute value of b. In the above equation, each of the four integers has its own name i.e., a is called the dividend. b is called the divisor. q is called the quotient. r is called the remainder. For Example: If a = 9 and b = 4, then q = 2 and r = 1, since 9 = 4 × 2 + 1. If a = -9 and b = 4, then q = -3 and r = 3, since -9 = 4 × -3 + 3. If a = 9 and b = -4, then q = -2 and r = 1, since 9 = -4 × -2 + 1. If a = -9 and b = -4, then q = 3 and r = 3, since -9 = -4 × 3 + 3. Explanations of the above examples: The first example is self-explanatory as 9/4 gives quotient 2 and remainder 1. The second example (-9/4) gives quotient -3 and not -2. This happens because if we take -2 as quotient then -9 = 4 × -2 + (-1). A remainder of -1 is generated which does not fulfill the conditions of the Euclidean division. It doesn’t make -9/4 = -2 wrong it is just not what we need in this case. Modular Arithmetic: In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” when reaching a certain value, called the modulus. Congruence: Given any integer N, called a modulus, two integers a and b are said to be congruent modulo N if they produce the same remainder when divided by N i.e., a = pN + r and b = qN + r, where 0 ≤ r < |N| is the common remainder. Congruence modulo N is denoted as a ≡ b (mod N) where the parentheses means that (mod N) applies to the entire equation, not just to the right-hand side ( here b). Examples:-5 ≡ 2 (mod 7) -14 ≡ 19 (mod 11) Analyzing the first example. -5 = 7 × -1 + 2 and 2 = 7 × 0 + 2. Both -5 and 2 leave the same remainder 2 when divided by 7. Hence, they are congruent to each other. Similarly, -14 = 11 × -2 + 8 and 19 = 11 × 1 + 8. Both -14 and 19 leave the same remainder 8 when divided by 11. Hence, they are congruent to each other.  Congruence Classes: Suppose a mod N leaves a remainder r when divided by N satisfying the condition 0 ≤ r < |N|.  The set of all the integers congruent to a mod N is called the congruence class of the integer a mod N. For Example: The congruence class of 3 mod 2 is {…, -5, -3, -1, 1, 3, 5, 7, … }. The congruence class of 7 mod 4 is {…, -9, -5, -1, 3, 7, 11, … }. Select any integer from the congruence class of the integer a mod N as a representative of that class. In mathematics, the least positive residue, the smallest non-negative integer that belongs to that class is chosen as the representative. For Example:  The representative of congruence class 3 mod 2 is 1. The representative of congruence class 7 mod 4 is 3. The Least positive residue is chosen because it is the remainder produced after the Euclidean division. Representative is chosen by Programming languages: If both a and N are positive, in all the programming languages, a mod N is the remainder of the Euclidean division. However, the difference in the result is observed when either a or N is negative or both are negative. The answer of a mod N then depends on the implementation of a mod N used by the programming language. The remainder produced by all the programming languages does follow a certain criterion i.e., |r| < |N|. However, this still leaves a sign ambiguity if the remainder is non-zero, then two possible choices for the remainder occur, one negative (the greatest negative element of the congruence class of a mod N) and the other positive (the least positive element of the congruence class of a mod N). Other elements do not satisfy the criteria of |r| < |N|. That is why there are different results when -3 mod 2 performed in C and Python. Both of them are producing the correct results. They are just not outputting the mathematically chosen representative of a mod N. In C, -3 mod 2 returns -1, which is a member class of -3 mod 2. However, Python returns 1, which is again a member class of -3 mod 2. Also, both the answer returned to satisfy the given condition of |r| < |N|. Implementations of % in Programming languages: Many programming languages like C, C++, Java, JavaScript use an implementation similar to the one given below. The remainder is returned according to the equation r = a – N*trunc(a/N) Below is the implementation of the above explanation: C++14 #include using namespace std; int truncMod(int a, int n) {                     int q = a / n;     return a - n * q; } int main() {     int a, b;          a = 9;     b = 4;     cout