Деление с остатком
Деление c остатком — арифметическая операция, играющая большую роль в арифметике, теории чисел, алгебре и криптографии. Чаще всего эта операция определяется для целых или натуральных чисел следующим образом[1]. Пусть [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] — целые числа, причём [math]\displaystyle{ b \ne 0. }[/math] Деление с остатком [math]\displaystyle{ a }[/math] («делимого») на [math]\displaystyle{ b }[/math] («делитель») означает нахождение таких целых чисел [math]\displaystyle{ q }[/math] и [math]\displaystyle{ r }[/math], что выполняется равенство:
- [math]\displaystyle{ a = b \cdot q+r }[/math]
Таким образом, результатами деления с остатком являются два целых числа: [math]\displaystyle{ q }[/math] называется неполным частным от деления, а [math]\displaystyle{ r }[/math] — остатком от деления. На остаток налагается дополнительное условие: [math]\displaystyle{ 0 \leqslant r \lt |b|, }[/math] то есть остаток от деления должен быть неотрицательным числом и по абсолютной величине меньше делителя. Это условие обеспечивает однозначность результатов деления с остатком для всех целых чисел, то есть существует единственное решение уравнения [math]\displaystyle{ a = b \cdot q+r }[/math] при заданных выше условиях. Если остаток равен нулю, говорят, что [math]\displaystyle{ a }[/math] нацело делится на [math]\displaystyle{ b. }[/math]
Нахождение неполного частного также называют целочисленным делением, а нахождение остатка от деления называют взятием остатка или, неформально, делением по модулю (однако последний термин стоит избегать, так как он может привести к путанице с делением в кольце или группе вычетов по аналогии со сложением или умножением по модулю).
- Примеры
- При делении с остатком положительного числа [math]\displaystyle{ a = 78 }[/math] на [math]\displaystyle{ b = 33 }[/math] получаем неполное частное [math]\displaystyle{ q = 2 }[/math] и остаток [math]\displaystyle{ r = 12 }[/math].
- Проверка: [math]\displaystyle{ 78 = 33 \cdot 2 + 12. }[/math]
- При делении с остатком отрицательного числа [math]\displaystyle{ a = -78 }[/math] на [math]\displaystyle{ b = 33 }[/math] получаем неполное частное [math]\displaystyle{ q = -3 }[/math] и остаток [math]\displaystyle{ r = 21 }[/math].
- Проверка: [math]\displaystyle{ -78 = 33 \cdot (-3) + 21. }[/math]
- При делении с остатком отрицательного числа [math]\displaystyle{ a = -9 }[/math] на [math]\displaystyle{ b = -13 }[/math] получаем неполное частное [math]\displaystyle{ q = 1 }[/math] и остаток [math]\displaystyle{ r = 4 }[/math].
- Проверка: [math]\displaystyle{ -9 = 1 \cdot (-13) + 4. }[/math]
- При делении с остатком положительного числа [math]\displaystyle{ a = 9 }[/math] на [math]\displaystyle{ b = 90 }[/math] получаем неполное частное [math]\displaystyle{ q = 0 }[/math] и остаток [math]\displaystyle{ r = 9 }[/math].
- Проверка: [math]\displaystyle{ 9 = 90 \cdot 0 + 9. }[/math]
- При делении с остатком числа [math]\displaystyle{ a = 78 }[/math] на [math]\displaystyle{ b = 26 }[/math] получаем неполное частное [math]\displaystyle{ q = 3 }[/math] и остаток [math]\displaystyle{ r = 0 }[/math], то есть деление выполняется нацело.
Операция деления с остатком может быть определена не только для целых чисел, но и для других математических объектов (например, для многочленов), см. ниже.
Определение
Оставаясь строго в рамках натуральных чисел, приходится различать деление с остатком и деление нацело, поскольку нулевой остаток не является натуральным числом; кроме того, неполное частное при делении меньшего числа на большее должно равняться нулю, что тоже выводит за рамки натуральных чисел. Все эти искусственные ограничения неоправданно усложняют формулировки, поэтому в источниках обычно либо рассматривается расширенный натуральный ряд, включающий ноль[2], либо теория сразу формулируется для целых чисел, как указано выше[1].
Для вычисления неполного частного от деления [math]\displaystyle{ a }[/math] на положительное число [math]\displaystyle{ b }[/math] следует разделить (в обычном смысле) [math]\displaystyle{ a }[/math] на [math]\displaystyle{ b }[/math] и округлить результат до ближайшего целого в меньшую сторону:
- [math]\displaystyle{ q = \left\lfloor \frac{a}{b}\right\rfloor, }[/math] когда [math]\displaystyle{ b\gt 0 }[/math].
где полускобки [math]\displaystyle{ \left\lfloor \cdot\right\rfloor }[/math] обозначают взятие целой части. Значение неполного частного [math]\displaystyle{ q }[/math] позволяет вычислить значение остатка [math]\displaystyle{ r }[/math] по формуле:
- [math]\displaystyle{ r = a - b \cdot q. }[/math]
Для отрицательного делителя нужно округлять частное в большую сторону:
- [math]\displaystyle{ q = \left\lceil \frac{a}{b}\right\rceil, }[/math] когда [math]\displaystyle{ b\lt 0 }[/math].
Операция «mod» и связь со сравнениями
Величина остатка может быть получена бинарной операцией «взятия остатка» от деления [math]\displaystyle{ a }[/math] на [math]\displaystyle{ b }[/math], обозначаемой mod:
- [math]\displaystyle{ r = a \bmod b. }[/math]
Не следует путать это обозначение с обозначением сравнения по модулю [math]\displaystyle{ b }[/math]. Формула для [math]\displaystyle{ r }[/math] влечёт выполнение сравнения:
- [math]\displaystyle{ r \equiv a \pmod{b}, }[/math]
однако обратная импликация, вообще говоря, неверна. А именно, это сравнение не подразумевает выполнения неравенства [math]\displaystyle{ 0 \leqslant r \lt |b| }[/math], необходимого для того, чтобы [math]\displaystyle{ 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]\displaystyle{ -\infty }[/math].
Если в языке есть оба типа остатков, каждому из них соответствует своя операция неполного частного. Обе операции имеют жизненный смысл.
- Есть сумма [math]\displaystyle{ n }[/math] копеек, положительная или отрицательная. Перевести её в рубли и копейки:
n div 100
иn mod 100
. Знак остатка совпадает со знаком делимого. - Есть бесконечное клеточное поле, каждая клетка 16×16 пикселей. В какую клетку попадает точка ([math]\displaystyle{ x }[/math], [math]\displaystyle{ y }[/math]), и каковы координаты относительно верхнего левого угла клетки? Ответ:
x div 16, y div 16
и(x mod 16, y mod 16)
соответственно. Знак остатка совпадает со знаком делителя.
Операция div
в x86/x64 делит регистровую пару rdx:rax
на любой другой регистр или число из памяти[10]. Неполное частное и остаток выходят по первому варианту — округляют к нулю.
Как запрограммировать, если такой операции нет?
Неполное частное можно вычислить через деление и взятие целой части: [math]\displaystyle{ q = \left[\frac{a}{b}\right] }[/math], где [math]\displaystyle{ [x] }[/math], в зависимости от задачи, может быть «полом» или усечением. Однако деление здесь получается дробное, которое намного медленнее целого. Такой алгоритм используется в языках, в которых нет целых типов (отдельные электронные таблицы, программируемые калькуляторы и математические программы), а также в скриптовых языках, в которых издержки интерпретации намного превышают издержки дробной арифметики (Perl, PHP).
При отсутствии команды mod
остаток программируется как [math]\displaystyle{ a - qb }[/math].
Если [math]\displaystyle{ b }[/math] положительно, а знак [math]\displaystyle{ r }[/math] совпадает со знаком делимого, не определён или неизвестен, для нахождения минимального неотрицательного остатка можно воспользоваться формулой [math]\displaystyle{ r' = (b+(a \operatorname{mod} b)) \operatorname{mod} b }[/math].
Неполное частное и неотрицательный остаток от деления на степень двойки [math]\displaystyle{ 2^n }[/math] — это битовый сдвиг [math]\displaystyle{ a \gg n }[/math] (для чисел со знаком — арифметический) и [math]\displaystyle{ a \operatorname{\&} (2^n - 1) }[/math].
Обобщения
Вещественные числа
Если два числа [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] (отличное от нуля) относятся к множеству вещественных чисел, [math]\displaystyle{ a }[/math] может быть поделено на [math]\displaystyle{ b }[/math] без остатка, и при этом частное также является вещественным числом. Если же частное по условию должно быть целым числом, в этом случае остаток будет вещественным числом, то есть может оказаться дробным.
Формально:
- если [math]\displaystyle{ a,b\in \mathbb{R}, b\ne 0 }[/math], то [math]\displaystyle{ a = bq+r }[/math], где [math]\displaystyle{ 0\leqslant r\lt |b| }[/math].
- Пример
Деление 7,9 на 2,1 с остатком даёт:
- [math]\displaystyle{ \left\lfloor \frac{7{,}9}{2{,}1}\right\rfloor = 3 }[/math] (неполное частное);
- [math]\displaystyle{ 7{,}9 - 3\cdot 2{,}1 = 1{,}6 }[/math] (остаток).
Гауссовы целые числа
Гауссово число — это комплексное число вида [math]\displaystyle{ a+bi }[/math], где [math]\displaystyle{ a, b }[/math] — целые числа. Для них можно определить деление с остатком: любое гауссово число [math]\displaystyle{ u }[/math] можно разделить с остатком на любое ненулевое гауссово число [math]\displaystyle{ v }[/math], то есть представить в виде:
- [math]\displaystyle{ u = vq + r }[/math],
где частное [math]\displaystyle{ q }[/math] и остаток [math]\displaystyle{ r }[/math] — гауссовы числа, причём [math]\displaystyle{ |r|\lt |v|. }[/math] Однако, в отличие от целых чисел, остаток от деления определяется неоднозначно. Например, [math]\displaystyle{ 7+2i }[/math] можно разделить на [math]\displaystyle{ 3-i }[/math] тремя способами:
- [math]\displaystyle{ 7+2i = (3-i)(2+i)+i = (3-i)(1+i)+3 = (3-i)(2+2i)+(-1-2i). }[/math]
Многочлены
При делении с остатком двух многочленов [math]\displaystyle{ f(x) }[/math] и [math]\displaystyle{ g(x) }[/math] для однозначности результата вводится условие: степень многочлена-остатка должна быть строго меньше степени делителя:
- [math]\displaystyle{ f(x) = q(x) g(x) + r(x) }[/math], причём [math]\displaystyle{ \deg(r) \lt \deg(g) }[/math].
- Пример
- [math]\displaystyle{ \frac{2x^2 + 4x + 5}{x+1} = 2x + 2 }[/math] (остаток 3), так как: [math]\displaystyle{ 2x^2 + 4x + 5 = (x + 1)(2x + 2) + 3 }[/math].
См. также
Примечания
- ↑ Перейти обратно: 1,0 1,1 Деление // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1979. — Т. 2.
- ↑ Потапов М. К., Александров В. В., Пасиченко П. И. Алгебра и анализ элементарных функций. М.: Наука, 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 данное изменение не числится. - ↑ «ISO/IEC 14882:2003 : Programming languages -- C++», 5.6.4: International Organization for Standardization, International Electrotechnical Commission, 2003. «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
- ↑ D language specification (англ.) (недоступная ссылка). dlang.org. Дата обращения: 29 октября 2017. Архивировано 3 октября 2017 года.
- ↑ Арнолд, Кен, Гослинг, Дж., Холмс, Д. Язык программирования Java. — 3-е изд. — М., СПб., Киев: Вильямс, 2001. — С. 173—174. — ISBN 5-8459-0215-0.
- ↑ Стандарт 1973 года: div — division with truncation.
- ↑ PHP: Arithmetic Operators — Manual . Дата обращения: 27 ноября 2014. Архивировано 19 ноября 2014 года.
- ↑ DIV — Unsigned Divide