Отрицательный остаток и модуль

Какой остаток от деления $7$ на $-3$? На самом деле, это может быть $1$ или $-2$, в зависимости от выбранного соглашения и/или используемого языка программирования.

Что? Отрицательные остатки? Давайте рассмотрим это подробно.

Деление в математике

В математике деление по сути связано с разделением количества на равные части.

Когда мы делим число $a$ на другое число $b$, мы спрашиваем: “Сколько $b$ помещается в $a$?”

Евклидово деление

Евклидово деление, также известное как целочисленное деление, это специфический тип деления, применяемый к целым числам.

Давайте посмотрим на формулу: $$ a=b*q+r $$

Здесь у нас есть:

• делимое ($a$): число, которое делят
  • например, в $7 / 3$ делимое равно $7$
• делитель ($b$): число, на которое делят
  • например, в $7 / 3$ делитель равен $3$

Евклидово деление дает нам два важных значения при делении целых чисел:

• целое частное ($q$): деление дает целочисленный результат (округление вниз)
  • например, $7 / 3$ имеет частное $2$
• целый остаток ($r$): оставшаяся часть после деления является целым числом
  • например, $7 - (3 * 2) = 1$

Более того, должно выполняться следующее условие: $$ b \neq 0 \\[1em] 0 \leq r < |b| \\[1em] 0 \leq остаток < |делитель| \quad \text{← то же, что и выше} $$

Обратите внимание:

• $b$ может быть отрицательным, но не может быть $0$
• $r$ - это положительное число меньше абсолютного значения $|b|$ (делителя) и может быть нулем.

Евклидово деление в чистой математике

Давайте посмотрим, как чистая математика будет обрабатывать все случаи:

• Положительное делимое, положительный делитель: $$ 7 \bmod 3 = 1 \\ 7 = 3 * 2 + 1 $$

• Положительное делимое, отрицательный делитель: $$ 7 \bmod (-3) = 1 \\ 7 = (-3) * (-2) + 1 $$

• Отрицательное делимое, положительный делитель. Обратите внимание, что мы находим частное ($-3$), так что результат ($-9$) меньше делимого ($-7$): $$ -7 \bmod 3 = 2 \\ -7 = 3 * (-3) + 2 $$

• Отрицательное делимое, отрицательный делитель. Обратите внимание, что мы находим частное ($3$), так что результат ($-9$) меньше делимого ($-7$): $$ (-7) \bmod (-3) = 2 \\ -7 = (-3) * 3 + 2 $$

Как видите, мы округляем вниз результат $частное * делитель$ даже для отрицательных чисел, поэтому остаток в математике положительный (в большинстве соглашений).

Взятие остатка vs Сравнение по модулю

Остаток можно вычислить с помощью операции mod: $$ r = a \bmod b $$

Важно не путать операцию mod и сравнение по модулю.

Сравнение по модулю обозначается как: $$ a \equiv b \pmod{m} $$

и по сути означает, что: $$ a \bmod m = b \bmod m $$

Другими словами: $a$ и $b$ дают одинаковый остаток при делении на $m$.

Остатки в программировании

Как мы видели ранее, в математике остаток является положительным числом (опять же, в большинстве соглашений).

Однако операция вычисления остатка в языках программирования может возвращать отрицательный результат (для отрицательного делимого или делителя).

Здесь есть два варианта:

• Знак остатка совпадает со знаком делимого
  • Неполное частное округляется к $0$.
• Знак остатка совпадает со знаком делителя
  • Неполное частное округляется к $-\infty$.

Давайте разберем каждый случай ниже.

Знак остатка = знак делимого

Неполное частное округляется в направлении $0$.

Рассмотрим случаи:

• Положительное делимое, положительный делитель: $$ 7 \bmod 3 = 1 \\[1em] 7 / 3 = 2.333(3) \approx 2 \quad \text{округление к $0$} \\[1em] 7 = 3 * 2 + 1 $$

• Положительное делимое, отрицательный делитель: $$ 7 \bmod (-3) = 1 \\[1em] 7 / (-3) = -2.333(3) \approx -2 \quad \text{округление к $0$} \\[1em] 7 = (-3) * (-2) + 1 $$

• Отрицательное делимое, положительный делитель. Видно, что частное здесь $-2$, а не $-3$, как в обычной математике: $$ (-7) \bmod 3 = -1 \\[1em] (-7) / 3 = -2.333(3) \approx -2 \quad \text{округление к $0$} \\[1em] -7 = 3 * (-2) + (-1) $$

• Отрицательное делимое, отрицательный делитель. Видно, что частное здесь $2$, а не $3$, как в обычной математике: $$ (-7) \bmod (-3) = -1 \\[1em] (-7) / (-3) = 2.333(3) \approx 2 \quad \text{округление к $0$} \\[1em] -7 = (-3) * 2 + (-1) $$

Знак остатка = знак делителя

Неполное частное округляется в направлении $−\infty$.

Рассмотрим случаи:

• Положительное делимое, положительный делитель: $$ 7 \bmod 3 = 1 \\[1em] 7 / 3 = 2.333(3) \approx 2 \quad \text{округление к $−\infty$} \\[1em] 7 = 3 * 2 + 1 $$

• Положительное делимое, отрицательный делитель. Видно, что частное здесь $-3$, а не $-2$, как в обычной математике: $$ 7 \bmod -3 = -2 \\[1em] 7 / (-3) = -2.333(3) \approx -3 \quad \text{округление к $−\infty$} \\[1em] 7 = (-3) * (-3) + (-2) $$

• Отрицательное делимое, положительный делитель: $$ -7 \bmod 3 = 2 \\[1em] -7 / 3 = -2.333(3) \approx -3 \quad \text{округление к $−\infty$} \\[1em] -7 = 3 * (-3) + 2 $$

• Отрицательное делимое, отрицательный делитель. Видно, что частное здесь $2$, а не $3$, как в обычной математике: $$ (-7) \bmod (-3) = -1 \\[1em] (-7 / (-3) = 2.333(3) \approx 2 \quad \text{округление к $−\infty$} \\[1em] -7 = (-3) * 2 + (-1) $$

‼️ Как видите, оба случая в информатике (совпадение знака с делимым и совпадение знака с делителем) отличаются от принципов чистой математики.

Детали реализации

Важно отметить, что поведение операции остатка может различаться в зависимости от языка программирования.

Некоторые языки округляют к нулю, в то время как другие округляют к минус бесконечности.

Существует два типа деления:

• Усеченное деление: $3.75$ равно $3$, а $-3.75$ равно $-3$.
• Деление с округлением вниз: $3.75$ равно $3$, но $-3.75$ равно $-4$ (округление вниз, Math.floor())

Реализация в Java

В Java операция mod (%) следует правилу, где остаток принимает знак делимого (первого операнда).

Операция mod в Java определяется формулой:

a % b = a - (a / b) * b

где / - это целочисленное (усеченное) деление, которое округляет к нулю.

Реализация в Python

В Python оператор mod (%) следует правилу, где остаток принимает знак делителя (второго операнда).

Операция mod в Python определяется формулой:

a % b = a - (a // b) * b

где // - это деление с округлением вниз, которое округляет к минус бесконечности.

Практические применения

Кто-то может спросить – подождите, зачем нам нужны разные способы вычисления остатков?

Что ж, каждый из способов имеет свои практические применения.

Знак остатка = знак делимого

Есть число n центов, положительное или отрицательное. Нужно конвертировать его в доллары и центы. Это будет:

dollars = n div 100
cents = n mod 100

Знак остатка совпадает со знаком делимого.

Знак остатка = знак делителя

Есть бесконечная сетка ячеек, каждая ячейка 16×16 пикселей. В какую ячейку попадает точка (x, y) и каковы ее координаты относительно верхнего левого угла ячейки? Ответ:

x div 16, y div 16
// и
(x mod 16, y mod 16)

Знак остатка совпадает со знаком делителя.

Поведение mod в разных языках

Поскольку каждый язык имеет оба типа деления, мы можем запрограммировать каждое поведение mod в каждом языке.

Python:

python_mod = a - (a // b) * b  # деление с округлением вниз
java_mod = a - int(a / b) * b  # усеченное деление

Java:

// деление с округлением вниз
int pythonMod = (int) (a - Math.floor((double) a / (double) b) * b);

// усеченное деление
int javaMod = a - (a / b) * b;

Реализация положительного остатка

Но что если в программировании нам нужно, чтобы остаток всегда был положительным?

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

Существует распространенный метод, делающий так, что результат операции взятия остатка всегда находится в неотрицательном диапазоне [0, a-1], независимо от того, как операция взятия остатка реализована в конкретном языке: $$ (a \bmod b + b) \bmod b $$

Разберемся:

1. a mod b: вычисляет начальный остаток. Это может быть как отрицательным числом (например, $-1 \bmod 5$ может вернуть $-1$ в некоторых контекстах), так и положительным
2. + b: сдвигает отрицательные результаты в положительный диапазон. Например, $-1 + 5 = 4$
3. mod b: даже если остаток изначально был положительной, это гарантирует, что конечный результат все еще находится в пределах [0, a-1].

Давайте рассмотрим подробнее:

1. a mod b:

• В Java -1 mod 5 = -1.
• В Python -1 mod 5 напрямую возвращает $4$.

2. + b:

• Если первый результат был $-1$: $-1 + 5 = 4$ (теперь положительное значение).
• Если первый результат уже был $4$: $4 + 5 = 9$ (временно превышает диапазон модуля).

3. mod b:

• Если у вас было $4$ с первого шага: 4 mod 5 = 4 (без изменений).
• Если у вас было $9$ с первого шага: 9 mod 5 = 4 (возвращает обратно в диапазон [0, 4]).