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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Деление c остатком (деление по модулю) — арифметическая операция, разновидность операции деления целого числа на другое целое число. Результатом операции являются два целых числа: неполное частное и остаток от деления. Например, при делении 7 на 2 неполное частное равно 3, а остаток равен 1:

7 = 2 \times 3 + 1

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

Определение[править | править вики-текст]

Натуральные числа[править | править вики-текст]

Разделить целое число a\, на натуральнoе число b > 0\, с остатком означает представить его в виде суммы:

a = b\,q + r,\quad 0 \leqslant r < b \quad (q \in \mathbb{Z},\,r \in \mathbb{Z}).

При этом q\, называется неполным частным, а r\, — остатком от деления a на b.

Примеры.

  • При делении с остатком положительного числа a = 78 на b = 33 получаем неполное частное q = 2 и остаток r = 12.
Проверка: 78 = 33 \cdot 2 + 12.
  • При делении с остатком отрицательного числа a = -78 на b = 33 получаем неполное частное q = -3 и остаток r = 21.
Проверка: -78 = 33 \cdot (-3) + 21.

Обобщения[править | править вики-текст]

Целые числа[править | править вики-текст]

Формула

r = a - \lfloor a/b \rfloor\cdot b

даёт обобщение понятия остатка на случай деления целого числа a на целое (ненулевое) число b. При этом выполняется соотношение a = bq+r и неравенство ~0\leqslant |r|<|b|.

Пример.

  • При делении с остатком положительного числа a = 17 на b = 33 получаем неполное частное q = 0 и остаток r = 17. Проверка: 17 = 33 \cdot 0 + 17.

Вещественные числа[править | править вики-текст]

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

Формально:

если a,b\in \mathbb{R}, b\ne 0, то ~a = p b+q, где 0\leqslant q< |b|

Пример:

~ 7{,}9 : 2{,}1 = 3 (остаток 1,6)

Многочлены[править | править вики-текст]

При делении двух полиномов f(x) и g(x) степень остаточного полинома должна быть строго меньше степени делителя:

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

Пример:

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

В программировании[править | править вики-текст]

Операция вычисления неполного частного и остатка в различных языках программирования
Язык Неполное
частное
Остаток Знак остатка
ActionScript % Делимое
Ada mod Делитель
rem Делимое
ASP Mod Не определено
Бейсик \ MOD Не определено
Си (ISO 1990) / % Не определено
Си (ISO 1999) / % Делимое[1]
C++ (ISO 2003) / % Не определено[2]
C++ (ISO 2011) / % Делимое[3]
C# / % Делимое
ColdFusion MOD Делимое
Common Lisp mod Делитель
rem Делимое
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 mod Делитель
/ rem Делимое
J |~ Делитель
Java / % Делимое[4]
JavaScript % Делимое
Lua % Делитель
Mathematica Mod Делитель
MATLAB idivide(?, ?, 'floor') mod Делитель
idivide rem Делимое
MySQL DIV MOD
%
Делимое
Objective Caml mod Не определено
Pascal div mod Делимое[5]
Perl Нет % Делитель
PHP /[6] % Делимое
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

Знак остатка[править | править вики-текст]

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

  • Знак остатка совпадает со знаком делимого: неполное частное округляет к нулю.
  • Знак остатка совпадает со знаком делителя: неполное частное округляет к −∞, если делитель положительный, и к +∞, если отрицательный.

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

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

Как запрограммировать, если такой операции нет?[править | править вики-текст]

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 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 данное изменение не числится.
  2. ««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».
  3. N3242=11-0012 (Working draft), текст совпадает с C99
  4. К. Арнолд, Дж. Гослинг, Д. Холмс Язык программирования Java. — 3-е изд. — М., СПб., Киев: Вильямс, 2001. — С. 173—174. — ISBN 5-8459-0215-0
  5. Стандарт 1973 года: div — division with truncation.
  6. Здесь в языке с динамической типизацией надо быть предельно осторожным: поведение операции / зависит от типа операндов, и если требуется дробное деление, стоит использовать код наподобие x / 2.0.