DivMod, QuotRem или что-то другое?27.01.2025 15:30

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

Несмотря на кажущуюся простоту и огромное количество написанных статей на эту тему, всё равно возникает огромная путаница. В разных языках операции определены и называются по-разному, а также дают разный результат (особенно сильно это сказывается когда в аргументах отрицательные значения).

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

Статья не претендует на срыв покровов, а скорее стремится быть удобной шпаргалкой. Листингов кода и точных названий операций конкретно в вашем языке программирования не будет, вместо этого красивые формулы.

Определения

Деление

Операция деления — нетривиальная операция.

Все знают, что делить на ноль нельзя (без предела), деление не терпит перестановки операндов (некоммутативно).

Однако если рассматривать целочисленное деление, всплывает еще один нюанс, так как появляется остаток от деления.

Для начала стоит рассмотреть деление $[\;/\;]$ в котором в общем случае при делении одного числа на другое мы получаем вещественное, в особых случаях может быть и целое, но это только при условии, что делимое делится на делитель нацело, то есть без остатка.

Обозначим это как

$a \;/\; b = c$

где — делимое, — делитель, — частное.

В то же время, в общем случае, для целочисленного деления должны выполняться такие условия:

$a = b \times q + r$

где

$q = a \div b, \;\; q ∈ \mathbb {Z} \\r = a \;\%\; b, \;\; |r| < |b|$

— делимое,
— делитель, причем $b \ne 0$ ,
— неполное частное,
— остаток от деления,
а также операции:
$[\div]$ — целочисленное деление,
$[\%]$ — взятие остатка.

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

$(a \div b) \times b + (a \;\%\; b) = a$

Однако для математического (Евклидова) деления с остатком вводится дополнительное ограничение для единственности решения:

$0 \leq r < |b|$

Которое говорит нам, что остаток от деления должен быть всегда положительным и не превосходящим делитель. Соблюдение этого условия в программировании встречается достаточно редко, а потому и появляется путаница.

Округление

Чтобы нам получить из частного — неполное частное, другими словами округлить, необходимы эти самые операции округления. Давайте их введем.

Округление вниз $\lfloor x \rfloor$
Когда число округляется в сторону отрицательной бесконечности.
Определение:

$y=\operatorname {floor} (x)=\left\lfloor x\right\rfloor =-\left\lceil -x\right\rceil$

Примеры:

$\displaylines{\lfloor +23.8 \rfloor = +23 \\\lfloor +23.2 \rfloor = +23 \\\lfloor -23.8 \rfloor = -24 \\\lfloor -23.2 \rfloor = -24 \\}$

Округление вверх $\lceil x \rceil$
Когда число округляется в сторону положительной бесконечности.

Определение:

$y=\operatorname{ceil} (x)=\left\lceil x\right\rceil =-\left\lfloor -x\right\rfloor$

Примеры:

$\displaylines{\lfloor +23.8 \rfloor = +24 \\\lfloor +23.2 \rfloor = +24 \\\lfloor -23.8 \rfloor = -23 \\\lfloor -23.2 \rfloor = -23 \\}$

Округление к нулю $\lceil x \rfloor$
Когда число округляется в сторону нуля. Или, другими словами, отрицательные числа округляются вверх, а положительные вниз.
Также эту операцию можно назвать отсечением дробной части.

Определение:

$y=\lceil x \rfloor =\operatorname {truncate} (x)=\operatorname {sign}(x)\left\lfloor \left|x\right|\right\rfloor =-\operatorname {sgn}(x)\left\lceil -\left|x\right|\right\rceil=\begin{cases} \left\lfloor x \right\rfloor &x\geq 0\\[5mu]\left\lceil x\right\rceil &x<0 \end{cases}$

Примеры:

$\displaylines{\lfloor +23.8 \rfloor = +23 \\\lfloor +23.2 \rfloor = +23 \\\lfloor -23.8 \rfloor = -23 \\\lfloor -23.2 \rfloor = -23 \\}$

Округление от нуля $\lfloor x \rceil$
Когда число округляется в сторону бесконечности от нуля. Или, другими словами, отрицательные числа округляются вниз, а положительные вверх.

Определение:

$y=\lfloor x \rceil =\operatorname {sign}(x)\left\lceil \left|x\right|\right\rceil =-\operatorname {sgn}(x)\left\lfloor -\left|x\right|\right\rfloor =\begin{cases}\left\lceil x\right\rceil &x\geq 0\\[5mu]\left\lfloor x\right\rfloor &x<0\end{cases}$

Примеры:

$\displaylines{\lfloor +23.8 \rfloor = +24 \\\lfloor +23.2 \rfloor = +24 \\\lfloor -23.8 \rfloor = -24 \\\lfloor -23.2 \rfloor = -24 \\}$

И ко всему прочему, для математического (Евклидова) деления с остатком тоже необходимо ввести операцию округления.

Евклидово округление $\langle x \rangle$
Когда число округляется в зависимости от знака делителя.
Определение:

$q=\operatorname {sign}(b)\left\lfloor {\frac {a}{\left|b\right|}}\right\rfloor =\begin{cases}\left\lfloor {\frac {a}{b}}\right\rfloor &{\text{if }}b>0\\\left\lceil {\frac {a}{b}}\right\rceil &{\text{if }}b<0\\\end{cases}$

Примеры:

$\displaylines{\langle +53 \; / +5 \rangle = +10 \\\langle +53 \; / -5 \rangle = -10 \\\langle -53 \; / +5 \rangle = -11 \\\langle -53 \; / -5 \rangle = +11 \\}$

Взятие остатка

Если говорить грубо, то в данном контексте операция взятия остатка не самостоятельная операция и зависит от метода округления.

И чтобы найти остаток, необходимо из уравнения

$a=b \times q + r = b \times (a \div b) + r$

вывести ,
тогда получаем

$r = a - q \times b = a - (a \div b) \times b$

Свойства

Теперь, когда всё готово, можно быстро сделать таблицы свойств и понять, по каким правилам происходит округление в вашем языке программирования.

Для вычисления неполного частного будем использовать:

$q = round\_type(a / b)$

и для вычисления остатка от деления:

$r = a - round\_type(a / b) \times b$

Для деления методом Евклида:

$q = sign(b) \times round\_dn(a / abs(b))$

и

$r = a - round\_dn(a / abs(b)) \times abs(b)$

соответственно.

Далее для примера продолжу использовать числа = 53, = 5, что при делении дает = 10,6.

Для неполного частного получаем следующую таблицу:

a	b	с	div_euclid	div_zero	div_inf	div_dn	div_up	Sign
+53	+5	+10,6	+10	+10	+11	+10	+11	+
+53	-5	-10,6	-10	-10	-11	-11	-10	-
-53	+5	-10,6	-11	-10	-11	-11	-10	-
-53	-5	+10,6	+11	+10	+11	+10	+11	+

Как видим, знак у неполного частного во всех случаях совпадает.

Для остатка от деления получаем следующую таблицу:

a	b	с	mod_euclid	mod_zero	mod_inf	mod_dn	mod_up
+53	+5	+10,6	+3	+3	-2	+3	-2
+53	-5	-10,6	+3	+3	-2	-2	+3
-53	+5	-10,6	+2	-3	+2	+2	-3
-53	-5	+10,6	+2	-3	+2	-3	+2

Как видим, знак у остатка от деления не во всех случаях совпадает.

Сведем все в единую таблицу

	Sa	Sb	Sq	Sr	Rules
euclid	++--	±+-	±-+	++++	sign^® = +1
zero	++--	±+-	±-+	++--	sign^® = sign (a)
inf	++--	±+-	±-+	--++	sign^® = sign (-a)
dn	++--	±+-	±-+	±+-	sign^® = sign (b)
up	++--	±+-	±-+	-±+	sign^® = sign (-b)

Отдельно стоит заметить, что для zero и inf выполняются такое условие

$(−a) \div b = −(a \div b)=a \div (−b)=-((-a) \div (-b))$

Заключение

Как видим, существует достаточное разнообразие для определения операции целочисленного деления, что и вынесено в заголовок статьи. При этом достаточно мало языков определяют две популярные DivMod и QuotRem операции, однако каким операциям по типу округления они соответствуют, я говорит не берусь.

А есть ли те, кто определяет больше? Скорее всего математические пакеты точно должны поддерживать div_mod_euclid.

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