Java - есть ли метод для евклидова или напольного модуля

Оператор по модулю Java % основан на усеченном делении (см. Википедия: операция по модулю).

  • 5%3 производит 2 (обратите внимание, что 5/3 производит 1)
  • 5%(-3) производит 2 (обратите внимание, что 5/(-3) производит -1)
  • (-5)%3 производит -2 (обратите внимание, что (-5)/3 производит -1)
  • (-5)%(-3) производит -2 (обратите внимание, что (-5)/(-3) производит 1)

В информатике, имея два целых числа a и n, n ›0, иногда полезно получить уникальное целое число r в пределах [a,n[, которое конгруэнтно a по модулю n.

Вопрос

Есть ли в Java эффективный универсальный оператор / метод, который соблюдает эту спецификацию по модулю?

Это сделано для того, чтобы не переписывать его в каждом проекте, где это необходимо ...

Разное

Я нашел много вопросов об этой проблеме по stackoverflow, большинство из которых сбивает с толку различные реализации по модулю. Если вас просто беспокоят результаты операции по модулю для отрицательных чисел, ниже приведены некоторые реализации, основанные на операторе Java %, которые могут быть полезны.

Общий взлом

Поскольку мы почти не используем отрицательный делитель, эта реализация возвращает евклидово значение по модулю, когда n > 0.

static int mod(int a, int n){    
  return a<0 ? (a%n + n)%n : a%n;
}
  • mod( 5, 3) производит 2
  • mod(-5, 3) производит 1

Евклидов по модулю

static int euclideanModulo(int a, int n){
  return n<0 ? euclideanModulo(a, -n) : mod(a, n);
}
  • euclideanModulo( 5, 3) производит 2
  • euclideanModulo(-5, 3) производит 1
  • euclideanModulo( 5,-3) производит 2
  • euclideanModulo(-5,-3) производит 1

Напольные по модулю

static int flooredModulo(int a, int n){
  return n<0 ? -flooredModulo(-a, -n) : mod(a, n);
}
  • flooredModulo( 5, 3) производит 2
  • flooredModulo(-5, 3) производит 1
  • flooredModulo( 5,-3) производит -1
  • flooredModulo(-5,-3) производит -2

java operators modulo negative-number modulus
person boumbh    schedule 08.02.2013    source источник
comment
Вы, наверное, уже проверяли это, но вы можете довольно легко использовать минимальные значения (ближайшее целое число вниз) с помощью Math.floor() (JavaDocs)   -  person Killrawr    schedule 08.02.2013
comment
@Killrawr Math.floor() хуже любого из вышеперечисленных решений.   -  person UmNyobe    schedule 08.02.2013
comment
@Killrawr a - n * (int)Math.floor((double)a/n); математически верен для напольного модуля, но не эффективен и не универсален.   -  person boumbh    schedule 08.02.2013
comment
@boumbh, какое поведение вы хотите? Что должен (-5)magicmod(-3) дать? -2 или 2?   -  person UmNyobe    schedule 08.02.2013
comment
Ха-ха, я не экспериментировал ни с одним из решений вопроса (чтобы найти улучшения). Но все равно спасибо за разъяснения UmNyobe (+1 респ). Обычно большинство функций, которые я нашел в библиотеке Math, хороши, хотя вроде cos / sin / tan / pow / sqrt / log / exp. Но я действительно ничего не кодировал с функцией пола / потолка (извините, я ничем не помог).   -  person Killrawr    schedule 08.02.2013
comment
@UmNyobe Даны два целых числа a и n, n > 0, вернуть уникальное целое число r в пределах [a,n[, которое конгруэнтно a по модулю n. У меня уже есть эффективная реализация, я просто хотел убедиться, что не изобретаю велосипед. Я был бы удивлен, что в Java нет более универсального способа сделать это. Может, я просто секу волосы. Если так, то ответ будет простым нет.   -  person boumbh    schedule 08.02.2013
comment
какой ты используешь сейчас? первое?   -  person UmNyobe    schedule 08.02.2013
comment
Да, велосипедные массивы array[mod(i++, array.length)]. Это не насущная проблема, скорее любопытный вопрос для моего личного совершенствования.   -  person boumbh    schedule 08.02.2013
comment
Если euclideanModulo(5, -3) дает 1, это неверно, потому что частное не является целым числом: a = bq + r, 5 = -3q + 1, q = -4/3. Та же проблема с euclideanModulo(-5,-3), который, по вашему мнению, выдает 2.   -  person Vlastimil Ovčáčík    schedule 28.03.2015
comment
Я плохо, 5 % -3 должно быть 2 и -5 % -3 должно быть 1, я внесу изменения в вопрос и другой свой комментарий.   -  person boumbh    schedule 30.03.2015

Ответы (2)


arrow_upward
10
arrow_downward 

+----+----+-----------+---------+-----------+-----------+---------+-----------+
| 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 |
+----+----+-----------+---------+-----------+-----------+---------+-----------+

Любой из них удовлетворяет как минимум x = yq + r.

Усеченное деление и по модулю

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

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

Напольное деление и по модулю

Вы можете использовать методы в java.lang.Math, начиная с Java 8. См. floorDiv и 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);
}

Евклидово деление и по модулю

а) по усеченному делению

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

б) по этажному разделению

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

в) по абсолютному модулю

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;
}
person Vlastimil Ovčáčík    schedule 28.03.2015
comment
Привет, Властимил, спасибо за хорошие новости о Java 8. У меня проблемы с вашей реализацией. Когда я попробовал версию a) и версию b), euclideanMod(-4, -2) вернул 2 вместо 0, а для версии c) euclideanModA(5, -3) вернул 2 вместо 1. Может, я сделал что-то не так, не могли бы вы подтвердить? - person boumbh; 30.03.2015
comment
Я прочитал ваш комментарий, я ошибаюсь, и мне нужно время, чтобы все исправить. Тем не менее, у вас может быть ошибка в реализации а) и б)? - person boumbh; 30.03.2015
comment
Нет, ты прав. По правде говоря, я отправил ответ как черновик - я не ожидал, что кто-то его протестирует до следующих выходных. Мне не нужна была альтернатива IFs вашему решению - я сказал, что подумываю об удалении a) и b) полностью. - person Vlastimil Ovčáčík; 30.03.2015
comment
@boumbh, я отказался от идеи отсутствия IF и просто вдохновился исходным кодом Java 8. Я бы выбрал евклидов по модулю, основанный на усеченном делении, поскольку это деление по умолчанию в Java. Однако алгоритм абсолютного по модулю запомнить намного проще. - person Vlastimil Ovčáčík; 31.03.2015
comment
Привет, Властимил, наконец-то проверил. Я удивлен, что усеченная версия работает так быстро. Я бы подумал, что что-то вроде int r = x % y; return r >= 0?r:r + Math.abs(y); будет быстрее, потому что есть только одно деление и нет умножения ... Ваша усеченная версия - самая быстрая, которую я нашел на данный момент. - person boumbh; 07.04.2015
comment
Для абсолютной версии есть некоторые проблемы. r *= signum(x); плохо ведет себя с большими целыми числами, я заменил его на if (a < 0) r = -r;. Затем у нас есть r = (r + abs(y)) % abs(y);, который может взорваться (когда r + y больше Integer.MAX_VALUE. Необходимо проверить r отрицательный результат: if (r < 0) r = (r + Math.abs(b)) % Math.abs(b);, чтобы получить лучший диапазон. Ваш ответ принят! ^^ - person boumbh; 07.04.2015

arrow_upward
-1
arrow_downward

как насчет этого кода

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);
}
person TheWhiteRabbit    schedule 08.02.2013