Java - Is there a method for Euclidean or floored modulo

Question

Java modulo operator % is based on the truncated division (see Wikipedia: Modulo operation).

• 5%3 produces 2 (note that 5/3 produces 1)
• 5%(-3) produces 2 (note that 5/(-3) produces -1)
• (-5)%3 produces -2 (note that (-5)/3 produces -1)
• (-5)%(-3) produces -2 (note that (-5)/(-3) produces 1)

In computing science, given two integers a and n, n > 0, sometimes it is useful to get the unique integer r within [a,n[ which is congruent to a modulo n.

Question

Is there an efficient generic operator / method in Java which respects this specification of modulo?

This is to avoid rewriting it in every project where it is needed...

Miscellaneous

I found a lot of questions on stackoverflow about this problem, most of them confusing the different modulo implementations. If you are just troubled about the results of the modulo operation on negative numbers, below are some implementations based on the Java % operator that may be useful.

Common hack

Since we hardly use a negative divisor, this implementation returns the Euclidean or floored modulo when n > 0.

static int mod(int a, int n){    
  return a<0 ? (a%n + n)%n : a%n;
}

• mod( 5, 3) produces 2
• mod(-5, 3) produces 1

Euclidean modulo

static int euclideanModulo(int a, int n){
  return n<0 ? euclideanModulo(a, -n) : mod(a, n);
}

• euclideanModulo( 5, 3) produces 2
• euclideanModulo(-5, 3) produces 1
• euclideanModulo( 5,-3) produces 2
• euclideanModulo(-5,-3) produces 1

Floored modulo

static int flooredModulo(int a, int n){
  return n<0 ? -flooredModulo(-a, -n) : mod(a, n);
}

• flooredModulo( 5, 3) produces 2
• flooredModulo(-5, 3) produces 1
• flooredModulo( 5,-3) produces -1
• flooredModulo(-5,-3) produces -2

Answer 1

+----+----+-----------+---------+-----------+-----------+---------+-----------+
| x mod y |           quotient 'q'          |          remainder 'r'          |
| x  | y  | truncated | floored | Euclidean | truncated | floored | Euclidean |
+----+----+-----------+---------+-----------+-----------+---------+-----------+
|  5 |  3 |         1 |       1 |         1 |         2 |       2 |         2 |
| -5 |  3 |        -1 |      -2 |        -2 |        -2 |       1 |         1 |
|  5 | -3 |        -1 |      -2 |        -1 |         2 |      -1 |         2 |
| -5 | -3 |         1 |       1 |         2 |        -2 |      -2 |         1 |
+----+----+-----------+---------+-----------+-----------+---------+-----------+

Any of them satisfies at least x = yq + r.

Truncated division and modulo

static int truncatedDiv(int x, int y) {    
    return x / y;
}

static int truncatedMod(int x, int y) {    
    return x % y;
}

Floored division and modulo

You can use methods in java.lang.Math since Java 8. See floorDiv and floorMod.

static int floorDiv(int x, int y) {    
    return Math.floorDiv(x, y);
}

static int floorMod(int x, int y) {    
    return Math.floorMod(x, y);
}

Euclidean division and modulo

a) based on truncated division

import static java.lang.Math.*;

static int euclideanDiv(int x, int y) {
    int r = x / y;
    // if the divident is negative and modulo not zero, round down for positive divisor, otherwise round up
    if (x < 0 && r * y != x) {
        r -= signum(y);
    }
    return r;
}

static int euclideanMod(int x, int y) {
    int r = x - euclideanDiv(x, y) * y;
    return r;
}

b) based on floored division

import static java.lang.Math.*;

static int euclideanDiv(int x, int y) {
    int r = floorDiv(x, y);
    // if the divisor is negative and modulo not zero, round up
    if (y < 0 && r * y != x) {
        r++;
    }
    return r;
}

static int euclideanMod(int x, int y) {
    int r = x - euclideanDiv(x, y) * y;
    return r;
}

c) based on absolute modulo

import static java.lang.Math.*;

static int euclideanMod(int x, int y) {
    int r = abs(x) % abs(y);
    // apply the sign of divident and make sure the remainder is positive number
    r *= signum(x);
    r = (r + abs(y)) % abs(y);
    return r;
}

Answer 2

how about this code

public static int gcd(int p, int q) {
    if(count == 0) 
        System.out.print("Gcd for " + p + " and " + q);
    if (q == 0) {
           System.out.println(" returns " + p + " after " + count + " iterations");
        return p;
    }
    count++;
    return gcd(q, p % q);
}
public static void main(String[] args) {
    count = 0;
    gcd(4, 16);
    count = 0;
    gcd(4, 16);
    count = 0;
    gcd(16, 4);
    count = 0;
    gcd(15, 60);
    count = 0;
    gcd(15, 65);
    count = 0;
    gcd(1052, 52);
}