How I encountered the modulo problem in Java?
While working on a project, I needed to implement a cyclic array(deque) in java. This is an array with fixed size, where you append elements, and when you fill the whole array, you start over overwriting the elements from the beginning:
The Example:
I wanted to have constant access to the previous 3 elements, so the deque seemed perfect for the job. Having the index of the current element i and number of elements n = 4, I was calculating the previous 3 elements to be:
(i – 1) % n
(i – 2) % n
(i – 3) % n
I am implementing this in Java, but I use the Python interpreter(Idle) to validate such mathematical expressions. It is just faster for me than checking it in Java.
So i checked the following, having i = 1:
[code language=”python”]
Python 3.5.2
>>> (1 – 0) % 4
1
>>> (1 – 1) % 4
0
>>> (1 – 2) % 4
3
>>> (1 – 3) % 4
2
[/code]
Okey, everything seems to be working fine, I implemented it in Java and was good to go.
While testing, sometimes the results were not as expected and sometimes I was getting IndexOutOfBoundException. Then I checked the same expressions in Java:
[code language=”java”]
for(int i = 0; i < 4; i++){
System.out.println((1 – i) % 4);
}
[/code]
And the result was:
[code language=”java”]
1
0
-1
-2
[/code]
It turned out that the implementation of the modulo operator is different in Python and languages like Java. In Java, the result has the sign of the dividend, but in Python, the sign is from the divisor.
Sometimes my dividends were negative, so the result, which is an array index, was negative and this is why I was getting IndexOutOtBoundsException. It turns out that both implementations are correct, but the Python’s one is more useful in practice. Python has a “true” modulo operation, while the Java has a remainder operation.
To achieve the Python’s result in Java, you can use:
(((n % m) + m) % m), where n is the dividend and m – the divisor.
You can find more information about the topic at this wiki page: https://en.wikipedia.org/wiki/Modulo_operation
Now here’s my implementation of the Deque in Java:
[code language=”java”]
public class Deque {
/**
* Appends new element and returns its index
*
* @param element integer
* @return index integer
*/
public static int append(int element, int[] elements, int index) {
System.out.println("Appending " + element);
index++;
if (index == elements.length) {
index = 0;
}
elements[index] = element;
return index;
}
private static int mod(int n, int m) {
return (((n % m) + m) % m);
}
/**
* Prints the elements in reverse order of their appending -> LIFO style
*/
private static void print(int[] elements, int index) {
for (int i = 0; i < elements.length; i++) {
System.out.print(elements[mod(index – i, elements.length)] + " ");
}
System.out.println("n———");
}
public static void main(String[] args) {
int N = 4;
int index = -1;
int[] elements = new int[N];
// Append 1, 2, 3, 4
for (int i = 1; i <= N; i++) {
index = append(i, elements, index);
}
// Prints 4, 3, 2, 1
print(elements, index);
// Append 4, 5, should overwrite 1 and 2
for (int i = 5; i <= 6; i++) {
index = append(i, elements, index);
}
// Prints 6, 5, 4, 3
print(elements, index);
}
}
[/code]
Do you know about other disparities in the implementation of operators?