Время на прочтение
4 мин
Количество просмотров 230K
Приготовьтесь, вас ждёт крайне педантичная статья, которая вполне может спасти вас на собеседовании или сэкономить несколько часов при вылавливании бага в продакшне!
Я сейчас активно работаю над вторым сезоном «Руководства для самозванца» и пишу о шифре RSA для SSH, который, очевидно, является самым загружаемым фрагментом кода в истории IT.
Хочется полностью разобраться в этой истории. Кто придумал этот шифр, как он работает, почему работает и будет ли работать в будущем. Сейчас я раскопал одну чертовски интересную историю. Я не криптоманьяк и вижу, как других буквально засасывает в эту область. Но мне это тоже интересно, потому что повсюду есть маленькие норки, а меня как сороку привлекают блестящие штучки в глубоких норках. Я также очень хорош в метафорах.
В любом случае: на прошлой неделе я узнал что-то странное и хочу поделиться: оказывается, mod и остаток от деления — не одно и то же. Действительно забавно то, что некоторые читатели при этих словах выпрыгивают со своих кресел и орут: «А ведь именно это я всегда пытался сказать вам и всем остальным!»
Позовите ребят из секты «mod не остаток»! Это для вас.
Что такое mod?
Я должен был изучить это, как и в прошлый раз, когда всплыла такая тема. Это одна из тех вещей, которые ты знаешь, но не запоминаешь. Когда вы применяете mod, то делите одно число на другое и берёте остаток. Итак: 5 mod 2 будет 1, потому что 5/2=2 с остатком 1.
Термин mod означает операцию modulo, с модулем 2 в данном случае. Большинство языков программирования используют %
для обозначения такой операции: 5 % 2 = 1
.
Вот где мы попадаем в странную серую область.
Математика циферблата
Помню, как учил это в школе, а потом забыл. Существует тип математики, называемый «модульной арифметикой», которая имеет дело с циклическими структурами. Самый простой способ представить это — циферблат с циклом 12. Для математика циферблат — это mod 12
. Если хотите понять, можно ли равномерно разделить 253 часа на дни, то можете применить операцию 253 mod 24
, результатом будет 13, поэтому ответ «нет»! Мы можем ответить «да» только если результат 0.
Другой вопрос, который вы можете задать: «Если я выеду в 6 вечера, сколько времени будет по приезду через 16 часов?». Это будет 6 + 16 mod 12
, то есть 10.
Криптографы любят mod
, потому что при использовании с действительно большими числами можно создать нечто, известное как «односторонние функции». Это специальные функции, которые позволяют легко вычислить что-то в одном направлении, но не в обратном.
Если я скажу вам, что 9 является результатом возведения в квадрат, вы можете легко определить, что на входе было 3. Перед вами весь процесс от начала до конца. Если я скажу, что 9 является результатом mod 29
, то будет сложнее понять, что на входе.
Криптографам нравится эта идея, потому что они могут использовать деление с остатком с гигантскими простыми числами для генерации криптографических ключей. Это совсем другая история: если хотите прочитать об этом, то можете купить книгу или, ещё лучше, поддержать мои усилия написать её.
Впрочем, не будем отклоняться от темы.
Остатки и математика циферблата
Теперь переходим к сути: modulo и простой остаток одинаковы, когда числа положительны, но отличаются в случае отрицательных чисел.
Рассмотрим такую задачу:
const x = 19 % 12;
console.log(x);
Каково значение x
? Делим числа и получаем 7 как остаток от 12. Это верный ответ. Как насчет такого:
const y = 19 % -12;
console.log(y);
Используя обычную математику, мы можем умножить -12 на -1, что даёт 12, и у нас по-прежнему остаётся 7, поэтому наш ответ снова 7.
JavaScript с этим согласен:
C# тоже согласен:
Google согласен с первым утверждением, но не согласен со вторым:
Ruby согласен с Google:
Во имя Дейкстры, что здесь происходит?
Вращение часов назад
Чтобы ответить на вопрос, следует понять разницу между остатком и modulo. Программисты объединяют эти операции, но не должны этого делать, потому что они дают одинаковый результат только в случае, если делитель (в нашем случае 12) положителен. Вы можете легко отправить баги в продакшн, если делитель отрицательный.
Но почему существует разница? Рассмотрим положительный делитель 19 mod 12
на часах:
Конечный результат 7. Мы это знаем и мы можем доказать математически. Но что насчёт 19 mod -12
? Здесь нужно использовать другие часы:
Модуль равен -12, и мы не можем игнорировать или изменить его, умножив на -1, поскольку модульная арифметика так не работает. Единственный способ правильно рассчитать результат — переставить метки на часах так, чтобы мы двигались от -12 или вращали часы против часовой стрелки, что даёт тот же результат.
Почему не начать метки с -1, двигаясь к -2, и т.д.? Потому что в таком случае мы будем двигаться назад и постоянно уменьшать результат, пока не достигнем -12, и в этот момент сделаем прыжок +12, а modulo так не работает.
Это известная вещь
Прежде чем назвать меня сумасшедшим и начать гуглить тему: это известный факт. На самом деле MDN (Mozilla Developer Network) даже дошла до того, чтобы назвать %
операцией «остатка» (remainder), а не modulo:
Оператор remainder возвращает остаток от деления одного операнда на другой. Он всегда принимает знак делимого.
Вот что Эрик Липперт, один из богов C#, говорит о modulo в C#:
Однако это совсем не то, что оператор % реально делает в C#. Оператор % не является каноническим оператором modulus, это оператор остатка.
А как на вашем языке?
Ну и что?
Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:
- Я представляю, как этот вопрос займёт меня врасплох на собеседовании.
- Я представляю, как этот попадёт в продакшн, а разработчики будут несколько часов выяснять, почему математика не работает.
Это также забавный факт на случай, если рядом появится ваш педантичный друг-программист.
в методичке по криптографии постоянно встречаются формулы вида этой:
Что такое mod? Простой остаток от деления e^-1 на p-1?
Судя по всему нет, т.к. вот пример из той же методички:
d = e^-1 (mod p-1) = 42239^-1 (mod(52631-1) = 32229
Как это считается?
p.s. Да, математика в институте была >5 лет назад, и она вовсе не мой конек.
Re: [математикам]что такое mod?
а вроде всегда это был остаток от деления. число, не превосходящее делитель.
Re: [математикам]что такое mod?
если по простому, то это как будто «зацикленное» отнимание. т.е. какое останется число k, если от числа n отнять число m максимум полных раз.
например. 11 mod 3 = 2. число 11 это 3+3+3+2. результат — 2. 61 mod 26 = 9. 61 это 26+26+9.
//читаю лекции по криптографии у людей с большими провалами в математике, даже поля Галуа и теорему Ейлера можно объяснить на пальцах, ящитаю
Re: [математикам]что такое mod?
про (mod p-1) уже сказали, но
> d = e^-1 (mod p-1) = 42239^-1 (mod(52631-1) = 32229
либо очепятка, либо ошибка:
a^=b(mod c) если a*b=1(mod c), но у тут
Re: [математикам]что такое mod?
кури теорию чисел
Re: [математикам]что такое mod?
Ужас. Закрывай методичку, открывай теорию чисел. А то что будет, когда дискретные логарифмы (ЕМНИП, ГОСТовское шифрование на них основано, но тут могу ошибаться, лет 10 криптографию не трогал) встретишь и т.д.
Re: [математикам]что такое mod?
ОМГ, так это ты подпускаешь людей без знания математики к криптографии?
Re: [математикам]что такое mod?
> //читаю лекции по криптографии у людей с большими провалами в математике, даже поля Галуа и теорему Ейлера можно объяснить на пальцах, ящитаю
Объясните на пальцах БПФ. Не что он делает, а КАК.
Ну мля, я хочу понять, как всё-таки эти формулы с интегралами в циклы расписать чтобы ему на вход массив с PCM, на выходе массив с частотами.
Re: [математикам]что такое mod?
Здесь либо порядок операций нужно смотреть, либо ограничение представления машинного числа в памяти компа. Положительное integer принимает значения от 0 до 32767. Ну, типа тогда 0-1=32767.
Re: [математикам]что такое mod?
Ну что такое остаток я понимаю, но как его найти в данном примере? Ведь e^ явно меньше чем (p-1)?
p.s. эта формула из «трехподходного протокола Шамира»
Re: [математикам]что такое mod?
>Как это считается?
Самое простое объяснение: в методичке опечатка, пропущена какая-то буква перед «-1».
Re: [математикам]что такое mod?
Второе объяснение — вопрос в том, что такое e^-1 в смысле (mod n), и как его вычислить.
Re: [математикам]что такое mod?
Это таки точно опечатка. У меня получается 34229, что слишком похоже на 32229, чтобы быть случайным.
Re: [математикам]что такое mod?
Т.е. получается: d = e^ (mod p-1) = 42239^ (mod(52631-1) = 34229
Еще раз, для малограмотных, объясните как взять остаток от деления 42239^ = 2.36748029073e-05 на 52630?
Re: [математикам]что такое mod?
>как взять остаток от деления 42239^
На самом деле mod(n), означает не остаток от деления(это только метод вычисления) а выполнение операций в соотв. кольце (или какой другой структуре — я основательно позабыл) — в котором не-целых чисел вообще нет, т.ч. e-05 там получить никак нельзя. Т.о. из определения ^-1: A^-1 (mod N) = B, такое, что A * B (mod n) = 1, следует немножко другое число. Как его вычислить и правда не знаю (:for i in range() помог:). Опыт показывает, что это 34229, т.к. *42239 mod (52630) == 1.
Оператор mod — остаток от деления. Что такое mod?
Оператор mod обозначается символом % и является оператором деления по модулю. Он возвращает остаток от деления 1-го операнда на 2-й и широко используется в разных языках программирования для решения ряда задач.
Оператор mod в Java
В Java operator mod может работать как с целыми числами (byte/int/short/long), так и с плавающей точкой (byte/int/short/long). Давайте приведём пример работы оператора mod при делении:
После выполнения этой программы вы получите результат следующего вида:
Как видим, оператор mod — это прекрасный способ найти остаток от деления. Зачем это может понадобиться на практике? Например, при нахождении кратности числа и определении, является ли некоторое число, введённое с клавиатуры, чётным. Также с помощью оператора mod можно узнать, делится ли одно число на другое без остатка или определить последнюю цифру числа. В общем, оператор mod очень полезен при решении различных задач по программированию.
Оператор mod в SQL
Не менее интересно использование mod в базах данных. Аналогично, mod находит остаток от деления. При этом вместо mod можно задействовать операцию %, делающую то же самое. Синтаксис в SQL следующий:
Но можно написать и иначе, используя % :
Давайте приведём пример использования mod в базах данных. Вот, например, таблица numbers:
Найдём остаток от деления столбца number на три:
В результате запрос SQL выберет следующие строки:
Но, как мы уже говорили выше, этот же запрос можно без проблем переписать:
Что такое mod в математике
Оператор div и оператор mod
В этой статье речь пойдет о целочисленном делении и делении с остатком.
Итак, что такое целочисленное деление вообще? В математике целочисленным делением называют такое деление, при котором одно целое число делится на другое целое число ,а результатом является целая часть их частного.
То есть например 20 / 5 = 4, 55 / 6 = 9, 100 / 3 = 33 и т.д.
Согласитесь, что в некоторых случаях это очень удобно и практично. Теперь поговорим о реализации этого метода в Паскале. Тут все достаточно просто, открывать Америку не придется. В паскале за целочисленное деление отвечает оператор div. Теперь как это записывается в Pascal’e
x — число , которое будем делить на y (делимое)
y — число , на которое будем делить число x (делитель)
z — результат целочисленного деления (целочисленное частное)
Таким образом, вот такая запись (55 / 6) нацело = 9 в результате использования оператора div будет выглядеть так
z будет равно 9. Запомните! При использовании оператора div дробная часть будет отброшена!
А сейчас поговорим о делении с остатком. Оно не особо отличается и главным здесь является то, что в результате отбрасывается как раз целая часть. То есть (40 / 6) с остатком = 4, (10 / 3) с остатком =1, (22 /5) с остатком = 2 и т.д. В паскале для этого есть оператор mod. Записывается он точно так же.
x — число , которое будем делить на y (делимое)
y — число , на которое будем делить число x (делитель)
z — остаток
Например (40 / 6) с остатком = 4 с оператором mod будет такой
И как результат получим z=1 .
Кстати оператор mod часто используют, для определения кратности чисел (кратность — это делимость на какое-нибудь число нацело. То есть например говорят, что числа 3, 6, 9, 12, 21 кратны трем. Или числа 5,10,15,20 кратны 5). В статье нахождение четных элементов массива я упоминал о числах кратных двум (четных). Итак как эту кратность определить в паскале. Обратите внимание, что если число кратное, то у него есть остаток (точнее оно имеет в остатке ноль). Этим и стоит воспользоваться.
Сейчас я привел пример условия, которое проверяет кратность, где v — это число, проверяемое на кратность по числу m. Например чтобы проверить,
является ли 40 кратным 4, используем оператор mod с условием и получим
From Wikipedia, the free encyclopedia
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the modulus of the operation).
Given two positive numbers a and n, a modulo n (often abbreviated as a mod n) is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor.[1]
For example, the expression «5 mod 2» would evaluate to 1, because 5 divided by 2 has a quotient of 2 and a remainder of 1, while «9 mod 3» would evaluate to 0, because 9 divided by 3 has a quotient of 3 and a remainder of 0; there is nothing to subtract from 9 after multiplying 3 times 3.
Although typically performed with a and n both being integers, many computing systems now allow other types of numeric operands. The range of values for an integer modulo operation of n is 0 to n − 1 inclusive (a mod 1 is always 0; a mod 0 is undefined, possibly resulting in a division by zero error in some programming languages). See Modular arithmetic for an older and related convention applied in number theory.
When exactly one of a or n is negative, the naive definition breaks down, and programming languages differ in how these values are defined.
Variants of the definition[edit]
In mathematics, the result of the modulo operation is an equivalence class, and any member of the class may be chosen as representative; however, the usual representative is the least positive residue, the smallest non-negative integer that belongs to that class (i.e., the remainder of the Euclidean division).[2] However, other conventions are possible. Computers and calculators have various ways of storing and representing numbers; thus their definition of the modulo operation depends on the programming language or the underlying hardware.
In nearly all computing systems, the quotient q and the remainder r of a divided by n satisfy the following conditions:
-
(1)
However, this still leaves a sign ambiguity if the remainder is non-zero: two possible choices for the remainder occur, one negative and the other positive, and two possible choices for the quotient occur. In number theory, the positive remainder is always chosen, but in computing, programming languages choose depending on the language and the signs of a or n.[a] Standard Pascal and ALGOL 68, for example, give a positive remainder (or 0) even for negative divisors, and some programming languages, such as C90, leave it to the implementation when either of n or a is negative (see the table under § In programming languages for details). a modulo 0 is undefined in most systems, although some do define it as a.
-
Quotient (q) and
remainder (r) as functions of dividend (a), using truncated division
Many implementations use truncated division, for which the quotient is defined by
where [] is the integral part function (rounding toward zero), i.e. the truncation to zero significant digits.
Thus according to equation (1), the remainder has the same sign as the dividend: -
Quotient and remainder using floored division
Donald Knuth[3] promotes floored division, for which the quotient is defined by
where ⌊⌋ is the floor function (rounding down).
Thus according to equation (1), the remainder has the same sign as the divisor: -
Quotient and remainder using Euclidean division
Raymond T. Boute[4] promotes Euclidean division, for which the quotient is defined by
where sgn is the sign function, ⌊⌋ is the floor function (rounding down), and ⌈⌉ is the ceiling function (rounding up).
Thus according to equation (1), the remainder is non negative: -
Quotient and remainder using rounded division
Common Lisp and IEEE 754 use rounded division, for which the quotient is defined by
where round is the round function (rounding half to even).
Thus according to equation (1), the remainder falls between and , and its sign depends on which side of zero it falls to be within these boundaries: -
Quotient and remainder using ceiling division
Common Lisp also uses ceiling division, for which the quotient is defined by
where ⌈⌉ is the ceiling function (rounding up).
Thus according to equation (1), the remainder has the opposite sign of that of the divisor:
As described by Leijen,
Boute argues that Euclidean division is superior to the other ones in terms of regularity and useful mathematical properties, although floored division, promoted by Knuth, is also a good definition. Despite its widespread use, truncated division is shown to be inferior to the other definitions.
— Daan Leijen, Division and Modulus for Computer Scientists[5]
However, truncated division satisfies the identity .[6]
Notation[edit]
This section is about the binary mod operation. For the (mod m) notation, see congruence relation.
Some calculators have a mod() function button, and many programming languages have a similar function, expressed as mod(a, n), for example. Some also support expressions that use «%», «mod», or «Mod» as a modulo or remainder operator, such as a % n
or a mod n
.
For environments lacking a similar function, any of the three definitions above can be used.
Common pitfalls[edit]
When the result of a modulo operation has the sign of the dividend (truncated definition), it can lead to surprising mistakes.
For example, to test if an integer is odd, one might be inclined to test if the remainder by 2 is equal to 1:
bool is_odd(int n) { return n % 2 == 1; }
But in a language where modulo has the sign of the dividend, that is incorrect, because when n (the dividend) is negative and odd, n mod 2 returns −1, and the function returns false.
One correct alternative is to test that the remainder is not 0 (because remainder 0 is the same regardless of the signs):
bool is_odd(int n) { return n % 2 != 0; }
Another alternative is to use the fact that for any odd number, the remainder may be either 1 or −1:
bool is_odd(int n) { return n % 2 == 1 || n % 2 == -1; }
A simpler alternative is to treat the result of n % 2 as if it is a boolean value, where any non-zero value is true:
bool is_odd(int n) { return n % 2; }
Performance issues[edit]
Modulo operations might be implemented such that a division with a remainder is calculated each time. For special cases, on some hardware, faster alternatives exist. For example, the modulo of powers of 2 can alternatively be expressed as a bitwise AND operation (assuming x is a positive integer, or using a non-truncating definition):
x % 2n == x & (2n - 1)
Examples:
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7
In devices and software that implement bitwise operations more efficiently than modulo, these alternative forms can result in faster calculations.[7]
Compiler optimizations may recognize expressions of the form expression % constant
where constant
is a power of two and automatically implement them as expression & (constant-1)
, allowing the programmer to write clearer code without compromising performance. This simple optimization is not possible for languages in which the result of the modulo operation has the sign of the dividend (including C), unless the dividend is of an unsigned integer type. This is because, if the dividend is negative, the modulo will be negative, whereas expression & (constant-1)
will always be positive. For these languages, the equivalence x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)
has to be used instead, expressed using bitwise OR, NOT and AND operations.
Optimizations for general constant-modulus operations also exist by calculating the division first using the constant-divisor optimization.
Properties (identities)[edit]
Some modulo operations can be factored or expanded similarly to other mathematical operations. This may be useful in cryptography proofs, such as the Diffie–Hellman key exchange. Some of these properties require that a and n are integers.
- Identity:
- (a mod n) mod n = a mod n.
- nx mod n = 0 for all positive integer values of x.
- If p is a prime number which is not a divisor of b, then abp−1 mod p = a mod p, due to Fermat’s little theorem.
- Inverse:
- [(−a mod n) + (a mod n)] mod n = 0.
- b−1 mod n denotes the modular multiplicative inverse, which is defined if and only if b and n are relatively prime, which is the case when the left hand side is defined: [(b−1 mod n)(b mod n)] mod n = 1.
- Distributive:
- (a + b) mod n = [(a mod n) + (b mod n)] mod n.
- ab mod n = [(a mod n)(b mod n)] mod n.
- Division (definition): a/b mod n = [(a mod n)(b−1 mod n)] mod n, when the right hand side is defined (that is when b and n are coprime), and undefined otherwise.
- Inverse multiplication: [(ab mod n)(b−1 mod n)] mod n = a mod n.
In programming languages[edit]
Language | Operator | Integer | Floating-point | Definition |
---|---|---|---|---|
ABAP | MOD
|
Yes | Yes | Euclidean |
ActionScript | %
|
Yes | No | Truncated |
Ada | mod
|
Yes | No | Floored[8] |
rem
|
Yes | No | Truncated[8] | |
ALGOL 68 | ÷× , mod
|
Yes | No | Euclidean |
AMPL | mod
|
Yes | No | Truncated |
APL | | [b]
|
Yes | No | Floored |
AppleScript | mod
|
Yes | No | Truncated |
AutoLISP | (rem d n)
|
Yes | No | Truncated |
AWK | %
|
Yes | No | Truncated |
bash | %
|
Yes | No | Truncated |
BASIC | Mod
|
Yes | No | Undefined |
bc | %
|
Yes | No | Truncated |
C C++ |
% , div
|
Yes | No | Truncated[c] |
fmod (C)std::fmod (C++)
|
No | Yes | Truncated[11] | |
remainder (C)std::remainder (C++)
|
No | Yes | Rounded | |
C# | %
|
Yes | Yes | Truncated |
Math.IEEERemainder
|
No | Yes | Rounded[12] | |
Clarion | %
|
Yes | No | Truncated |
Clean | rem
|
Yes | No | Truncated |
Clojure | mod
|
Yes | No | Floored[13] |
rem
|
Yes | No | Truncated[14] | |
COBOL | FUNCTION MOD
|
Yes | No | Floored[d] |
CoffeeScript | %
|
Yes | No | Truncated |
%%
|
Yes | No | Floored[15] | |
ColdFusion | % , MOD
|
Yes | No | Truncated |
Common Lisp | mod
|
Yes | Yes | Floored |
rem
|
Yes | Yes | Truncated | |
Crystal | % , modulo
|
Yes | Yes | Floored |
remainder
|
Yes | Yes | Truncated | |
D | %
|
Yes | Yes | Truncated[16] |
Dart | %
|
Yes | Yes | Euclidean[17] |
remainder()
|
Yes | Yes | Truncated[18] | |
Eiffel | \
|
Yes | No | Truncated |
Elixir | rem/2
|
Yes | No | Truncated[19] |
Integer.mod/2
|
Yes | No | Floored[20] | |
Elm | modBy
|
Yes | No | Floored[21] |
remainderBy
|
Yes | No | Truncated[22] | |
Erlang | rem
|
Yes | No | Truncated |
math:fmod/2
|
No | Yes | Truncated (same as C)[23] | |
Euphoria | mod
|
Yes | No | Floored |
remainder
|
Yes | No | Truncated | |
F# | %
|
Yes | Yes | Truncated |
Math.IEEERemainder
|
No | Yes | Rounded[12] | |
Factor | mod
|
Yes | No | Truncated |
FileMaker | Mod
|
Yes | No | Floored |
Forth | mod
|
Yes | No | Implementation defined |
fm/mod
|
Yes | No | Floored | |
sm/rem
|
Yes | No | Truncated | |
Fortran | mod
|
Yes | Yes | Truncated |
modulo
|
Yes | Yes | Floored | |
Frink | mod
|
Yes | No | Floored |
GLSL | %
|
Yes | No | Undefined[24] |
mod
|
No | Yes | Floored[25] | |
GameMaker Studio (GML) | mod , %
|
Yes | No | Truncated |
GDScript (Godot) | %
|
Yes | No | Truncated |
fmod
|
No | Yes | Truncated | |
posmod
|
Yes | No | Floored | |
fposmod
|
No | Yes | Floored | |
Go | %
|
Yes | No | Truncated[26] |
math.Mod
|
No | Yes | Truncated[27] | |
big.Int.Mod
|
Yes | No | Euclidean[28] | |
Groovy | %
|
Yes | No | Truncated |
Haskell | mod
|
Yes | No | Floored[29] |
rem
|
Yes | No | Truncated[29] | |
Data.Fixed.mod' (GHC)
|
No | Yes | Floored | |
Haxe | %
|
Yes | No | Truncated |
HLSL | %
|
Yes | Yes | Undefined[30] |
J | | [b]
|
Yes | No | Floored |
Java | %
|
Yes | Yes | Truncated |
Math.floorMod
|
Yes | No | Floored | |
JavaScript TypeScript |
%
|
Yes | Yes | Truncated |
Julia | mod
|
Yes | Yes | Floored[31] |
% , rem
|
Yes | Yes | Truncated[32] | |
Kotlin | % , rem
|
Yes | Yes | Truncated[33] |
mod
|
Yes | Yes | Floored[34] | |
ksh | %
|
Yes | No | Truncated (same as POSIX sh) |
fmod
|
No | Yes | Truncated | |
LabVIEW | mod
|
Yes | Yes | Truncated |
LibreOffice | =MOD()
|
Yes | No | Floored |
Logo | MODULO
|
Yes | No | Floored |
REMAINDER
|
Yes | No | Truncated | |
Lua 5 | %
|
Yes | Yes | Floored |
Lua 4 | mod(x,y)
|
Yes | Yes | Truncated |
Liberty BASIC | MOD
|
Yes | No | Truncated |
Mathcad | mod(x,y)
|
Yes | No | Floored |
Maple | e mod m (by default), modp(e, m)
|
Yes | No | Euclidean |
mods(e, m)
|
Yes | No | Rounded | |
frem(e, m)
|
Yes | Yes | Rounded | |
Mathematica | Mod[a, b]
|
Yes | No | Floored |
MATLAB | mod
|
Yes | No | Floored |
rem
|
Yes | No | Truncated | |
Maxima | mod
|
Yes | No | Floored |
remainder
|
Yes | No | Truncated | |
Maya Embedded Language | %
|
Yes | No | Truncated |
Microsoft Excel | =MOD()
|
Yes | Yes | Floored |
Minitab | MOD
|
Yes | No | Floored |
Modula-2 | MOD
|
Yes | No | Floored |
REM
|
Yes | No | Truncated | |
MUMPS | #
|
Yes | No | Floored |
Netwide Assembler (NASM, NASMX) | % , div (unsigned)
|
Yes | No | — |
%% (signed)
|
Yes | No | Implementation-defined[35] | |
Nim | mod
|
Yes | No | Truncated |
Oberon | MOD
|
Yes | No | Floored-like[e] |
Objective-C | %
|
Yes | No | Truncated (same as C99) |
Object Pascal, Delphi | mod
|
Yes | No | Truncated |
OCaml | mod
|
Yes | No | Truncated[36] |
mod_float
|
No | Yes | Truncated[37] | |
Occam |
|
Yes | No | Truncated |
Pascal (ISO-7185 and -10206) | mod
|
Yes | No | Euclidean-like[f] |
Programming Code Advanced (PCA) |
|
Yes | No | Undefined |
Perl | %
|
Yes | No | Floored[g] |
POSIX::fmod
|
No | Yes | Truncated | |
Phix | mod
|
Yes | No | Floored |
remainder
|
Yes | No | Truncated | |
PHP | %
|
Yes | No | Truncated[39] |
fmod
|
No | Yes | Truncated[40] | |
PIC BASIC Pro | \
|
Yes | No | Truncated |
PL/I | mod
|
Yes | No | Floored (ANSI PL/I) |
PowerShell | %
|
Yes | No | Truncated |
Programming Code (PRC) | MATH.OP - 'MOD; ()'
|
Yes | No | Undefined |
Progress | modulo
|
Yes | No | Truncated |
Prolog (ISO 1995) | mod
|
Yes | No | Floored |
rem
|
Yes | No | Truncated | |
PureBasic | % , Mod(x,y)
|
Yes | No | Truncated |
PureScript | `mod`
|
Yes | No | Euclidean[41] |
Pure Data | %
|
Yes | No | Truncated (same as C) |
mod
|
Yes | No | Floored | |
Python | %
|
Yes | Yes | Floored |
math.fmod
|
No | Yes | Truncated | |
Q# | %
|
Yes | No | Truncated[42] |
R | %%
|
Yes | Yes | Floored[43] |
Racket | modulo
|
Yes | No | Floored |
remainder
|
Yes | No | Truncated | |
Raku | %
|
No | Yes | Floored |
RealBasic | MOD
|
Yes | No | Truncated |
Reason | mod
|
Yes | No | Truncated |
Rexx | //
|
Yes | Yes | Truncated |
RPG | %REM
|
Yes | No | Truncated |
Ruby | % , modulo()
|
Yes | Yes | Floored |
remainder()
|
Yes | Yes | Truncated | |
Rust | %
|
Yes | Yes | Truncated |
rem_euclid()
|
Yes | Yes | Euclidean[44] | |
SAS | MOD
|
Yes | No | Truncated |
Scala | %
|
Yes | No | Truncated |
Scheme | modulo
|
Yes | No | Floored |
remainder
|
Yes | No | Truncated | |
Scheme R6RS | mod
|
Yes | No | Euclidean[45] |
mod0
|
Yes | No | Rounded[45] | |
flmod
|
No | Yes | Euclidean | |
flmod0
|
No | Yes | Rounded | |
Scratch | mod
|
Yes | Yes | Floored |
Seed7 | mod
|
Yes | Yes | Floored |
rem
|
Yes | Yes | Truncated | |
SenseTalk | modulo
|
Yes | No | Floored |
rem
|
Yes | No | Truncated | |
sh (POSIX) (includes bash, mksh, &c.)
|
%
|
Yes | No | Truncated (same as C)[46] |
Smalltalk | \
|
Yes | No | Floored |
rem:
|
Yes | No | Truncated | |
Snap! | mod
|
Yes | No | Floored |
Spin | //
|
Yes | No | Floored |
Solidity | %
|
Yes | No | Floored |
SQL (SQL:1999) | mod(x,y)
|
Yes | No | Truncated |
SQL (SQL:2011) | %
|
Yes | No | Truncated |
Standard ML | mod
|
Yes | No | Floored |
Int.rem
|
Yes | No | Truncated | |
Real.rem
|
No | Yes | Truncated | |
Stata | mod(x,y)
|
Yes | No | Euclidean |
Swift | %
|
Yes | No | Truncated[47] |
remainder(dividingBy:)
|
No | Yes | Rounded[48] | |
truncatingRemainder(dividingBy:)
|
No | Yes | Truncated[49] | |
Tcl | %
|
Yes | No | Floored |
tcsh | %
|
Yes | No | Truncated |
Torque | %
|
Yes | No | Truncated |
Turing | mod
|
Yes | No | Floored |
Verilog (2001) | %
|
Yes | No | Truncated |
VHDL | mod
|
Yes | No | Floored |
rem
|
Yes | No | Truncated | |
VimL | %
|
Yes | No | Truncated |
Visual Basic | Mod
|
Yes | No | Truncated |
WebAssembly | i32.rem_u , i64.rem_u (unsigned)
|
Yes | No | —[50] |
i32.rem_s , i64.rem_s (signed)
|
Yes | No | Truncated[51] | |
x86 assembly | IDIV
|
Yes | No | Truncated |
XBase++ | %
|
Yes | Yes | Truncated |
Mod()
|
Yes | Yes | Floored | |
Zig | % ,
|
Yes | Yes | Truncated[52] |
Z3 theorem prover | div , mod
|
Yes | No | Euclidean |
In addition, many computer systems provide a divmod
functionality, which produces the quotient and the remainder at the same time. Examples include the x86 architecture’s IDIV
instruction, the C programming language’s div()
function, and Python’s divmod()
function.
Generalizations[edit]
Modulo with offset[edit]
Sometimes it is useful for the result of a modulo n to lie not between 0 and n − 1, but between some number d and d + n − 1. In that case, d is called an offset. There does not seem to be a standard notation for this operation, so let us tentatively use a modd n. We thus have the following definition:[53] x = a modd n just in case d ≤ x ≤ d + n − 1 and x mod n = a mod n. Clearly, the usual modulo operation corresponds to zero offset: a mod n = a mod0 n. The operation of modulo with offset is related to the floor function as follows:
(To see this, let . We first show that x mod n = a mod n. It is in general true that (a + bn) mod n = a mod n for all integers b; thus, this is true also in the particular case when ; but that means that , which is what we wanted to prove. It remains to be shown that d ≤ x ≤ d + n − 1. Let k and r be the integers such that a − d = kn + r with 0 ≤ r ≤ n − 1 (see Euclidean division). Then , thus . Now take 0 ≤ r ≤ n − 1 and add d to both sides, obtaining d ≤ d + r ≤ d + n − 1. But we’ve seen that x = d + r, so we are done. □)
The modulo with offset a modd n is implemented in Mathematica as Mod[a, n, d]
.[53]
Implementing other modulo definitions using truncation[edit]
Despite the mathematical elegance of Knuth’s floored division and Euclidean division, it is generally much more common to find a truncated division-based modulo in programming languages. Leijen provides the following algorithms for calculating the two divisions given a truncated integer division:[5]
/* Euclidean and Floored divmod, in the style of C's ldiv() */ typedef struct { /* This structure is part of the C stdlib.h, but is reproduced here for clarity */ long int quot; long int rem; } ldiv_t; /* Euclidean division */ inline ldiv_t ldivE(long numer, long denom) { /* The C99 and C++11 languages define both of these as truncating. */ long q = numer / denom; long r = numer % denom; if (r < 0) { if (denom > 0) { q = q - 1; r = r + denom; } else { q = q + 1; r = r - denom; } } return (ldiv_t){.quot = q, .rem = r}; } /* Floored division */ inline ldiv_t ldivF(long numer, long denom) { long q = numer / denom; long r = numer % denom; if ((r > 0 && denom < 0) || (r < 0 && denom > 0)) { q = q - 1; r = r + denom; } return (ldiv_t){.quot = q, .rem = r}; }
For both cases, the remainder can be calculated independently of the quotient, but not vice versa. The operations are combined here to save screen space, as the logical branches are the same.
See also[edit]
- Modulo (disambiguation) – many uses of the word modulo, all of which grew out of Carl F. Gauss’s introduction of modular arithmetic in 1801.
- Modulo (mathematics), general use of the term in mathematics
- Modular exponentiation
- Turn (angle)
Notes[edit]
- ^ Mathematically, these two choices are but two of the infinite number of choices available for the inequality satisfied by a remainder.
- ^ a b Argument order reverses, i.e.,
α|ω
computes , the remainder when dividingω
byα
. - ^ C99 and C++11 define the behavior of
%
to be truncated.[9] The standards before then leave the behavior implementation-defined.[10] - ^ As implemented in ACUCOBOL, Micro Focus COBOL, and possible others.
- ^ Divisor must be positive, otherwise undefined.
- ^ As discussed by Boute, ISO Pascal’s definitions of
div
andmod
do not obey the Division Identity of D = d · (D / d) + D % d, and are thus fundamentally broken. - ^ Perl usually uses arithmetic modulo operator that is machine-independent. For examples and exceptions, see the Perl documentation on multiplicative operators.[38]
References[edit]
- ^ Weisstein, Eric W. «Congruence». mathworld.wolfram.com. Retrieved 2020-08-27.
- ^ Caldwell, Chris. «residue». Prime Glossary. Retrieved August 27, 2020.
- ^ Knuth, Donald. E. (1972). The Art of Computer Programming. Addison-Wesley.
- ^ Boute, Raymond T. (April 1992). «The Euclidean definition of the functions div and mod». ACM Transactions on Programming Languages and Systems. ACM Press (New York, NY, USA). 14 (2): 127–144. doi:10.1145/128861.128862. hdl:1854/LU-314490. S2CID 8321674.
- ^ a b Leijen, Daan (December 3, 2001). «Division and Modulus for Computer Scientists» (PDF). Retrieved 2014-12-25.
- ^ Peterson, Doctor (5 July 2001). «Mod Function and Negative Numbers». Math Forum — Ask Dr. Math. Archived from the original on 2019-10-22. Retrieved 22 October 2019.
- ^ Horvath, Adam (July 5, 2012). «Faster division and modulo operation — the power of two».
- ^ a b «ISO/IEC 8652:2012 — Information technology — Programming languages — Ada». ISO, IEC. 2012. sec. 4.5.5 Multiplying Operators.
- ^ «C99 specification (ISO/IEC 9899:TC2)» (PDF). 2005-05-06. sec. 6.5.5 Multiplicative operators. Retrieved 16 August 2018.
- ^ «ISO/IEC 14882:2003: Programming languages – C++». International Organization for Standardization (ISO), International Electrotechnical Commission (IEC). 2003. sec. 5.6.4.
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
- ^ «ISO/IEC 9899:1990: Programming languages – C». ISO, IEC. 1990. sec. 7.5.6.4.
The fmod function returns the value x — i * y, for some integer i such that, if y is nonzero, the result has the same sign as x and magnitude less than the magnitude of y.
- ^ a b dotnet-bot. «Math.IEEERemainder(Double, Double) Method (System)». learn.microsoft.com. Retrieved 2022-10-04.
- ^ «clojure.core — Clojure v1.10.3 API documentation». clojure.github.io. Retrieved 2022-03-16.
- ^ «clojure.core — Clojure v1.10.3 API documentation». clojure.github.io. Retrieved 2022-03-16.
- ^ CoffeeScript operators
- ^ «Expressions — D Programming Language». dlang.org. Retrieved 2021-06-01.
- ^ «operator % method — num class — dart:core library — Dart API». api.dart.dev. Retrieved 2021-06-01.
- ^ «remainder method — num class — dart:core library — Dart API». api.dart.dev. Retrieved 2021-06-01.
- ^ «Kernel — Elixir v1.11.3». hexdocs.pm. Retrieved 2021-01-28.
- ^ «Integer — Elixir v1.11.3». hexdocs.pm. Retrieved 2021-01-28.
- ^ «Basics — core 1.0.5». package.elm-lang.org. Retrieved 2022-03-16.
- ^ «Basics — core 1.0.5». package.elm-lang.org. Retrieved 2022-03-16.
- ^ «Erlang — math». erlang.org. Retrieved 2021-06-01.
- ^ «GLSL Language Specification, Version 4.50.7» (PDF). section 5.9 Expressions.
If both operands are non-negative, then the remainder is non-negative. Results are undefined if one or both operands are negative.
- ^ «GLSL Language Specification, Version 4.50.7» (PDF). section 8.3 Common Functions.
- ^ «The Go Programming Language Specification — The Go Programming Language». go.dev. Retrieved 2022-02-28.
- ^ «math package — math — pkg.go.dev». pkg.go.dev. Retrieved 2022-02-28.
- ^ «big package — math/big — pkg.go.dev». pkg.go.dev. Retrieved 2022-02-28.
- ^ a b «6 Predefined Types and Classes». www.haskell.org. Retrieved 2022-05-22.
- ^ «Operators». Microsoft. Retrieved 2021-07-19.
The % operator is defined only in cases where either both sides are positive or both sides are negative. Unlike C, it also operates on floating-point data types, as well as integers.
- ^ «Mathematics · The Julia Language». docs.julialang.org. Retrieved 2021-11-20.
- ^ «Mathematics · The Julia Language». docs.julialang.org. Retrieved 2021-11-20.
- ^ «rem — Kotlin Programming Language». Kotlin. Retrieved 2021-05-05.
- ^ «mod — Kotlin Programming Language». Kotlin. Retrieved 2021-05-05.
- ^ «Chapter 3: The NASM Language». NASM — The Netwide Assembler version 2.15.05.
- ^ «OCaml library : Stdlib». ocaml.org. Retrieved 2022-02-19.
- ^ «OCaml library : Stdlib». ocaml.org. Retrieved 2022-02-19.
- ^ Perl documentation
- ^ «PHP: Arithmetic Operators — Manual». www.php.net. Retrieved 2021-11-20.
- ^ «PHP: fmod — Manual». www.php.net. Retrieved 2021-11-20.
- ^ «EuclideanRing».
- ^ QuantumWriter. «Expressions». docs.microsoft.com. Retrieved 2018-07-11.
- ^ «R: Arithmetic Operators». search.r-project.org. Retrieved 2022-12-24.
- ^ «F32 — Rust».
- ^ a b r6rs.org
- ^ «Shell Command Language». pubs.opengroup.org. Retrieved 2021-02-05.
- ^ «Apple Developer Documentation». developer.apple.com. Retrieved 2021-11-20.
- ^ «Apple Developer Documentation». developer.apple.com. Retrieved 2021-11-20.
- ^ «Apple Developer Documentation». developer.apple.com. Retrieved 2021-11-20.
- ^ «Numerics — WebAssembly 1.1 (Draft 2022-03-02)». webassembly.github.io. Retrieved 2022-03-16.
- ^ «Numerics — WebAssembly 1.1 (Draft 2022-03-02)». webassembly.github.io. Retrieved 2022-03-16.
- ^ «Zig Documentation». Zig Programming Language. Retrieved 2022-12-18.
- ^ a b «Mod». Wolfram Language & System Documentation Center. Wolfram Research. 2020. Retrieved April 8, 2020.
External links[edit]
- Modulorama, animation of a cyclic representation of multiplication tables (explanation in French)
Математические термины
Во всём последующем материале никак не фигурирует понятие “модуль числа”
в привычном смысле ((lvert x rvert)). Речь идёт о “сравнении по модулю”.
Если вы не знакомы с этим понятием, вкратце сравнение по модулю выглядит
следующим образом:
[a equiv b pmod{m}.]
Это читается “(a) сравнимо с (b) по модулю (m)”, и в привычных для
информатики терминах обозначает следующее:
[(a — b) bmod m = 0]
или
[a bmod m = b bmod m,]
где (bmod) — операция взятия остатка от деления.
Поле по модулю
В некоторых задачах фигурирует условие следующего вида: “выведите остаток от
деления ответа на 1000000007” или “выведите ответ по модулю 1000000007”. Это
вовсе не значит, что вам нужно посчитать ответ обычным способом и вывести
ans % 1000000007
. Ответ в таких задачах
часто настолько огромен, что его сложно представить даже с помощью длинной
арифметики. Для их решения нужно вносить изменения во все
промежуточные вычисления, чтобы не выйти за границы целочисленного типа.
Можно сказать, что в таких задачах мы оперируем не числами, а
их остатками от деления на 1000000007. Это возможно благодаря
следующим свойствам вычислений с остатком:
[(a + b) bmod m = ((a bmod m) + (b bmod m)) bmod m \
(a — b) bmod m = ((a bmod m) — (b bmod m)) bmod m \
(ab) bmod m = ((a bmod m) * (b bmod m)) bmod m]
Таким образом, мы можем выполнять три важнейшие математические операции,
даже не зная точных значений чисел, только их остатки от деления на заданное
число (модуль). Деление — отдельная тема,
которую мы обсудим позже.
Не углубляясь в определения терминов из высшей математики, операции с остатками
от деления на модуль называются операциями в поле по модулю, а сами
остатки — числами по модулю.
Примечание: термин “поле” применим только в том случае, когда модуль —
простое число. В противном случае это называется “кольцо”. Отличие
заключается в том, что для поля определена операция деления, а для кольца —
нет.
Доказательство возможности сложения, вычитания и умножения по модулю
Для начала докажем достаточно очевидное утверждение:
[forall n in mathbb{Z}: x bmod m = (x + nm) bmod m.]
Доказательство:
[((x + nm) — x) bmod m = nm bmod m = 0]
Значит, по определению сравнимости, (forall n in mathbb{Z}: x equiv x + nm pmod{m}),
что и требовалось доказать.
Докажем возможность сложения ((x) и (y) — целые части от
деления (a) и (b) на (m) соответственно):
[(a + b) bmod m = \
= (xm + a bmod m + ym + b bmod m) bmod m = \
= (a bmod m + b bmod m + m(x + y)) bmod m, = \
= (a bmod m + b bmod m) bmod m,]
что и требовалось доказать.
Вычитание и умножение доказываются похожим образом:
[(a — b) bmod m = \
= (xm + a bmod m — ym — b bmod m) bmod m = \
= (a bmod m — b bmod m + m(x — y)) bmod m, = \
= (a bmod m — b bmod m) bmod m,]
[(a * b) bmod m = \
= ((xm + a bmod m) * (ym + b bmod m)) bmod m = \
= (a bmod m * b bmod m + a bmod m * ym + b bmod m * xm + xym^2) bmod m = \
= (a bmod m * b bmod m + m(a bmod m * y + b bmod m * x + xym)) bmod m = \
= (a bmod m * b bmod m) bmod m]
Пример: вычисление факториала по модулю
В качестве примера, вычислим значение (10^8!) по модулю (10^9 + 7):
1 2 3 4 5 6 7 8 9 10 11 12 const long long MOD = 1e9 + 7; long long fact_mod() { long long result = 1; for (int i = 1; i <= 100000000; i++) { result *= i; result %= MOD; //Самая важная строка. } return result; }Как видите, на практике вычисления в поле по модулю отличаются от обычных
лишь наличием взятия всех промежуточных результатов по модулю (строка 8).
Однако существует два момента, которые нужно всегда учитывать для избежания
ошибок:
-
Взятие отрицательных чисел по модулю.
Согласно математическому определению, (-1 bmod 5 = 4), так как (-1 = -1 * 5 + 4).
К сожалению, оператор%
в С++ реализован иначе, и по его версии (-1 bmod 5 = -1).
Это может привести к ошибкам в вычислениях, поэтому нужно вручную обрабатывать такие
случаи следующим образом:long long result; //... result -= x; result %= MOD; if (result < 0) result += MOD; //Теперь всё должно работать.
-
Переполнение типа
int
при умножении.
Не рекомендуется использовать типint
для хранения чисел по модулю
1000000007, так как при умножении двух таких чисел результат может достигать (10^{18}),
что вызывет переполнение. При умножении чисел по модулю всегда используйте тип
long long
!
Возведение в степень по модулю. Бинарное возведение в степень
Возможность умножения по модулю позволяет нам естественным образом возводить
числа в различные степени по модулю. При операциях в поле по модулю степени часто
сильно превышают привычные значения, и тривиальный алгоритм с линейным временем
работы оказывается неприменимым. В таких ситуациях чаще всего используется
алгоритм бинарного возведения в степень.
Алгоритм бинарного возведения в степень достаточно лаконичен. Его идея
заключается в том, чтобы использовать возведение в квадрат промежуточных
результатов, когда это возможно. Используется следующее очевидное свойство:
[x^{2n} = x^n * x^n]
Таким образом засчёт одной операции умножения можно уменьшить степень вдвое.
Если же текущая степень нечётная, то можно просто уменьшить её на единицу простым
умножением, и получить чётную.
Простой рекурсивный вариант на C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 const long long MOD = 1e9 + 7; //base ^ p long long bin_pow(long long base, long long p) { if (p == 1) { return base; //Выход из рекурсии. } if (p % 2 == 0) { long long t = bin_pow(base, p / 2); return t * t % MOD; } else { return bin_pow(base, p - 1) * base % MOD; } }Можно заметить, что в худшем случае на каждом втором вызове функции
степень будет уменьшаться вдвое. Значит, время работы алгоритма можно оценить
как (O(log p)).Разумеется, бинарное возведение в степень можно использовать и без модуля,
но степени в таких случаях слишком малы, чтобы заметить разницу в скорости.Деление в поле по модулю
К сожалению, деление не так легко адаптируется к полю по модулю, как другие
арифметические операции. В этом разделе описывается один из способов деления
по модулю, но не приводится его доказательство, так как оно значительно
усложнило бы эту лекцию.С делением по модулю связана одна особенность. Чтобы операция (a/b bmod m)
имела смысл, необходимо, чтобы числа (b) и (m) были взаимнопростыми. Если модуль
(m) — простое число, он является взаимнопростым со всеми числами по модулю
(m), то есть, делить можно на все числа. Но если модуль составной, то операция
деления имеет смысл лишь для некоторых чисел, и определяется значительно сложнее.
На практике считается, что делить можно только в поле по простому модулю.Деление по модулю определяется через умножение следующим образом:
[{a over b} bmod b = (a * {1 over b}) bmod m = ab^{-1} bmod m.]
Ключевую роль играет значение (b^{-1}), называющееся обратный элемент в
поле по модулю. Оно никак не связано с классическим понятием обратного
числа, хотя бы тем, что всегда является целым (так как в поле по модулю
существуют только целые числа). Для обратного элемента должно выполняться
следующее условие:[(x * x^{-1}) bmod m = 1.]
Например, обратным элементов в поле по модулю (1000000007) для числа (2) является
число (500000004), так как ((2 * 500000004) bmod 1000000007 = 1). Следовательно, в
поле по модулю (1000000007) делению на (2) соответствует умножение на (500000004)Алгоритм нахождения обратного элемента в поле по простому модулю
достаточно прост (в реализации) и выражается следующей формулой:[x^{-1} bmod m = x^{m — 2} bmod m]
Как можно заметить, число (x) возводится в достаточно большую степень, и
линейный алгоритм в этой ситуации не подойдёт. Вот и пример необходимости
использования бинарного возведения в степень по модулю.Реализация на C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 const long long MOD = 1e9 + 7; //base ^ p long long bin_pow(long long base, long long p) { if (p == 1) { return base; } if (p % 2 == 0) { long long t = bin_pow(base, p / 2); return t * t % MOD; } else { return bin_pow(base, p - 1) * base % MOD; } } long long inverse_element(long long x) { return bin_pow(x, MOD - 2); } //(a / b) mod m long long divide(long long a, long long b) { return a * inverse_element(b) % MOD; }Стоит заметить что из-за использования бинарного возведения в степень,
деление по модулю имеет сложность (O(log m)), тогда как все остальные
арифметические операции по модулю работают за (O(1)).
Введение в модульную математику
Когда мы делим одно целое число на другое, мы получаем примерно вот такое выражение:
start fraction, A, divided by, B, end fraction, equals, Q, start text, space, о, с, т, а, т, о, к, space, end text, R
A — делимое
B — делитель
Q — частное
R — остаток
Иногда при делении A на B нас интересует только остаток.
В этом случае используется операция «взятия остатка» или «деления по модулю» (обозначается как mod).
Если взять те же A, B, Q и R, что и в примере выше, получим: A, start text, space, m, o, d, space, end text, B, equals, R
Здесь A разделить по модулю B равняется R. Таким образом, B в такой операции называется модулем.
Наглядное представление модуля при помощи циферблата
Смотрите, что произойдёт, если мы начнём увеличивать на 1, а затем разделим на 3.
Остаток начинается с 0, а затем на каждом шаге он будет увеличиваться на 1, пока не станет на 1 меньше делителя. Затем последовательность начнёт повторяться.
Заметив эту закономерность, мы можем представить деление по модулю при помощи кругов.
Запишем 0 сверху круга, а затем по часовой стрелке будем подписывать: 0, 1, …, до числа, на единицу меньшего, чем модуль.
Например, часовой циферблат, на котором вместо 12 будет стоять 0, — это круг для деления по модулю 12.
Чтобы найти, чему равно A, start text, space, m, o, d, space, end text, B, можно проделать следующие шаги:
- Строим циферблат для модуля B.
- Начиная с 0, движемся по циферблату на A делений.
- Число, на котором мы остановимся, и будет ответом.
(Если число положительное, мы движемся по циферблату по часовой стрелке, если число отрицательное, то мы движемся против часовой стрелки.)
Пример
8, start text, space, m, o, d, space, end text, 4, equals, question mark
Для модуля 4 мы рисуем циферблат с числами 0, 1, 2, 3.
Начинаем с 0 и делаем 8 шагов по часовой стрелке: 1, 2, 3, 0, 1, 2, 3, 0.
Мы остановились на числе 0, следовательно, 8, start text, space, m, o, d, space, end text, 4, equals, 0.
7, start text, space, m, o, d, space, end text, 2, equals, question mark
Для модуля 2 мы рисуем циферблат с числами 0, 1.
Начинаем с 0 и делаем 7 шагов по часовой стрелке: 1, 0, 1, 0, 1, 0, 1.
Мы остановились на 1, значит, 7, start text, space, m, o, d, space, end text, 2, equals, 1.
minus, 5, start text, space, m, o, d, space, end text, 3, equals, question mark
Для модуля 3 мы рисуем циферблат с числами 0, 1, 2.
Начинаем с 0 и делаем 5 шагов против часовой стрелки (число −5 — отрицательное): 2, 1, 0, 2, 1.
Мы остановились на 1, значит, minus, 5, start text, space, m, o, d, space, end text, 3, equals, 1.
Заключение
Если взять выражение A, start text, space, m, o, d, space, end text, B и увеличить A на число, кратное B, результат не изменится, то есть:
A, start text, space, m, o, d, space, end text, B, equals, left parenthesis, A, plus, K, dot, B, right parenthesis, start text, space, m, o, d, space, end text, B для любого целого K.
Примечания для читателя
Деление по модулю в языках программирования и калькуляторах
Во многих языках программирования и калькуляторах есть операция деления по модулю, часто она обозначается символом %. Если вы делите по модулю отрицательное число, в некоторых языках программирования ответ может также получиться отрицательным.
Например:
Сравнение по модулю
Вы можете встретить следующее выражение:
A, equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Это значит, что A равно B по модулю C. Это выражение очень похоже на то, которым мы пользовались выше, но есть и отличия.
В следующей статье мы объясним, что это значит и как это связано с уже известным нам выражением.