Модуль

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

Учитывая два положительных числа $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$ удовлетворяют следующим условиям:

{\begin{aligned}&q\in \mathbb {Z} \\&a=nq+r\\&|r|<|n|\end{aligned}}

( 1 )

Это по-прежнему оставляет неоднозначность знака, если остаток не равен нулю: возможны два варианта выбора остатка: один отрицательный, а другой положительный; этот выбор определяет, какое из двух последовательных частных необходимо использовать для удовлетворения уравнения (1). В теории чисел всегда выбирается положительный остаток, но в вычислительной технике языки программирования выбирают в зависимости от языка и знаков $a$ или $n$ . ^[а]Стандартный Паскаль и АЛГОЛ 68 , например, дают положительный остаток (или 0) даже для отрицательных делителей, а некоторые языки программирования, такие как C90, оставляют его на усмотрение реализации, когда любое из $n$ или $a$ отрицательно (см. таблицу под § в языках программирования Подробности $). модуль$ 0 не определен в большинстве систем, хотя некоторые определяют его $как$ .

Частное ( $q$ ) и остаток ( $r$ ) как функция делимого ( $a$ ), используя усеченное деление

Во многих реализациях используется усеченное деление , для которого частное определяется выражением

$q=\operatorname {trunc} \left({\frac {a}{n}}\right)$

где $\operatorname {trunc}$ — это целая часть функции ( округление в сторону нуля ), т.е. усечение до нуля значащих цифр. Таким образом, согласно уравнению ( 1 ), остаток имеет тот же знак, что и делимое a, поэтому может принимать $2| п | - 1$ значение:

$r=a-n\operatorname {trunc} \left({\frac {a}{n}}\right)$
Частное и остаток с использованием напольного деления

Дональд Кнут ^[3] способствует напольному делению , для которого частное определяется выражением

$q=\left\lfloor {\frac {a}{n}}\right\rfloor$

где ⌊⌋ — функция пола ( округление вниз ). Таким образом, согласно уравнению ( 1 ), остаток имеет тот же знак, что и делитель n :

$r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor$
Частное и остаток с использованием евклидова деления

Раймонд Т. Бут ^[4] продвигает евклидово деление , для которого частное определяется выражением

$q=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor ={\begin{cases}\left\lfloor {\frac {a}{n}}\right\rfloor &{\text{if }}n>0\\\left\lceil {\frac {a}{n}}\right\rceil &{\text{if }}n<0\\\end{cases}}$

где $sn$ — знаковая функция , ⌊⌋ — функция пола ( округление вниз ), а ⌈⌉ — функция потолка ( округление вверх ). Таким образом, согласно уравнению ( 1 ), остаток неотрицательен :

$r=a-|n|\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor$
Частное и остаток с использованием округленного деления

Common Lisp и IEEE 754 используют округленное деление , для которого частное определяется выражением

$q=\operatorname {round} \left({\frac {a}{n}}\right)$

где $round$ — функция округления ( округление половины до четного ). Таким образом, согласно уравнению ( 1 ), остаток попадает между $-{\frac {n}{2}}$ и ${\frac {n}{2}}$ , а его знак зависит от того, в какую сторону от нуля он попадает в эти границы:

$r=a-n\operatorname {round} \left({\frac {a}{n}}\right)$
Частное и остаток с использованием потолочного деления

Common Lisp также использует потолочное деление , для которого частное определяется выражением

$q=\left\lceil {\frac {a}{n}}\right\rceil$

где ⌈⌉ — функция потолка ( округление в большую сторону ). Таким образом, согласно уравнению ( 1 ), остаток имеет знак, противоположный знаку делителя :

$r=a-n\left\lceil {\frac {a}{n}}\right\rceil$

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

Как описывает Лейен,

Баут утверждает, что евклидово деление превосходит другие с точки зрения регулярности и полезных математических свойств, хотя напольное деление, предложенное Кнутом, также является хорошим определением. Несмотря на широкое использование, усеченное деление уступает другим определениям.
— Даан Лейен, « Деление и модуль для компьютерщиков» ^[5]

Однако усеченное деление удовлетворяет тождеству $({-a})/b={-(a/b)}=a/({-b})$ . ^[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 % 2ⁿ == x & (2ⁿ - 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 % 2ⁿ == x < 0 ? x | ~(2ⁿ - 1) : x & (2ⁿ - 1) Вместо этого необходимо использовать, выраженное с помощью побитовых операций ИЛИ, НЕ и И.

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

Свойства (личности) [ править ]

Некоторые операции по модулю можно факторизовать или расширять аналогично другим математическим операциям. Это может быть полезно при криптографических доказательствах, таких как обмен ключами Диффи-Хеллмана . Свойства, включающие умножение, деление и возведение в степень, обычно требуют, чтобы $a$ и $n$ были целыми числами.

Личность:
- $(мод п) п = мод п .$ мод
- $н Икс mod n = 0$ для всех положительных целых значений $x$ .
- Если $p$ — простое число не делящее b $,$ , то $ab р -1 mod p = a mod p$ по малой теореме Ферма .
Обратный:
- $[(- a mod n) + (a mod n)] mod n знак равно 0$ .
- $б -1 mod n$ обозначает модульную мультипликативную обратную величину , которая определяется тогда и только тогда, когда $b$ и $n$ , взаимно просты что имеет место, когда определена левая часть: $[(b -1 mod n)(b mod n)] mod n знак равно 1$ .
Дистрибутив:
- $(a + b) mod n = [(a mod n) + (b mod n)] mod n$ .
- $ab mod n = [(a mod n)(b mod n)] mod n$ .
Подразделение (определение): $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}a / b mod n = [( a mod n )( b −1 mod n )] mod n$ , когда правая часть определена (то есть, когда $b$ и $n$ ) взаимно просты , и неопределена в противном случае.
Обратное умножение: $[(ab mod n)(b -1 мод n)] n = мод n .$ mod

В языках программирования [ править ]

Операторы по модулю в различных языках программирования
Язык	Оператор	Целое число	Плавающая запятая	Определение
АБАП	`MOD`	Да	Да	евклидов
ActionScript	`%`	Да	Нет	Усечено
Есть	`mod`	Да	Нет	Напольный ^[8]
Есть	`rem`	Да	Нет	Усечено ^[8]
АЛГОЛ 68	`÷×`, `mod`	Да	Нет	евклидов
AMPL	`mod`	Да	Нет	Усечено
АПЛ	`\|`^[б]	Да	Да	Напольный
AppleScript	`mod`	Да	Нет	Усечено
АвтоЛИСП	`(rem d n)`	Да	Нет	Усечено
АВК	`%`	Да	Нет	Усечено
бить	`%`	Да	Нет	Усечено
БАЗОВЫЙ	`Mod`	Да	Нет	Зависит от реализации
До нашей эры	`%`	Да	Нет	Усечено
С С++	`%`, `div`	Да	Нет	Усечено ^[с]
	`fmod` (С) `std::fmod` (С++)	Нет	Да	Усечено ^[11]
	`remainder` (С) `std::remainder` (С++)	Нет	Да	Закругленный
С#	`%`	Да	Да	Усечено
С#	`Math.IEEERemainder`	Нет	Да	Закругленный ^[12]
Кларион	`%`	Да	Нет	Усечено
Чистый	`rem`	Да	Нет	Усечено
Кложур	`mod`	Да	Нет	Напольный ^[13]
Кложур	`rem`	Да	Нет	Усечено ^[14]
КОБОЛ	`FUNCTION MOD`	Да	Нет	Напольный ^[15]
КОБОЛ	`FUNCTION REM`	Да	Да	Усечено ^[15]
Кофескрипт	`%`	Да	Нет	Усечено
Кофескрипт	`%%`	Да	Нет	Напольный ^[16]
Холодный синтез	`%`, `MOD`	Да	Нет	Усечено
Общий промежуточный язык	`rem` (подпись)	Да	Да	Усечено ^[17]
Общий промежуточный язык	`rem.un` (без подписи)	Да	Нет	—
Общий Лисп	`mod`	Да	Да	Напольный
Общий Лисп	`rem`	Да	Да	Усечено
Кристалл	`%`, `modulo`	Да	Да	Напольный
Кристалл	`remainder`	Да	Да	Усечено
Д	`%`	Да	Да	Усечено ^[18]
Дарт	`%`	Да	Да	евклидов ^[19]
Дарт	`remainder()`	Да	Да	Усечено ^[20]
Эйфелева	`\\`	Да	Нет	Усечено
Эликсир	`rem/2`	Да	Нет	Усечено ^[21]
Эликсир	`Integer.mod/2`	Да	Нет	Напольный ^[22]
Вяз	`modBy`	Да	Нет	Напольный ^[23]
Вяз	`remainderBy`	Да	Нет	Усечено ^[24]
Эрланг	`rem`	Да	Нет	Усечено
Эрланг	`math:fmod/2`	Нет	Да	Усеченный (так же, как C) ^[25]
Эйфория	`mod`	Да	Нет	Напольный
Эйфория	`remainder`	Да	Нет	Усечено
Ф#	`%`	Да	Да	Усечено
Ф#	`Math.IEEERemainder`	Нет	Да	Закругленный ^[12]
Фактор	`mod`	Да	Нет	Усечено
Файлмейкер	`Mod`	Да	Нет	Напольный
Форт	`mod`	Да	Нет	Реализация определена
	`fm/mod`	Да	Нет	Напольный
	`sm/rem`	Да	Нет	Усечено
Фортран	`mod`	Да	Да	Усечено
Фортран	`modulo`	Да	Да	Напольный
Фринк	`mod`	Да	Нет	Напольный
Полный БЕЙСИК	`MOD`	Да	Да	Напольный ^[26]
Полный БЕЙСИК	`REMAINDER`	Да	Да	Усечено ^[27]
ГЛСЛ	`%`	Да	Нет	Неопределенный ^[28]
ГЛСЛ	`mod`	Нет	Да	Напольный ^[29]
Студия GameMaker (GML)	`mod`, `%`	Да	Нет	Усечено
GDScript (Годо)	`%`	Да	Нет	Усечено
	`fmod`	Нет	Да	Усечено
	`posmod`	Да	Нет	евклидов
	`fposmod`	Нет	Да	евклидов
Идти	`%`	Да	Нет	Усечено ^[30]
	`math.Mod`	Нет	Да	Усечено ^[31]
	`big.Int.Mod`	Да	Нет	евклидов ^[32]
	`big.Int.Rem`	Да	Нет	Усечено ^[33]
классный	`%`	Да	Нет	Усечено
Хаскелл	`mod`	Да	Нет	Напольный ^[34]
	`rem`	Да	Нет	Усечено ^[34]
	`Data.Fixed.mod'` ( ГХК )	Нет	Да	Напольный
Смешанный	`%`	Да	Нет	Усечено
ХЛСЛ	`%`	Да	Да	Неопределенный ^[35]
Дж	`\|`^[б]	Да	Нет	Напольный
Джава	`%`	Да	Да	Усечено
Джава	`Math.floorMod`	Да	Нет	Напольный
JavaScript Машинопись	`%`	Да	Да	Усечено
Юлия	`mod`	Да	Да	Напольный ^[36]
Юлия	`%`, `rem`	Да	Да	Усечено ^[37]
Котлин	`%`, `rem`	Да	Да	Усечено ^[38]
Котлин	`mod`	Да	Да	Напольный ^[39]
кш	`%`	Да	Нет	Усеченный (так же, как POSIX sh)
кш	`fmod`	Нет	Да	Усечено
ЛабВЬЮ	`mod`	Да	Да	Усечено
LibreOffice	`=MOD()`	Да	Нет	Напольный
Логотип	`MODULO`	Да	Нет	Напольный
Логотип	`REMAINDER`	Да	Нет	Усечено
Второй 5	`%`	Да	Да	Напольный
Второй 4	`mod(x,y)`	Да	Да	Усечено
Свобода БЕЙСИК	`MOD`	Да	Нет	Усечено
Mathcad	`mod(x,y)`	Да	Нет	Напольный
Клен	`e mod m` (по умолчанию), `modp(e, m)`	Да	Нет	евклидов
	`mods(e, m)`	Да	Нет	Закругленный
	`frem(e, m)`	Да	Да	Закругленный
Математика	`Mod[a, b]`	Да	Нет	Напольный
МАТЛАБ	`mod`	Да	Нет	Напольный
МАТЛАБ	`rem`	Да	Нет	Усечено
Максима	`mod`	Да	Нет	Напольный
Максима	`remainder`	Да	Нет	Усечено
Встроенный язык Maya	`%`	Да	Нет	Усечено
Майкрософт Эксель	`=MOD()`	Да	Да	Напольный
Минитаб	`MOD`	Да	Нет	Напольный
Модуль-2	`MOD`	Да	Нет	Напольный
Модуль-2	`REM`	Да	Нет	Усечено
Свинка	`#`	Да	Нет	Напольный
Сетевой ассемблер ( NASM , NASMX )	`%`, `div` (без подписи)	Да	Нет	—
Сетевой ассемблер ( NASM , NASMX )	`%%` (подпись)	Да	Нет	Определяется реализацией ^[40]
Nim	`mod`	Да	Нет	Усечено
Оберон	`MOD`	Да	Нет	Напольный ^[д]
Цель-C	`%`	Да	Нет	Усеченный (то же, что и C99)
Объект Паскаль , Делфи	`mod`	Да	Нет	Усечено
OCaml	`mod`	Да	Нет	Усечено ^[41]
OCaml	`mod_float`	Нет	Да	Усечено ^[42]
Оккам	`\`	Да	Нет	Усечено
Паскаль (ISO-7185 и -10206)	`mod`	Да	Нет	евклидовоподобный ^[Это]
Перл	`%`	Да	Нет	Напольный ^[ф]
Перл	`POSIX::fmod`	Нет	Да	Усечено
Фикс	`mod`	Да	Нет	Напольный
Фикс	`remainder`	Да	Нет	Усечено
PHP	`%`	Да	Нет	Усечено ^[44]
PHP	`fmod`	Нет	Да	Усечено ^[45]
ПИК БЕЙСИК Про	`\\`	Да	Нет	Усечено
ПЛ/Я	`mod`	Да	Нет	Напольный (ANSI PL/I)
PowerShell	`%`	Да	Нет	Усечено
Код программирования ( КНР )	`MATH.OP - 'MOD; (\)'`	Да	Нет	Неопределенный
Прогресс	`modulo`	Да	Нет	Усечено
Пролог ( ISO 1995 )	`mod`	Да	Нет	Напольный
Пролог ( ISO 1995 )	`rem`	Да	Нет	Усечено
PureBasic	`%`, `Mod(x,y)`	Да	Нет	Усечено
Чистый скрипт	`mod`	Да	Нет	евклидов ^[46]
Чистые данные	`%`	Да	Нет	Усеченный (так же, как C)
Чистые данные	`mod`	Да	Нет	Напольный
Питон	`%`	Да	Да	Напольный
Питон	`math.fmod`	Нет	Да	Усечено
Вопрос#	`%`	Да	Нет	Усечено ^[47]
р	`%%`	Да	Да	Напольный ^[48]
Ракетка	`modulo`	Да	Нет	Напольный
Ракетка	`remainder`	Да	Нет	Усечено
Раку	`%`	Нет	Да	Напольный
RealBasic	`MOD`	Да	Нет	Усечено
Причина	`mod`	Да	Нет	Усечено
Рекс	`//`	Да	Да	Усечено
РПГ	`%REM`	Да	Нет	Усечено
Рубин	`%`, `modulo()`	Да	Да	Напольный
Рубин	`remainder()`	Да	Да	Усечено
Ржавчина	`%`	Да	Да	Усечено
Ржавчина	`rem_euclid()`	Да	Да	евклидов ^[49]
САС	`MOD`	Да	Нет	Усечено
Скала	`%`	Да	Да	Усечено
Схема	`modulo`	Да	Нет	Напольный
Схема	`remainder`	Да	Нет	Усечено
Схема Р ⁶РС	`mod`	Да	Нет	евклидов ^[50]
	`mod0`	Да	Нет	Закругленный ^[50]
	`flmod`	Нет	Да	евклидов
	`flmod0`	Нет	Да	Закругленный
Царапать	`mod`	Да	Да	Напольный
Сид7	`mod`	Да	Да	Напольный
Сид7	`rem`	Да	Да	Усечено
SenseTalk	`modulo`	Да	Нет	Напольный
SenseTalk	`rem`	Да	Нет	Усечено
`sh` (POSIX) (включая bash , mksh и т. д.)	`%`	Да	Нет	Усеченный (так же, как C) ^[51]
Болтовня	`\\`	Да	Нет	Напольный
Болтовня	`rem:`	Да	Нет	Усечено
Щелчок!	`mod`	Да	Нет	Напольный
Вращаться	`//`	Да	Нет	Напольный
Солидность	`%`	Да	Нет	Напольный
SQL ( SQL:1999 )	`mod(x,y)`	Да	Нет	Усечено
SQL ( SQL:2011 )	`%`	Да	Нет	Усечено
Стандартный ML	`mod`	Да	Нет	Напольный
	`Int.rem`	Да	Нет	Усечено
	`Real.rem`	Нет	Да	Усечено
Был	`mod(x,y)`	Да	Нет	евклидов
Быстрый	`%`	Да	Нет	Усечено ^[52]
	`remainder(dividingBy:)`	Нет	Да	Закругленный ^[53]
	`truncatingRemainder(dividingBy:)`	Нет	Да	Усечено ^[54]
Ткл	`%`	Да	Нет	Напольный
Ткл	`fmod()`	Нет	Да	Усечено (как C)
ткш	`%`	Да	Нет	Усечено
Крутящий момент	`%`	Да	Нет	Усечено
Тьюринг	`mod`	Да	Нет	Напольный
Верилог (2001)	`%`	Да	Нет	Усечено
VHDL	`mod`	Да	Нет	Напольный
VHDL	`rem`	Да	Нет	Усечено
ВимЛ	`%`	Да	Нет	Усечено
Visual Basic	`Mod`	Да	Нет	Усечено
Веб-сборка	`i32.rem_u`, `i64.rem_u` (без подписи)	Да	Нет	— ^[55]
Веб-сборка	`i32.rem_s`, `i64.rem_s` (подпись)	Да	Нет	Усечено ^[55]
сборка х86	`IDIV`	Да	Нет	Усечено
XBase++	`%`	Да	Да	Усечено
XBase++	`Mod()`	Да	Да	Напольный
Зиг	`%`, `@mod`, `@rem`	Да	Да	Усечено ^[56]
Средство доказательства теорем Z3	`div`, `mod`	Да	Нет	евклидов

Кроме того, многие компьютерные системы предоставляют divmodфункциональность, которая производит частное и остаток одновременно. Примеры включают архитектуру x86 . IDIV инструкция, язык программирования C div() и Python функция divmod() функция.

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

По модулю со смещением [ править ]

Иногда полезно, чтобы результат по $n$ модулю $находился$ не между 0 и $n - 1$ , а между некоторым числом $d$ и $d + n - 1$ . В этом случае $d$ называется смещением , и $d = 1$ встречается особенно часто.

что для этой операции не существует стандартной записи, поэтому давайте условно воспользуемся $модом Похоже , d n$ . Таким образом, мы имеем следующее определение: ^[57] $x = a mod d n$ только в том случае, если $d \leq x \leq d + n - 1$ и $x mod n = a mod n$ . Очевидно, что обычная операция по модулю соответствует смещению нуля: $a mod n = a mod 0 n$ .

Операция по модулю со смещением связана с функцией пола следующим образом:

a\operatorname {mod} _{d}n=a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor .

Чтобы увидеть это, позвольте ${\textstyle x=a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor }$ . Сначала мы покажем, $x mod n = mod что n$ . В общем случае верно, что $(a + bn) mod n = a mod n$ для всех целых чисел $b$ ; таким образом, это верно и в том частном случае, когда ${\textstyle b=-\!\left\lfloor {\frac {a-d}{n}}\right\rfloor }$ ; но это значит, что ${\textstyle x{\bmod {n}}=\left(a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor \right)\!{\bmod {n}}=a{\bmod {n}}}$ , что мы и хотели доказать. Осталось показать, что $d \leq x \leq d + n - 1$ . Пусть $k$ и $r$ — целые числа такие, что $a - d = kn + r$ , $0 \leq r \leq n - 1$ (см. евклидово деление ). Затем ${\textstyle \left\lfloor {\frac {a-d}{n}}\right\rfloor =k}$ , таким образом ${\textstyle x=a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor =a-nk=d+r}$ . Теперь возьмем $0 \leq r \leq n - 1$ и прибавим $d$ к обеим частям, получив $d \leq d + r \leq d + n - 1$ . Но мы видели, что $x = d + r$ , так что мы закончили.

Модуль со смещением $a mod d n$ реализован в системе Mathematica как Mod[a, n, d] . ^[57]

Реализация других определений по модулю с использованием усечения [ править ]

Несмотря на математическую элегантность напольного деления Кнута и евклидова деления, в языках программирования гораздо чаще можно встретить усеченное деление по модулю, основанное на делении. Лейен предоставляет следующие алгоритмы для вычисления двух делений с учетом усеченного целочисленного деления: ^[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  ,   .   рем   =   р  }; 
  }

В обоих случаях остаток можно вычислить независимо от частного, но не наоборот. Здесь операции объединены для экономии места на экране, поскольку логические ветви одинаковы.

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

По модулю (значения) - множество вариантов использования слова по модулю , все из которых возникли из Карлом Ф. Гауссом введения модульной арифметики в 1801 году.
По модулю (математика) , общее использование термина в математике.
Модульное возведение в степень
Поворот (угол)

Примечания [ править ]

^ Математически эти два варианта — всего лишь два из бесконечного числа вариантов, доступных для неравенства, удовлетворяемого остатком .
^ Перейти обратно: ^а ^б Порядок аргументов меняется на обратный, т.е. α|ω вычисляет $\omega {\bmod {\alpha }}$ , остаток при делении ω к α.
^ C99 и C++11 определяют поведение % быть усеченным. ^[9] Стандарты до этого оставляют поведение определяемым реализацией. ^[10]
^ Делитель должен быть положительным, иначе не определен.
^ Как обсуждал Буте, определения ISO Pascal div и mod не подчиняются тождеству деления $D = d \cdot (D / d) + D % d$ и, таким образом, фундаментально нарушены.
^ Perl обычно использует арифметический оператор по модулю, который не зависит от машины. Примеры и исключения см. в документации Perl по мультипликативным операторам. ^[43]

Ссылки [ править ]

^ Вайсштейн, Эрик В. «Конгруэнтность» . Вольфрам Математический мир . Проверено 27 августа 2020 г.
^ Колдуэлл, Крис. «осадок» . Главный глоссарий . Проверено 27 августа 2020 г.
^ Кнут, Дональд. Э. (1972). Искусство компьютерного программирования . Аддисон-Уэсли.
^ Бут, Раймонд Т. (апрель 1992 г.). «Евклидово определение функций div и mod» . Транзакции ACM в языках и системах программирования . 14 (2). ACM Press (Нью-Йорк, штат Нью-Йорк, США): 127–144. дои : 10.1145/128861.128862 . hdl : 1854/LU-314490 . S2CID 8321674 .
^ Перейти обратно: ^а ^б Лейен, Даан (3 декабря 2001 г.). «Деление и модуль для компьютерщиков» (PDF) . Проверено 25 декабря 2014 г.
^ Петерсон, доктор (5 июля 2001 г.). «Функция Mod и отрицательные числа» . Математический форум — спросите доктора Математика . Архивировано из оригинала 22 октября 2019 г. Проверено 22 октября 2019 г.
^ Хорват, Адам (5 июля 2012 г.). «Быстрое деление и операция по модулю — сила двух» .
^ Перейти обратно: ^а ^б ISO/IEC 8652:2012 — Информационные технологии. Языки программирования. Ада . ИСО , МЭК . 2012. сек. 4.5.5 Операторы умножения.
^ «Спецификация C99 (ISO/IEC 9899:TC2)» (PDF) . 06 мая 2005 г. сек. 6.5.5 Мультипликативные операторы . Проверено 16 августа 2018 г.
^ ISO/IEC 14882:2003: Языки программирования – C++ . Международная организация по стандартизации (ISO), Международная электротехническая комиссия (IEC). 2003. сек. 5.6.4. бинарный оператор % возвращает остаток от деления первого выражения на второе. .... Если оба операнда неотрицательны, то остаток неотрицательен; если нет, то знак остатка определяется реализацией
^ ISO/IEC 9899:1990: Языки программирования – C. ИСО , МЭК . 1990. сек. 7.5.6.4. Функция $fmod$ возвращает значение $x - i * y$ для некоторого целого числа $i$ , такого, что, если $y$ не равно нулю, результат имеет тот же знак, что и $x$ , и величину меньше, чем величина $y$ .
^ Перейти обратно: ^а ^б дотнет-бот. «Метод Math.IEEERemainder(Double, Double) (Система)» . Microsoft Learn . Проверено 4 октября 2022 г.
^ «clojure.core — Документация по API Clojure v1.10.3» . Clojure.github.io . Проверено 16 марта 2022 г.
^ «clojure.core — Документация по API Clojure v1.10.3» . Clojure.github.io . Проверено 16 марта 2022 г.
^ Перейти обратно: ^а ^б ISO/IEC JTC 1/SC 22/WG 4 (январь 2023 г.). ISO/IEC 1989:2023 – Язык программирования COBOL . ИСО {{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка )
^ Операторы CoffeeScript
^ ISO/IEC JTC 1/SC 22 (февраль 2012 г.). ISO/IEC 23271:2012 — Информационные технологии. Общеязыковая инфраструктура (CLI) . ИСО §§ III.3.55–56. {{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка )
^ «Выражения — язык программирования D» . dlang.org . Проверено 1 июня 2021 г.
^ «метод оператора % — номер класса — dart:core Library — Dart API» . api.dart.dev . Проверено 1 июня 2021 г.
^ «метод остатка — номер класса — библиотека dart:core — API Dart» . api.dart.dev . Проверено 1 июня 2021 г.
^ «Ядро — Эликсир v1.11.3» . hexdocs.pm . Проверено 28 января 2021 г.
^ «Целое число — Эликсир v1.11.3» . hexdocs.pm . Проверено 28 января 2021 г.
^ «Основы — ядро 1.0.5» . package.elm-lang.org . Проверено 16 марта 2022 г.
^ «Основы — ядро 1.0.5» . package.elm-lang.org . Проверено 16 марта 2022 г.
^ «Эрланг — математика» . erlang.org . Проверено 1 июня 2021 г.
^ АНСИ (28 января 1987 г.). Языки программирования — Полный БЕЙСИК . Нью-Йорк: Американский национальный институт стандартов. § 5.4.4. X по модулю Y, т.е. XY*INT(X/Y).
^ АНСИ (28 января 1987 г.). Языки программирования — Полный БЕЙСИК . Нью-Йорк: Американский национальный институт стандартов. § 5.4.4. Функция остатка, т.е. XY*IP(X/Y).
^ «Спецификация языка GLSL, версия 4.50.7» (PDF) . раздел 5.9 Выражения. Если оба операнда неотрицательны, то остаток неотрицательен. Результаты не определены, если один или оба операнда отрицательны.
^ «Спецификация языка GLSL, версия 4.50.7» (PDF) . раздел 8.3 Общие функции.
^ «Спецификация языка программирования Go — Язык программирования Go» . go.dev . Проверено 28 февраля 2022 г.
^ «математический пакет — math — pkg.go.dev» . pkg.go.dev . Проверено 28 февраля 2022 г.
^ «большой пакет — math/big — pkg.go.dev» . pkg.go.dev . Проверено 28 февраля 2022 г.
^ «большой пакет — math/big — pkg.go.dev» . pkg.go.dev . Проверено 12 апреля 2024 г.
^ Перейти обратно: ^а ^б «6 предопределенных типов и классов» . www.haskell.org . Проверено 22 мая 2022 г.
^ «Операторы» . Майкрософт . Проверено 19 июля 2021 г. Оператор % определяется только в тех случаях, когда либо обе стороны положительны, либо обе стороны отрицательны. В отличие от C, он также работает с типами данных с плавающей запятой, а также с целыми числами.
^ «Математика · Язык Джулии» . docs.julialang.org . Проверено 20 ноября 2021 г.
^ «Математика · Язык Джулии» . docs.julialang.org . Проверено 20 ноября 2021 г.
^ «rem — язык программирования Kotlin» . Котлин . Проверено 5 мая 2021 г.
^ «мод — язык программирования Котлин» . Котлин . Проверено 5 мая 2021 г.
^ «Глава 3: Язык NASM» . NASM — Netwide Assembler версии 2.15.05 .
^ «Библиотека OCaml: Stdlib» . ocaml.org . Проверено 19 февраля 2022 г.
^ «Библиотека OCaml: Stdlib» . ocaml.org . Проверено 19 февраля 2022 г.
^ Документация Perl
^ «PHP: Арифметические операторы — Руководство» . www.php.net . Проверено 20 ноября 2021 г.
^ «PHP: fmod — Руководство» . www.php.net . Проверено 20 ноября 2021 г.
^ «Евклидово кольцо» .
^ КвантумПисатель. «Выражения» . docs.microsoft.com . Проверено 11 июля 2018 г.
^ «R: Арифметические операторы» . search.r-project.org . Проверено 24 декабря 2022 г.
^ «F32 — Ржавчина» .
^ Перейти обратно: ^а ^б r6rs.org
^ «Язык команд оболочки» . pubs.opengroup.org . Проверено 5 февраля 2021 г.
^ «Документация разработчика Apple» . разработчик.apple.com . Проверено 20 ноября 2021 г.
^ «Документация разработчика Apple» . разработчик.apple.com . Проверено 20 ноября 2021 г.
^ «Документация разработчика Apple» . разработчик.apple.com . Проверено 20 ноября 2021 г.
^ Перейти обратно: ^а ^б Россберг, Андреас, изд. (19 апреля 2022 г.). «Основная спецификация WebAssembly: версия 2.0» . Консорциум Всемирной паутины . § 4.3.2 Целочисленные операции.
^ «Зиг-документация» . Язык программирования Zig . Проверено 18 декабря 2022 г.
^ Перейти обратно: ^а ^б «Мод» . Центр документации по языкам и системам Wolfram . Вольфрам Исследования . 2020 . Проверено 8 апреля 2020 г.

Внешние ссылки [ править ]

Различные виды целочисленного деления
Модулорама , анимация циклического представления таблицы умножения (объяснение на французском языке)

[3] Математически эти два варианта — всего лишь два из бесконечного числа вариантов, доступных для неравенства, удовлетворяемого остатком .

[rev-10] Перейти обратно: ^а ^б Порядок аргументов меняется на обратный, т.е. α|ω вычисляет $\omega {\bmod {\alpha }}$ , остаток при делении ω к α.

[c-13] C99 и C++11 определяют поведение % быть усеченным. ^[9] Стандарты до этого оставляют поведение определяемым реализацией. ^[10]

[44] Делитель должен быть положительным, иначе не определен.

[47] Как обсуждал Буте, определения ISO Pascal div и mod не подчиняются тождеству деления $D = d \cdot (D / d) + D % d$ и, таким образом, фундаментально нарушены.

[49] Perl обычно использует арифметический оператор по модулю, который не зависит от машины. Примеры и исключения см. в документации Perl по мультипликативным операторам. ^[43]

[1] Вайсштейн, Эрик В. «Конгруэнтность» . Вольфрам Математический мир . Проверено 27 августа 2020 г.

[2] Колдуэлл, Крис. «осадок» . Главный глоссарий . Проверено 27 августа 2020 г.

[4] Кнут, Дональд. Э. (1972). Искусство компьютерного программирования . Аддисон-Уэсли.

[5] Бут, Раймонд Т. (апрель 1992 г.). «Евклидово определение функций div и mod» . Транзакции ACM в языках и системах программирования . 14 (2). ACM Press (Нью-Йорк, штат Нью-Йорк, США): 127–144. дои : 10.1145/128861.128862 . hdl : 1854/LU-314490 . S2CID 8321674 .

[Leijen-6] Перейти обратно: ^а ^б Лейен, Даан (3 декабря 2001 г.). «Деление и модуль для компьютерщиков» (PDF) . Проверено 25 декабря 2014 г.

[7] Петерсон, доктор (5 июля 2001 г.). «Функция Mod и отрицательные числа» . Математический форум — спросите доктора Математика . Архивировано из оригинала 22 октября 2019 г. Проверено 22 октября 2019 г.

[8] Хорват, Адам (5 июля 2012 г.). «Быстрое деление и операция по модулю — сила двух» .

[Ada-9] Перейти обратно: ^а ^б ISO/IEC 8652:2012 — Информационные технологии. Языки программирования. Ада . ИСО , МЭК . 2012. сек. 4.5.5 Операторы умножения.

[C99-11] «Спецификация C99 (ISO/IEC 9899:TC2)» (PDF) . 06 мая 2005 г. сек. 6.5.5 Мультипликативные операторы . Проверено 16 августа 2018 г.

[12] ISO/IEC 14882:2003: Языки программирования – C++ . Международная организация по стандартизации (ISO), Международная электротехническая комиссия (IEC). 2003. сек. 5.6.4. бинарный оператор % возвращает остаток от деления первого выражения на второе. .... Если оба операнда неотрицательны, то остаток неотрицательен; если нет, то знак остатка определяется реализацией

[14] ISO/IEC 9899:1990: Языки программирования – C. ИСО , МЭК . 1990. сек. 7.5.6.4. Функция $fmod$ возвращает значение $x - i * y$ для некоторого целого числа $i$ , такого, что, если $y$ не равно нулю, результат имеет тот же знак, что и $x$ , и величину меньше, чем величина $y$ .

[.NET-15] Перейти обратно: ^а ^б дотнет-бот. «Метод Math.IEEERemainder(Double, Double) (Система)» . Microsoft Learn . Проверено 4 октября 2022 г.

[16] «clojure.core — Документация по API Clojure v1.10.3» . Clojure.github.io . Проверено 16 марта 2022 г.

[17] «clojure.core — Документация по API Clojure v1.10.3» . Clojure.github.io . Проверено 16 марта 2022 г.

[isocobol-18] Перейти обратно: ^а ^б ISO/IEC JTC 1/SC 22/WG 4 (январь 2023 г.). ISO/IEC 1989:2023 – Язык программирования COBOL . ИСО {{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка )

[CoffeeScript-19] Операторы CoffeeScript

[20] ISO/IEC JTC 1/SC 22 (февраль 2012 г.). ISO/IEC 23271:2012 — Информационные технологии. Общеязыковая инфраструктура (CLI) . ИСО §§ III.3.55–56. {{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка )

[21] «Выражения — язык программирования D» . dlang.org . Проверено 1 июня 2021 г.

[22] «метод оператора % — номер класса — dart:core Library — Dart API» . api.dart.dev . Проверено 1 июня 2021 г.

[23] «метод остатка — номер класса — библиотека dart:core — API Dart» . api.dart.dev . Проверено 1 июня 2021 г.

[24] «Ядро — Эликсир v1.11.3» . hexdocs.pm . Проверено 28 января 2021 г.

[25] «Целое число — Эликсир v1.11.3» . hexdocs.pm . Проверено 28 января 2021 г.

[26] «Основы — ядро 1.0.5» . package.elm-lang.org . Проверено 16 марта 2022 г.

[27] «Основы — ядро 1.0.5» . package.elm-lang.org . Проверено 16 марта 2022 г.

[28] «Эрланг — математика» . erlang.org . Проверено 1 июня 2021 г.

[29] АНСИ (28 января 1987 г.). Языки программирования — Полный БЕЙСИК . Нью-Йорк: Американский национальный институт стандартов. § 5.4.4. X по модулю Y, т.е. XY*INT(X/Y).

[30] АНСИ (28 января 1987 г.). Языки программирования — Полный БЕЙСИК . Нью-Йорк: Американский национальный институт стандартов. § 5.4.4. Функция остатка, т.е. XY*IP(X/Y).

[31] «Спецификация языка GLSL, версия 4.50.7» (PDF) . раздел 5.9 Выражения. Если оба операнда неотрицательны, то остаток неотрицательен. Результаты не определены, если один или оба операнда отрицательны.

[32] «Спецификация языка GLSL, версия 4.50.7» (PDF) . раздел 8.3 Общие функции.

[33] «Спецификация языка программирования Go — Язык программирования Go» . go.dev . Проверено 28 февраля 2022 г.

[34] «математический пакет — math — pkg.go.dev» . pkg.go.dev . Проверено 28 февраля 2022 г.

[35] «большой пакет — math/big — pkg.go.dev» . pkg.go.dev . Проверено 28 февраля 2022 г.

[36] «большой пакет — math/big — pkg.go.dev» . pkg.go.dev . Проверено 12 апреля 2024 г.

[Haskell_2010-37] Перейти обратно: ^а ^б «6 предопределенных типов и классов» . www.haskell.org . Проверено 22 мая 2022 г.

[38] «Операторы» . Майкрософт . Проверено 19 июля 2021 г. Оператор % определяется только в тех случаях, когда либо обе стороны положительны, либо обе стороны отрицательны. В отличие от C, он также работает с типами данных с плавающей запятой, а также с целыми числами.

[39] «Математика · Язык Джулии» . docs.julialang.org . Проверено 20 ноября 2021 г.

[40] «Математика · Язык Джулии» . docs.julialang.org . Проверено 20 ноября 2021 г.

[41] «rem — язык программирования Kotlin» . Котлин . Проверено 5 мая 2021 г.

[42] «мод — язык программирования Котлин» . Котлин . Проверено 5 мая 2021 г.

[43] «Глава 3: Язык NASM» . NASM — Netwide Assembler версии 2.15.05 .

[45] «Библиотека OCaml: Stdlib» . ocaml.org . Проверено 19 февраля 2022 г.

[46] «Библиотека OCaml: Stdlib» . ocaml.org . Проверено 19 февраля 2022 г.

[48] Документация Perl

[50] «PHP: Арифметические операторы — Руководство» . www.php.net . Проверено 20 ноября 2021 г.

[51] «PHP: fmod — Руководство» . www.php.net . Проверено 20 ноября 2021 г.

[purescript_euclid-52] «Евклидово кольцо» .

[53] КвантумПисатель. «Выражения» . docs.microsoft.com . Проверено 11 июля 2018 г.

[54] «R: Арифметические операторы» . search.r-project.org . Проверено 24 декабря 2022 г.

[rust_rem_euclid-55] «F32 — Ржавчина» .

[r6rs-56] Перейти обратно: ^а ^б r6rs.org

[57] «Язык команд оболочки» . pubs.opengroup.org . Проверено 5 февраля 2021 г.

[58] «Документация разработчика Apple» . разработчик.apple.com . Проверено 20 ноября 2021 г.

[59] «Документация разработчика Apple» . разработчик.apple.com . Проверено 20 ноября 2021 г.

[60] «Документация разработчика Apple» . разработчик.apple.com . Проверено 20 ноября 2021 г.

[wasmcs2-61] Перейти обратно: ^а ^б Россберг, Андреас, изд. (19 апреля 2022 г.). «Основная спецификация WebAssembly: версия 2.0» . Консорциум Всемирной паутины . § 4.3.2 Целочисленные операции.

[62] «Зиг-документация» . Язык программирования Zig . Проверено 18 декабря 2022 г.

[Mathematica_Mod-63] Перейти обратно: ^а ^б «Мод» . Центр документации по языкам и системам Wolfram . Вольфрам Исследования . 2020 . Проверено 8 апреля 2020 г.

[1]

[2]

[а]

[3]

[4]

[5]

[6]

[7]

[8]

[б]

[с]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[д]

[41]

[42]

[Это]

[ф]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[9]

[10]

[43]