Операция по модулю

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

Учитывая два положительных числа a и n , по модулю n (сокращенно по модулю n ) является остаток от евклидова деления числа a на n , где a - делимое, а n - делитель . ^[1] Операцию по модулю следует отличать от символа mod , который относится к модулю ^[2] (или делителю), с которым работает.

Например, выражение «5 mod 2» будет оцениваться как 1, потому что 5, разделенное на 2, дает частное 2, а остаток - 1, тогда как «9 mod 3» будет оцениваться как 0, потому что деление 9 на 3 дает частное 3 и остаток 0; после умножения 3 на 3 из 9 нечего вычитать.

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

Хотя обычно они выполняются с целыми числами a и n , многие вычислительные системы теперь позволяют использовать другие типы числовых операндов. Диапазон чисел для целого числа по модулю из п равно от 0 до п - 1 включительно ( мод 1 всегда 0; мод 0 не определено, возможно , в результате чего деление на ноль ошибок в некоторых языках программирования). См. Модульную арифметику для более старого и связанного с ним соглашения, применяемого в теории чисел .

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

Варианты определения [ править ]

В математике результатом операции по модулю является класс эквивалентности , и любой член этого класса может быть выбран в качестве представителя; однако обычным представителем является наименьший положительный остаток , наименьшее неотрицательное целое число, которое принадлежит этому классу (то есть остаток от евклидова деления ). ^[3] Однако возможны и другие соглашения. Компьютеры и калькуляторы имеют различные способы хранения и представления чисел; таким образом, их определение операции по модулю зависит от языка программирования или базового оборудования .

Почти во всех вычислительных системах частное q и остаток r от деления a на n удовлетворяют следующим условиям:

${\ displaystyle {\ begin {align} q \, & \ in \ mathbb {Z} \\ a \, & = nq + r \\ | r | \, & <| n | \ end {align}}}$

( 1 )

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

По словам Лейена,

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

-  Даан Лейен, Отдел и модуль для компьютерных ученых ^[6]

Однако усеченное деление удовлетворяет тождеству . ^[7]${\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 ; }

Но на языке, где modulo имеет знак делимого, это неверно, потому что, когда n (делимое) является отрицательным и нечетным, n mod 2 возвращает -1, а функция возвращает false.

Одна из правильных альтернатив - проверить, что остаток не равен 0 (потому что остаток 0 одинаков независимо от знаков):

bool  is_odd ( int  n )  {  вернуть  n  %  2  ! =  0 ; }

Другой альтернативой является использование того факта, что для любого нечетного числа остаток может быть либо 1, либо -1:

bool  is_odd ( int  n )  {  return  n  %  2  ==  1  ||  п  %  2  ==  -1 ; }

Проблемы с производительностью [ править ]

Операции по модулю могут быть реализованы так, что деление с остатком вычисляется каждый раз. Для особых случаев на некотором оборудовании существуют более быстрые альтернативы. Например, модуль степеней двойки может быть альтернативно выражен как побитовая операция И (при условии, что x является положительным целым числом, или с использованием определения без усечения):

x % 2n == x & (2n - 1)

Примеры:

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

В устройствах и программном обеспечении, которые реализуют побитовые операции более эффективно, чем по модулю, эти альтернативные формы могут привести к более быстрым вычислениям. ^[8]

Оптимизация компилятора может распознавать выражения формы, expression % constantгде constant- степень двойки, и автоматически реализовывать их как expression & (constant-1), позволяя программисту писать более четкий код без ущерба для производительности. Эта простая оптимизация невозможна для языков, в которых результат операции по модулю имеет знак делимого (включая C), за исключением случаев, когда делимое имеет целочисленный тип без знака . Это потому, что, если дивиденд отрицательный, модуль будет отрицательным, тогда как expression & (constant-1)всегда будет положительным. Для этих языков вместо этого следует использовать эквивалентность , выраженную с помощью побитовых операций ИЛИ, НЕ и И.x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)

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

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

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

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

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

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

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

Иногда бывает полезно для результата в по модулю п лежать не между 0 и п -1 , а между некоторым числом д и д + п -1 . В этом случае d называется смещением. Там , кажется, не являются стандартным обозначением для этой операции, так что давайте предварительно использовать в модах _д н . Таким образом, мы имеем следующее определение: ^[22] 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 = a mod n . В целом верно, что ( a + bn ) mod n = a mod n для всех целых чисел b ; таким образом, это верно также в частный случай, когда ; но это означает , что это то, что мы хотели доказать. Осталось показать, что d ≤ x ≤ d + n −1 . Пусть k и r - целые числа такие, что a -${\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}}}$d = kn + r, где 0 ≤ r ≤ n −1 (см. евклидово деление ). Тогдатак. Теперь возьмем 0 ≤ r ≤ n −1 и прибавим d к обеим сторонам, получив d ≤ d + r ≤ d + n −1 . Но мы видели, что x = d + r , поэтому мы закончили. □)${\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 как ^[22] Mod[a, n, d] .

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

Несмотря на математическую элегантность напольного деления Кунта и евклидова деления, в языках программирования, как правило, гораздо чаще можно найти усеченное деление по модулю на основе деления. Лейен предлагает следующие алгоритмы для вычисления двух делений с учетом усеченного целочисленного деления: ^[6]

/ * Евклидово-напольное divmod в стиле ldiv () языка C * / typedef  struct  {  / * Эта структура является частью C stdlib.h, но воспроизведена здесь для ясности * /  long  int  quot ;  long  int  rem ; }  ldiv_t ;/ * Евклидово деление * / рядный  ldiv_t  ldivE ( долгое  Спальных ,  долго  DENOM )  {  / * The C99 и C ++ 11 языков определяют оба из них , как усечение. * /  Длинный  д  =  Numer  /  DENOM ;  длинный  г  =  Numer  %  DENOM ;  if  ( r  <  0 )  {  if  ( denom  >  0 )  {  q  =  q  -  1 ;  г  =  г +  номинал ;  }  else  {  q  =  q  +  1 ;  r  =  r  -  номинал ;  }  }  return  ( ldiv_t ) {. Quot  =  д ,  . rem  =  r }; }/ * * Сражено деление / инлайн  ldiv_t  ldivF ( длинные  Спальные ,  длинные  DENOM )  {  длинные  д  =  Numer  /  DENOM ;  длинный  г  =  Numer  %  DENOM ;  if  (( r  >  0  &&  denom  <  0 )  ||  ( r  <  0  &&  denom  >  0 ))  {  q  =  q  -  1 ;  r  = г  +  деном ;  }  return  ( ldiv_t ) {. Quot  =  д ,  . rem  =  r }; }

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

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

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

Заметки [ править ]

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

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

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