В вычислениях операция по модулю возвращает остаток или знаковый остаток от деления после того, как одно число делится на другое (называемое модулем операции).
Учитывая два положительных числа a и n , модуль n (часто сокращенно mod n ) является остатком евклидова деления a на n , где a — делимое , а n — делитель . [1]
Например, выражение «5 по модулю 2» оценивается как 1, поскольку 5, разделенное на 2, имеет частное 2 и остаток 1, а выражение «9 по модулю 3» будет равно 0, поскольку 9, разделенное на 3, имеет частное 3 и остаток 0.
Хотя обычно a и n являются целыми числами , многие вычислительные системы теперь допускают другие типы числовых операндов. Диапазон значений для целочисленной операции по модулю n составляет от 0 до n - 1 ( модуль 1 всегда равен 0; мод 0 не определен, поскольку представляет собой деление на ноль ).
Когда ровно одно из a или n отрицательно, базовое определение нарушается, и языки программирования различаются в том, как определяются эти значения.
В математике результатом операции по модулю является класс эквивалентности , и любой член класса может быть выбран в качестве представителя ; однако обычным представителем является наименьший положительный остаток , наименьшее неотрицательное целое число, принадлежащее этому классу (т. е. остаток евклидова деления ). [2] Однако возможны и другие соглашения. Компьютеры и калькуляторы имеют различные способы хранения и представления чисел; таким образом, их определение операции по модулю зависит от языка программирования или базового оборудования .
Почти во всех вычислительных системах частное q и остаток r от деления на n удовлетворяют следующим условиям:
Это по-прежнему оставляет неоднозначность знака, если остаток ненулевой: возможны два возможных выбора для остатка: один отрицательный, а другой положительный, и этот выбор определяет, какой из двух последовательных частных должен использоваться для удовлетворения уравнений (1). В теории чисел всегда выбирается положительный остаток, но в вычислительной технике языки программирования выбирают в зависимости от языка и знаков a или n . [a] Стандартный Паскаль и АЛГОЛ 68 , например, дают положительный остаток (или 0) даже для отрицательных делителей, а некоторые языки программирования, такие как C90, оставляют это на усмотрение реализации, когда любое из n или a отрицательно (см. подробности в таблице в разделе «В языках программирования»). модуль 0 не определен в большинстве систем, хотя некоторые определяют его как .
Во многих реализациях используется усеченное деление , для которого частное определяется выражением
где – целая часть функции ( округление в сторону нуля ), т.е. усечение до нуля значащих цифр. Таким образом, согласно уравнению ( 1 ), остаток имеет тот же знак, что и делимое a , поэтому может принимать 2| п | − 1 значение:
Дональд Кнут [3] продвигает напольное деление , для которого частное определяется выражением
где ⌊⌋ — функция пола ( округление вниз ). Таким образом, согласно уравнению ( 1 ), остаток имеет тот же знак, что и делитель n :
Раймонд Т. Баут [4] продвигает евклидово деление , для которого частное определяется формулой
где sn — знаковая функция , ⌊⌋ — функция пола ( округление вниз ), а ⌈⌉ — функция потолка ( округление вверх ). Таким образом, согласно уравнению ( 1 ), остаток неотрицательен :
Common Lisp и IEEE 754 используют округленное деление , для которого частное определяется выражением
где round — функция округления ( округление половины до четного ). Таким образом, согласно уравнению ( 1 ), остаток попадает между и , а его знак зависит от того, с какой стороны от нуля он попадает в эти границы:
Common Lisp также использует потолочное деление , для которого частное определяется выражением
где ⌈⌉ — функция потолка ( округление в большую сторону ). Таким образом, согласно уравнению ( 1 ), остаток имеет знак, противоположный знаку делителя :
Если и делимое, и делитель положительны, то усеченное, минимальное и евклидово определения совпадают. Если делимое положительно, а делитель отрицателен, то усеченное и евклидово определения согласуются. Если делимое отрицательно, а делитель положителен, то определения пола и Евклида согласуются. Если и делимое, и делитель отрицательны, то усеченное и минимальное определения совпадают.
Как описывает Лейен,
Баут утверждает, что евклидово деление превосходит другие с точки зрения регулярности и полезных математических свойств, хотя напольное деление, предложенное Кнутом, также является хорошим определением. Несмотря на широкое использование, усеченное деление уступает другим определениям.
- Даан Лейен, Деление и модуль для компьютерщиков [5]
Однако усеченное деление удовлетворяет тождеству . [6]
В некоторых калькуляторах есть функциональная кнопка mod() , и во многих языках программирования есть аналогичная функция, выраженная, например, как mod( a , n ) . Некоторые из них также поддерживают выражения, которые используют «%», «mod» или «Mod» в качестве оператора по модулю или остатку , например a % n
или a mod n
.
Для сред, в которых отсутствует подобная функция, можно использовать любое из трех приведенных выше определений.
Когда результат операции по модулю имеет знак делимого (усеченное определение), это может привести к неожиданным ошибкам.
Например, чтобы проверить, является ли целое число нечетным , можно проверить, равен ли остаток от 2 1:
bool is_odd ( int n ) { return n % 2 == 1 ; }
Но в языке, где по модулю есть знак делимого, это неверно, потому что, когда n (делимое) отрицательное и нечетное, n mod 2 возвращает −1, а функция возвращает false.
Одна правильная альтернатива — проверить, что остаток не равен 0 (поскольку остаток 0 одинаков независимо от знаков):
bool is_odd ( int n ) { return n % 2 != 0 ; }
Другая альтернатива — использовать тот факт, что для любого нечетного числа остаток может быть либо 1, либо −1:
bool is_odd ( int n ) { return n % 2 == 1 || п % 2 == -1 ; }
Более простая альтернатива — рассматривать результат n % 2 как логическое значение, где любое ненулевое значение является истинным:
bool is_odd ( int n ) { return n % 2 ; }
Операции по модулю могут быть реализованы таким образом, чтобы каждый раз вычислялось деление с остатком. В особых случаях на некотором оборудовании существуют более быстрые альтернативы. Например, модуль степени 2 можно альтернативно выразить как побитовую операцию И (при условии, что x является положительным целым числом или с использованием определения без усечения):
x % 2n == x & (2n - 1)
Примеры:
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7
В устройствах и программном обеспечении, которые реализуют побитовые операции более эффективно, чем по модулю, эти альтернативные формы могут привести к более быстрым вычислениям. [7]
Оптимизация компилятора может распознавать выражения вида expression % constant
где constant
– степень двойки и автоматически реализовывать их как expression & (constant-1)
, что позволяет программисту писать более понятный код без ущерба для производительности. Эта простая оптимизация невозможна для языков, в которых результат операции по модулю имеет знак делимого (включая C ), если только делимое не имеет целочисленного типа без знака . Это потому, что, если дивиденд отрицательный, модуль будет отрицательным, тогда как expression & (constant-1)
всегда будет положительным. Для этих языков вместо этого необходимо использовать эквивалентность , выраженную с помощью побитовых операций ИЛИ, НЕ и И.x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)
Оптимизация для общих операций с постоянным модулем также существует путем сначала вычисления деления с использованием оптимизации постоянного делителя .
Некоторые операции по модулю можно факторизовать или расширять аналогично другим математическим операциям. Это может быть полезно при доказательствах криптографии , таких как обмен ключами Диффи-Хеллмана . Некоторые из этих свойств [ какие? ] требуют, чтобы a и n были целыми числами.
Кроме того, многие компьютерные системы предоставляют divmod
функцию, позволяющую одновременно вычислять частное и остаток. Примеры включают инструкцию архитектуры x86IDIV
, функцию языка программирования C div()
и функцию Pythondivmod()
.
Иногда полезно, чтобы результат по модулю n находился не между 0 и n − 1 , а между некоторым числом d и d + n − 1 . В этом случае d называется смещением , и d = 1 встречается особенно часто.
Похоже , что для этой операции не существует стандартной записи, поэтому давайте условно воспользуемся модом d n . Таким образом, мы имеем следующее определение: [56] x = a mod d n только в случае d ≤ x ≤ d + n − 1 и x mod n = a mod n . Очевидно, что обычная операция по модулю соответствует смещению нуля: a mod n = a mod 0 n .
Операция по модулю со смещением связана с функцией пола следующим образом:
Чтобы увидеть это, позвольте . Сначала мы покажем, что x mod n = mod n . В общем случае верно, что ( a + bn ) mod n = a mod n для всех целых чисел b ; таким образом, это верно и в частном случае, когда ; но это значит , что именно это мы и хотели доказать. Осталось показать, что d ≤ x ≤ d + n − 1 . Пусть k и r — целые числа такие, что a − d = kn + r , где 0 ≤ r ≤ n − 1 (см. евклидово деление ). Тогда , таким образом . Теперь возьмем 0 ≤ r ≤ n − 1 и прибавим d к обеим частям, получив d ≤ d + r ≤ d + n − 1 . Но мы видели, что x = d + r , так что мы закончили.
Модуль со смещением a mod d n реализован в системе Mathematica как Mod[a, n, d]
. [56]
Несмотря на математическую элегантность напольного деления Кнута и евклидова деления, в языках программирования гораздо чаще можно встретить усеченное деление по модулю, основанное на делении. Лейен предлагает следующие алгоритмы для вычисления двух делений с учетом усеченного целочисленного деления: [5]
/* Euclidean и Floored divmod в стиле C ldiv() */ typedef struct { /* Эта структура является частью C stdlib.h, но воспроизводится здесь для ясности */ long int quot ; длинный интервал времени ; } ldiv_t ; /* Евклидово деление */ inline ldiv_t ldivE ( long numer , long denom ) { /* Языки C99 и C++11 определяют оба этих метода как усечение. */ long q = число / деном ; длинный r = число % denom ; если ( р < 0 ) { если ( номинал > 0 ) { q знак равно q - 1 ; г = г + номинал ; } Еще { q = q + 1 ; г = г - номинал ; } } return ( ldiv_t ){. quot = q , . рем = р }; } /* Деление по этажам */ inline ldiv_t ldivF ( long numer , long denom ) { long q = numer / denom ; длинный r = число % denom ; if (( r > 0 && denom < 0 ) || ( r < 0 && denom > 0 )) { q = q - 1 ; г = г + номинал ; } Возврат ( ldiv_t ){. quot = q , . рем = р }; }
В обоих случаях остаток можно вычислить независимо от частного, но не наоборот. Здесь операции объединены для экономии места на экране, поскольку логические ветви одинаковы.
α|ω
вычисляет остаток при делении на .ω
α
%
усечения. [9] Предыдущие стандарты оставляли поведение определяемым реализацией. [10]div
и mod
не подчиняются тождеству деления D = d · ( D / d ) + D % d и, таким образом, фундаментально нарушены.{{cite journal}}
: Требуется цитировать журнал |journal=
( помощь )бинарный оператор % возвращает остаток от деления первого выражения на второе.
.... Если оба операнда неотрицательны, то остаток неотрицательен;
если нет, то знак остатка определяется реализацией
{{cite journal}}
: Требуется цитировать журнал |journal=
( помощь )Функция
fmod
возвращает значение
x - i * y
для некоторого целого числа
i
, такого, что, если
y
не равно нулю, результат имеет тот же знак, что и
x
, и величину меньше, чем величина
y
.
{{cite journal}}
: Требуется цитировать журнал |journal=
( помощь ){{cite book}}
: CS1 maint: числовые имена: список авторов ( ссылка ){{cite book}}
: CS1 maint: числовые имена: список авторов ( ссылка )X по модулю Y, т.е. XY*INT(X/Y).
Функция остатка, т.е. XY*IP(X/Y).
Если оба операнда неотрицательны, то остаток неотрицательен.
Результаты не определены, если один или оба операнда отрицательны.
Оператор % определяется только в тех случаях, когда либо обе стороны положительны, либо обе стороны отрицательны.
В отличие от C, он также работает с типами данных с плавающей запятой, а также с целыми числами.