Деление с остатком

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

• Знак остатка совпадает со знаком делимого: неполное частное округляет к нулю.
• Знак остатка совпадает со знаком делителя: неполное частное округляет к ${\displaystyle -\infty }$.

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

• Есть сумма ${\displaystyle n}$ копеек, положительная или отрицательная. Перевести её в рубли и копейки: n div 100 и n mod 100. Знак остатка совпадает со знаком делимого.
• Есть бесконечное клеточное поле, каждая клетка 16×16 пикселей. В какую клетку попадает точка (${\displaystyle x}$, ${\displaystyle y}$), и каковы координаты относительно верхнего левого угла клетки? Ответ: x div 16, y div 16 и (x mod 16, y mod 16) соответственно. Знак остатка совпадает со знаком делителя.

Неполное частное можно вычислить через деление и взятие целой части: ${\displaystyle q=\left[{\frac {a}{b}}\right]}$, где ${\displaystyle [x]}$, в зависимости от задачи, может быть «полом» или усечением. Однако деление здесь получается дробное, которое намного медленнее целого. Такой алгоритм используется в языках, в которых нет целых типов (отдельные электронные таблицы, программируемые калькуляторы и математические программы), а также в скриптовых языках, в которых издержки интерпретации намного превышают издержки дробной арифметики (Perl, PHP).

При отсутствии команды mod остаток программируется как ${\displaystyle a-qb}$.

Если ${\displaystyle b}$ положительно, а знак ${\displaystyle r}$ совпадает со знаком делимого, не определён или неизвестен, для нахождения минимального неотрицательного остатка можно воспользоваться формулой ${\displaystyle r'=(b+(a\operatorname {mod} b))\operatorname {mod} b}$.

Неполное частное и неотрицательный остаток от деления на степень двойки ${\displaystyle 2^{n}}$ — это битовый сдвиг ${\displaystyle a\gg n}$ (для чисел со знаком — арифметический) и ${\displaystyle a\mathop {\&} (2^{n}-1)}$.

Если два числа ${\displaystyle a}$ и ${\displaystyle b}$ (отличное от нуля) относятся к множеству вещественных чисел, ${\displaystyle a}$ может быть поделено на ${\displaystyle b}$ без остатка, и при этом частное также является вещественным числом. Если же частное по условию должно быть целым числом, в этом случае остаток будет вещественным числом, то есть может оказаться дробным.

Формально:

если ${\displaystyle a,b\in \mathbb {R} ,b\neq 0}$, то ${\displaystyle a=bq+r}$, где ${\displaystyle 0\leqslant r<|b|}$.

Пример

Деление 7,9 на 2,1 с остатком даёт:

${\displaystyle \left\lfloor {\frac {7{,}9}{2{,}1}}\right\rfloor =3}$ (неполное частное);

${\displaystyle 7{,}9-3\cdot 2{,}1=1{,}6}$ (остаток).

Гауссово число — это комплексное число вида ${\displaystyle a+bi}$, где ${\displaystyle a,b}$ — целые числа. Для них можно определить деление с остатком: любое гауссово число ${\displaystyle u}$ можно разделить с остатком на любое ненулевое гауссово число ${\displaystyle v}$, то есть представить в виде:

${\displaystyle u=vq+r}$,

где частное ${\displaystyle q}$ и остаток ${\displaystyle r}$ — гауссовы числа, причём ${\displaystyle |r|<|v|.}$ Однако, в отличие от целых чисел, остаток от деления определяется неоднозначно. Например, ${\displaystyle 7+2i}$ можно разделить на ${\displaystyle 3-i}$ тремя способами:

${\displaystyle 7+2i=(3-i)(2+i)+i=(3-i)(1+i)+3=(3-i)(2+2i)+(-1-2i).}$

При делении с остатком двух многочленов ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$ для однозначности результата вводится условие: степень многочлена-остатка должна быть строго меньше степени делителя:

${\displaystyle f(x)=q(x)g(x)+r(x)}$, причём ${\displaystyle \deg(r)<\deg(g)}$.

Пример

${\displaystyle {\frac {2x^{2}+4x+5}{x+1}}=2x+2}$ (остаток 3), так как: ${\displaystyle 2x^{2}+4x+5=(x+1)(2x+2)+3}$.