по модулю

Вычислительная операция

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

Учитывая два положительных числа 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 не определен в большинстве систем, хотя некоторые определяют его как .

• 

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

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

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

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

  ${\displaystyle r=a-n\operatorname {trunc} \left({\frac {a}{n}}\right)}$

• 

  Частное и остаток с использованием напольного деления

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

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

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

  ${\displaystyle r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor }$

• 

  Частное и остаток с использованием евклидова деления

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

  ${\displaystyle 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 ), остаток неотрицательен :

  ${\displaystyle r=a-|n|\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor }$

• 

  Частное и остаток с использованием округленного деления

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

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

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

  ${\displaystyle r=a-n\operatorname {round} \left({\frac {a}{n}}\right)}$

• 

  Частное и остаток с использованием потолочного деления

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

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

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

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

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

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

Баут утверждает, что евклидово деление превосходит другие с точки зрения регулярности и полезных математических свойств, хотя напольное деление, предложенное Кнутом, также является хорошим определением. Несмотря на широкое использование, усеченное деление уступает другим определениям.

-  Даан Лейен, Деление и модуль для компьютерщиков ^[5]

Однако усеченное деление удовлетворяет тождеству . ^[6] ${\displaystyle ({-a})/b={-(a/b)}=a/({-b})}$

Обозначения

В некоторых калькуляторах есть функциональная кнопка 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 были целыми числами.

• Личность:
  • ( мод п ) мод п = мод п . _
  • n ^x mod n = 0 для всех положительных целых значений x .
  • Если p — простое число , которое не является делителем b , то ab p ^{− 1} mod p = a mod p согласно малой теореме Ферма .
• Обратный:
  • [(− a mod n ) + ( a mod n )] mod n знак равно 0 .
  • b ⁻¹ mod n обозначает модульную мультипликативную обратную величину , которая определяется тогда и только тогда, когда b и n взаимно просты ,что имеет место, когда определена левая часть: [( b ⁻¹ mod n )( b 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 .
• Подразделение (определение): а/бmod n = [( a mod n )( b ⁻¹ mod n )] mod n , когда определена правая часть (то есть, когда b и n взаимно просты ), и неопределена в противном случае.
• Обратное умножение: [( ab mod n )( b ⁻¹ mod n )] mod n = a mod 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 ₀ n .

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

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

Чтобы увидеть это, позвольте . Сначала мы покажем, что 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 , так что мы закончили. ${\textstyle x=a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor }$ ${\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}}}$ ${\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}$

Модуль со смещением 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 , . рем = р }; }                                                     

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

Смотрите также

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

Примечания

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

Рекомендации

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

Внешние ссылки

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