navigation

Modulo problem in Java

Modulo problem in Java

by
July 27, 2016
frontpage, Java
4 Comments

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:

cyclic array(deque) in java

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:

Python 3.5.2
>>> (1 - 0) % 4
1
>>> (1 - 1) % 4
0
>>> (1 - 2) % 4
3
>>> (1 - 3) % 4
2

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:

for(int i = 0; i < 4; i++){
    System.out.println((1 - i) % 4);
}

And the result was:

1
0
-1
-2

 

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:


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);
    }
}

Do you know about other disparities in the implementation of operators?

Do you want more great blogs like this?

Subscribe for Dreamix Blog now!

  • sid

    Well, I’d say the Python behaviour is in fact the expected one, considering that the Zen of Python dictates to use the most straightforward and generic solution where possible, without defining special cases which break the rules. In this case, the most intuitive generalization of the remainder operation is the congruence relation (which you referred to as the “modulo operation”) because it is applicable to negative numbers (and could even be extended to handle reals). In addition, it returns a result that is actually meaningful and useful in this special case (which is proven by your example).
    However, the inconsistent behaviour here is the Java one. While Java tries to be explicit in most cases, throwing exceptions where many other languages would go ahead silently, the remainder operation does something pretty much counter-intuitive when used with negatives: it finds the remainder of the division of the absolute values of the operands and then applies the sign of the first operand to the resultant value. This is not only completely at odds with the language’s ideology (how could anyone think of such a workaround in the beginning?) but also completely useless (how would anyone use such a result anyway?). To be honest, the most sensible thing the language could do here (besides applying the congruence relation) would be to throw an exception: at least the user won’t lose their time contemplating how he got that result.
    As for your question about inconsistencies in implementations of operators: from my experience with large C++ codebases, especially with libraries and frameworks that provide generic data structures (like Boost or wxWidgets, for example), I can say that every one of them overloads operators in their own unique way, giving them a different meaning depending on the specific case. So Java is at least more consistent when talking about operators as it does not permit overloading them at all :-)

    • dimitarchaushev

      Great reply! It is a perfect addition to the blog. Thanks! :)

  • OoOo

    FYI :

    private static int mod(int n, int m) {
    if(n > 0) { return n % m; } else { return m + n%m; )
    }

    Is faster as division is a costly operation for a CPU (more than a jump).

    If this implementation is done like this, it’s mostly because remainder is more “low level” than “real” modulo, which is all case will relay on remainder operation.

    Finally, if division and remainder interest you, give a look at http://libdivide.com/, which is a non-div implementation of divisions

    • StoyanMit

      Thanks for this comment:)