Модульное разделение Java

Я исправляю некоторые ошибки, и мне нужно разделить две цифры по модулю 11 в Java.

Теперь это я знаю, используя модульный калькулятор:

9/1 mod 11 = 9
2/10 mod 11 = 9

Проблема заключается в том, чтобы заставить Java вычислить это. В Java:

(9 / 1) % 11 = 9 - This is fine
(2 / 10) % 11 = 0 - This is not correct.

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


java division modular-arithmetic
person Tony    schedule 22.10.2011    source источник
comment
Err, 2/10 равно 0. А 0 % 11 равно 0. Почему должно быть 9?   -  person JB Nizet    schedule 22.10.2011
comment
Потому что делаю под мод 11. Не нормальное деление.   -  person Tony    schedule 22.10.2011
comment
Я только что сделал следующее: (2 * 10) % 11 = 9. Кажется, это дает мне правильный ответ.   -  person Tony    schedule 22.10.2011
comment
Ах, конечно. Но умножение и деление не совсем одно и то же. Вы нашли правильную проблему для вашего решения.   -  person JB Nizet    schedule 22.10.2011
comment
Так в чем вопрос? Вы узнали, что вам нужно было использовать умножение вместо деления... Нет вопросов. Я проголосовал за закрытие.   -  person stivlo    schedule 22.10.2011
comment
@stivlo: вопрос об инвертировании умножения в модульной арифметике. Поскольку 10 является обратным по модулю 11, умножение на 10 и деление на 10 дает тот же эффект в арифметике по модулю 11. Вот почему Тони получает правильный ответ несколькими комментариями выше.   -  person Luke Woodward    schedule 22.10.2011
comment
@LukeWoodward спасибо, я понял, тогда нужно определить свой собственный класс с его оператором равенства, его делением, умножением и так далее.   -  person stivlo    schedule 23.10.2011

Ответы (2)


arrow_upward
5
arrow_downward

Я думаю, что вы ищете, как найти мультипликативную инверсию числа по модулю 11.

10 является обратным по модулю 11, так что это не особенно полезный пример. Вместо этого давайте найдем мультипликативную обратную 7 по модулю 11.

Для этого решим уравнение 7a + 11b = 1 для a и b в целых числах. Мы используем алгоритм Евклида, чтобы найти подходящие значения для a и b. В этом случае мы можем взять a = -3 и b = 2. Мы игнорируем значение b и принимаем a ( = -3) как обратное 7 по модулю 11. В арифметике по модулю 11 7 умножить на -3 1.

Если нам не нравятся отрицательные числа, мы можем вместо этого взять обратное 7 по модулю 11 равное 8 (= -3 + 11).

Итак, вместо деления на 7 по модулю 11 мы умножаем на -3 или на 8. Например, в арифметике по модулю 11 9/7 = 9 * 8 = 72 = 6.

Если у вас есть только один модуль для работы (например, вы когда-либо работали только по модулю 11), вероятно, лучше заранее рассчитать таблицу мультипликативных инверсий по модулю 11 и использовать ее в своих расчетах.

person Luke Woodward    schedule 22.10.2011
comment
Спасибо за это, Люк, у меня было подозрение, что мне придется это сделать. Есть ли у вас какие-либо советы по созданию такой таблицы? Я предполагаю, что мне нужен многомерный массив? - person Tony; 23.10.2011
comment
Я не понимаю, зачем вам нужен многомерный массив. Если вы когда-либо работали только по модулю 11, вычислите обратные числа от 1 до 10 по модулю 11 и поместите их в одномерный массив. Если вы работаете с большим количеством модулей или любыми большими модулями, таблица не будет такой хорошей идеей. - person Luke Woodward; 23.10.2011
comment
Спасибо, Люк, я немного запутался в том, что я пытался сделать (для меня еще довольно рано) :). Теперь я построил обратную таблицу, используя массив, и теперь все работает по плану. Спасибо за вашу помощь!! - person Tony; 23.10.2011
comment
Люк, ты мне очень помог, и я подумал, могу ли я попросить тебя о помощи в последний раз. Просто мне нужен способ на Java, чтобы он выводил 7, когда я ввожу y = -4% 11. Есть предложения? - person Tony; 24.10.2011
comment
@Tony: одно из возможных выражений, которое обрабатывает как положительные, так и отрицательные числа, - это ((y % 11) + 11) % 11. - person Luke Woodward; 25.10.2011

arrow_upward
1
arrow_downward

Не уверен, что это то, что вы имеете в виду, но...

public static int divmod(int dividend, int divisor, int mod) {
    if (dividend >= divisor)
        return (dividend / divisor) % mod;
    return mod - dividend;
}

Тестирование:

divmod(9, 1, 11)  // returns 9
divmod(2, 10, 11) // returns 9
person Óscar López    schedule 22.10.2011
comment
Спасибо, Оскар, это работает для одних пар чисел, но не для других. - person Tony; 23.10.2011
comment
Дайте мне набор чисел для тестирования, особенно те, которые не соответствуют действительности, и я посмотрю, чем могу вам помочь. - person Óscar López; 23.10.2011