Русская Википедия:Деление с остатком
Деление c остатком — арифметическая операция, играющая большую роль в арифметике, теории чисел, алгебре и криптографии. Чаще всего эта операция определяется для целых или натуральных чисел следующим образом[1]. Пусть <math>a</math> и <math>b</math> — целые числа, причём <math>b \ne 0.</math> Деление с остатком <math>a</math> («делимого») на <math>b</math> («делитель») означает нахождение таких целых чисел <math>q</math> и <math>r</math>, что выполняется равенство:
- <math>a = b \cdot q+r</math>
Таким образом, результатами деления с остатком являются два целых числа: <math>q</math> называется неполным частным от деления, а <math>r</math> — остатком от деления. На остаток налагается дополнительное условие: <math>0 \leqslant r < |b|,</math> то есть остаток от деления должен быть неотрицательным числом и по абсолютной величине меньше делителя. Это условие обеспечивает однозначность результатов деления с остатком для всех целых чисел, то есть существует единственное решение уравнения <math>a = b \cdot q+r</math> при заданных выше условиях. Если остаток равен нулю, говорят, что <math>a</math> нацело делится на <math>b.</math>
Нахождение неполного частного также называют целочисленным делением, а нахождение остатка от деления называют взятием остатка или, неформально, делением по модулю (однако последний термин стоит избегать, так как он может привести к путанице с делением в кольце или группе вычетов по аналогии со сложением или умножением по модулю).
- Примеры
- При делении с остатком положительного числа <math>a = 78</math> на <math>b = 33</math> получаем неполное частное <math>q = 2</math> и остаток <math>r = 12</math>.
- Проверка: <math>78 = 33 \cdot 2 + 12.</math>
- При делении с остатком отрицательного числа <math>a = -78</math> на <math>b = 33</math> получаем неполное частное <math>q = -3</math> и остаток <math>r = 21</math>.
- Проверка: <math>-78 = 33 \cdot (-3) + 21.</math>
- При делении с остатком отрицательного числа <math>a = -9</math> на <math>b = -13</math> получаем неполное частное <math>q = 1</math> и остаток <math>r = 4</math>.
- Проверка: <math>-9 = 1 \cdot (-13) + 4.</math>
- При делении с остатком положительного числа <math>a = 9</math> на <math>b = 90</math> получаем неполное частное <math>q = 0</math> и остаток <math>r = 9</math>.
- Проверка: <math>9 = 90 \cdot 0 + 9.</math>
- При делении с остатком числа <math>a = 78</math> на <math>b = 26</math> получаем неполное частное <math>q = 3</math> и остаток <math>r = 0</math>, то есть деление выполняется нацело.
Операция деления с остатком может быть определена не только для целых чисел, но и для других математических объектов (например, для многочленов), см. ниже.
Определение
Оставаясь строго в рамках натуральных чисел, приходится различать деление с остатком и деление нацело, поскольку нулевой остаток не является натуральным числом; кроме того, неполное частное при делении меньшего числа на большее должно равняться нулю, что тоже выводит за рамки натуральных чисел. Все эти искусственные ограничения неоправданно усложняют формулировки, поэтому в источниках обычно либо рассматривается расширенный натуральный ряд, включающий ноль[2], либо теория сразу формулируется для целых чисел, как указано выше[1].
Для вычисления неполного частного от деления <math>a</math> на положительное число <math>b</math> следует разделить (в обычном смысле) <math>a</math> на <math>b</math> и округлить результат до ближайшего целого в меньшую сторону:
- <math>q = \left\lfloor \frac{a}{b}\right\rfloor,</math> когда <math>b>0</math>.
где полускобки <math>\left\lfloor \cdot\right\rfloor</math> обозначают взятие целой части. Значение неполного частного <math>q</math> позволяет вычислить значение остатка <math>r</math> по формуле:
- <math>r = a - b \cdot q.</math>
Для отрицательного делителя нужно округлять частное в большую сторону:
- <math>q = \left\lceil \frac{a}{b}\right\rceil,</math> когда <math>b<0</math>.
Операция «mod» и связь со сравнениями
Шаблон:Anchor Величина остатка может быть получена бинарной операцией «взятия остатка» от деления <math>a</math> на <math>b</math>, обозначаемой Шаблон:Math:
- <math>r = a \bmod b.</math>
Не следует путать это обозначение с обозначением сравнения по модулю <math>b</math>. Формула для <math>r</math> влечёт выполнение сравнения:
- <math>r \equiv a \pmod{b},</math>
однако обратная импликация, вообще говоря, неверна. А именно, это сравнение не подразумевает выполнения неравенства <math>0 \leqslant r < |b|</math>, необходимого для того, чтобы <math>r</math> было остатком.
В программировании
| Язык | Неполное частное |
Остаток | Знак остатка |
|---|---|---|---|
| ActionScript | % |
Делимое | |
| Ada | mod |
Делитель | |
rem |
Делимое | ||
| Бейсик | \ |
MOD |
Не определено |
| Си (ISO 1990) | / |
% |
Не определено |
| Си (ISO 1999) | / |
% |
Делимое[3] |
| C++ (ISO 2003) | / |
% |
Не определено[4] |
| C++ (ISO 2011) | / |
% |
Делимое[5] |
| C# | / |
% |
Делимое |
| ColdFusion | MOD |
Делимое | |
| Common Lisp | mod |
Делитель | |
rem |
Делимое | ||
| D | / |
% |
Делимое[6] |
| Delphi | div |
mod |
Делимое |
| Eiffel | // |
\\ |
Делимое |
| Erlang | div |
rem |
Делимое |
| Euphoria | remainder |
Делимое | |
| Microsoft Excel (англ.) | QUOTIENT() |
MOD()
|
Делитель |
| Microsoft Excel (рус.) | ЧАСТНОЕ() |
ОСТАТ()
| |
| FileMaker | Div() |
Mod() |
Делитель |
| Fortran | mod |
Делимое | |
modulo |
Делитель | ||
| GML (Game Maker) | div |
mod |
Делимое |
| Go | / |
% |
Делимое |
| Haskell | div
|
mod |
Делитель |
quot
|
rem |
Делимое | |
| J | |~ |
Делитель | |
| Java | /
|
%
|
Делимое[7] |
Math.floorDiv
|
Math.floorMod
|
Делитель (1.8+) | |
| JavaScript | .toFixed(0) | % |
Делимое |
| Lua | % |
Делитель | |
| Mathematica | Quotient
|
Mod |
Делитель |
| MATLAB | idivide(?, ?, 'floor') |
mod |
Делитель |
idivide |
rem |
Делимое | |
| MySQL | DIV |
MOD% |
Делимое |
| Oberon | DIV |
MOD |
+ |
| Objective Caml | mod |
Не определено | |
| Pascal | div |
mod |
Делимое[8] |
| Perl | Нет | % |
Делитель |
| PHP | Нет[9] | % |
Делимое |
| PL/I | mod |
Делитель (ANSI PL/I) | |
| Prolog (ISO 1995) | mod |
Делитель | |
| PureBasic | / |
Mod% |
Делимое |
| Python | // |
% |
Делитель |
| QBasic | \ |
MOD |
Делимое |
| R | %/% | %% |
Делитель |
| RPG | %REM |
Делимое | |
| Ruby | /
|
% |
Делитель |
| Scheme | modulo |
Делитель | |
| SenseTalk | modulo |
Делитель | |
rem |
Делимое | ||
| Tcl | % |
Делитель | |
| Verilog (2001) | % |
Делимое | |
| VHDL | mod |
Делитель | |
rem |
Делимое | ||
| Visual Basic | \ |
Mod |
Делимое |
Нахождение остатка от деления часто используется в компьютерной технике и телекоммуникационном оборудовании для создания контрольных чисел и получения случайных чисел в ограниченном диапазоне, например в конгруэнтном генераторе случайных чисел.
Обозначения операции взятия остатка в различных языках программирования представлены в таблице справа.
Например, в Паскале операция mod вычисляет остаток от деления, а операция div осуществляет целочисленное деление, при котором остаток от деления отбрасывается:
78 mod 33 = 12
78 div 33 = 2
Знак остатка
Операция взятия остатка в языках программирования может возвращать отрицательный результат (для отрицательного делимого или делителя). Тут есть два варианта:
- Знак остатка совпадает со знаком делимого: неполное частное округляет к нулю.
- Знак остатка совпадает со знаком делителя: неполное частное округляет к <math>-\infty</math>.
Если в языке есть оба типа остатков, каждому из них соответствует своя операция неполного частного. Обе операции имеют жизненный смысл.
- Есть сумма <math>n</math> копеек, положительная или отрицательная. Перевести её в рубли и копейки:
n div 100иn mod 100. Знак остатка совпадает со знаком делимого. - Есть бесконечное клеточное поле, каждая клетка 16×16 пикселей. В какую клетку попадает точка (<math>x</math>, <math>y</math>), и каковы координаты относительно верхнего левого угла клетки? Ответ:
x div 16, y div 16и(x mod 16, y mod 16)соответственно. Знак остатка совпадает со знаком делителя.
Операция div в x86/x64 делит регистровую пару rdx:rax на любой другой регистр или число из памяти[10]. Неполное частное и остаток выходят по первому варианту — округляют к нулю.
Как запрограммировать, если такой операции нет?
Неполное частное можно вычислить через деление и взятие целой части: <math>q = \left[\frac{a}{b}\right]</math>, где <math>[x]</math>, в зависимости от задачи, может быть «полом» или усечением. Однако деление здесь получается дробное, которое намного медленнее целого. Такой алгоритм используется в языках, в которых нет целых типов (отдельные электронные таблицы, программируемые калькуляторы и математические программы), а также в скриптовых языках, в которых издержки интерпретации намного превышают издержки дробной арифметики (Perl, PHP).
При отсутствии команды mod остаток программируется как <math>a - qb</math>.
Если <math>b</math> положительно, а знак <math>r</math> совпадает со знаком делимого, не определён или неизвестен, для нахождения минимального неотрицательного остатка можно воспользоваться формулой <math>r' = (b+(a \operatorname{mod} b)) \operatorname{mod} b</math>.
Неполное частное и неотрицательный остаток от деления на степень двойки <math>2^n</math> — это битовый сдвиг <math>a \gg n</math> (для чисел со знаком — арифметический) и <math>a \operatorname{\&} (2^n - 1)</math>.
Обобщения
Вещественные числа
Если два числа <math>a</math> и <math>b</math> (отличное от нуля) относятся к множеству вещественных чисел, <math>a</math> может быть поделено на <math>b</math> без остатка, и при этом частное также является вещественным числом. Если же частное по условию должно быть целым числом, в этом случае остаток будет вещественным числом, то есть может оказаться дробным.
Формально:
- если <math>a,b\in \mathbb{R}, b\ne 0</math>, то <math>a = bq+r</math>, где <math>0\leqslant r< |b|</math>.
- Пример
Деление 7,9 на 2,1 с остатком даёт:
- <math>\left\lfloor \frac{7{,}9}{2{,}1}\right\rfloor = 3</math> (неполное частное);
- <math>7{,}9 - 3\cdot 2{,}1 = 1{,}6</math> (остаток).
Гауссовы целые числа
Гауссово число — это комплексное число вида <math>a+bi</math>, где <math>a, b</math> — целые числа. Для них можно определить деление с остатком: любое гауссово число <math>u</math> можно разделить с остатком на любое ненулевое гауссово число <math>v</math>, то есть представить в виде:
- <math>u = vq + r</math>,
где частное <math>q</math> и остаток <math>r</math> — гауссовы числа, причём <math>|r|<|v|.</math> Однако, в отличие от целых чисел, остаток от деления определяется неоднозначно. Например, <math>7+2i</math> можно разделить на <math>3-i</math> тремя способами:
- <math>7+2i = (3-i)(2+i)+i = (3-i)(1+i)+3 = (3-i)(2+2i)+(-1-2i).</math>
Многочлены
При делении с остатком двух многочленов <math>f(x)</math> и <math>g(x)</math> для однозначности результата вводится условие: степень многочлена-остатка должна быть строго меньше степени делителя:
- <math>f(x) = q(x) g(x) + r(x) </math>, причём <math> \deg(r) < \deg(g)</math>.
- Пример
- <math>\frac{2x^2 + 4x + 5}{x+1} = 2x + 2</math> (остаток 3), так как: <math>2x^2 + 4x + 5 = (x + 1)(2x + 2) + 3</math>.
См. также
Примечания
- ↑ 1,0 1,1 Шаблон:Книга
- ↑ Потапов М. К., Александров В. В., Пасиченко П. И. Алгебра и анализ элементарных функций. М.: Наука, 1981, 560 с., С. 9.
- ↑ ISO/IEC 9899:TC2: When integers are divided, the result of the
/operator is the algebraic quotient with any fractional part discarded. [This is often called «truncation toward zero».]; в списке изменений 1999→TC1 и TC1→TC2 данное изменение не числится. - ↑ Шаблон:Citation. «the binary % operator yields the remainder from the division of the first expression by the second. …. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined».
- ↑ N3242=11-0012 (Working draft), текст совпадает с C99
- ↑ Шаблон:Cite web
- ↑ Шаблон:Книга
- ↑ Стандарт 1973 года: div — division with truncation.
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
