В чем разница между получением остатка от деления и взятия модуля?
Сегодня мы продолжим мою постоянную рубрику «В чем разница?» и рассмотрим разницу между получением остатка от деления и взятия по модулю и, выясним, какую из этих операций представляет оператор C# «%»?
Отношение эквивалентности является прекрасным понятием, которое снова и снова всплывает в математике и программировании.
Прежде всего, давайте (снова) определим понятие «отношения»; отношение – это функция, принимающая два аргумента, скажем, два целых числа и возвращающая булев результат, которой говорит, «связаны» ли эти числа или нет. Например, «больше» является отношением. Оно принимает два целых числа, скажем, 4 и 2, и возвращает булев результат, который показывает, является ли 4 «большим», чем 2 или нет; в данном случае, да, является.
«Отношение эквивалентности» – это отношение, которое является рефлексивным, симметричным и транзитивным. То есть, если ∾ – отношение эквивалентности, тогда:
Рефлексивность: отношение X∾X истинно для любого X
Симметричность: X∾Y = Y∾X для любых X и Y
Транзитивность: если оба отношения X∾Y и Y∾Z являются истинными, тогда X∾Z тоже истинно; в противном случае – оно ложно.
Очевидно, что отношение «больше» не является отношением эквивалентности; хотя оно является транзитивным, оно не является ни симметричным, ни рефлексивным. С другой стороны, отношение «иметь одинаковый знак» является отношением эквивалентности; все отрицательные числа эквиваленты, все положительные числа – эквиваленты и нуль – эквивалентен самому себе.
Отношение эквивалентности делит множество целых чисел на (потенциально бесконечное количество) классов эквивалентности. Например, давайте рассмотрим отношение эквивалентности A∾B, которое истинно тогда и только тогда, когда A-B делится без остатка на 4. Тогда отношения 0∾4 и -86∾2 являются истинными. Мы можем создать четыре «класса эквивалентности», в которых каждое целое число находится только в одном классе и при этом отношение между любыми двумя целыми числами внутри этого класса будет истинным. Такими классами являются {0, 4, -4, 8, -8, 12, -12, ... },
{1, -3, 5, -7, 9, -11, ... }, {2, -2, 6, -6, 10, -10} и {3, -1, 7, -5, 11, -9, ... }
Эти классы представляют собой классы «эквивалентных» целых чисел, для которых «эквивалентность» означает, что они «одинаково хорошо подходят для определения того, выполняется отношение или нет». Классы эквивалентности обычно определяются «каноническим» членом; в случае с классами эквивалентности «целых чисел, эквивалентных по модулю четыре» каноническими значениями обычно берутся значения 0, 1, 2 и 3.
Конечно же, этот подход можно обобщить; для любого положительного целого n, можно создать отношение эквивалентности «A∾B, которое выполняется, если разница A-B делится без остатка на n». Это отношение определяет n классов эквивалентности, которые обычно определяются каноническими элементами 0, 1, …, n – 1. Такое отношение обычно записывается (несколько неуклюже с моей точки зрения) как A ≡ B mod n и читается «А эквивалентно B по модулю n».
Хочется думать, что оператор языка C# A % M означает «разбить целые числа на M классов эквивалентности и получить канонический элемент, связанный с классом, содержащим A». Т.е. если вы напишете 123 % 4, то результатом выполнения этого оператора будет 3, поскольку 123 ≡ 3 mod 4, и 3 является «каноническим» элементом, связанным с классом эквивалентности, который содержит 123.
Однако, это совершенно не то, что делает оператор % языка C#. Оператор % – это не оператор получения канонического модуля, это оператор вычисления остатка. На самом деле, выражение A % B отвечает на вопрос: «каким будет остаток от деления A на B, используя целочисленную арифметику?»
Для определения того, что такое остаток от деления, давайте четко определим термины. Делитель, делимое, остаток и частное должны следовать следующему тождеству:
dividend = quotient * divisor + remainder
Сейчас с помощью данного тождества мы не можем дать точный ответ на вопрос, скажем, чему будет равно 123 / 4. С одной стороны, 123 = 30 * 4 + 3 является ожидаемым решением, но следующее решение также является возможным: 123 = 6000 * 4 – 23877. Нам нужно добавить ограничения для частного и остатка от деления.
Мы можем наивно полагать, что минимальное частное является лучшим решением. Но этот вариант, тоже не подходит, поскольку 123 = 1 * 4 + 119 в этом случае будет подходящим решением, поскольку 1 меньше 30, но 1 – это не лучшее частное. Нам нужны более строгие правила, и мы пришли к следующим определениям частного и остатка от деления (мы предполагаем, что делимое и делитель являются корректными, т.е. мы не пытаемся разделить на 0 и т.п.):
* Если существует такое частное, при котором остаток от деления равен нулю, тогда мы берем это частное и при этом остаток равен нулю.
* В противном случае, рассматриваем в качестве частного все неотрицательные целые числа. Берем наибольшее частное, при котором остаток от деления является положительным.
* Если знаки делителя и делимого противоположные, тогда частное должно быть отрицательным.
* Теперь можно вычислить остаток от деления, при котором тождество будет выполняться.
Следствием этих правил является то, что целочисленное деление округляется до целого в сторону нуля. Это разумно; мы хотим, чтобы результатом деления 123 на 4 было 30 с остатком 3, а не 31 с остатком от деления -1. Аналогично, мы хотим, чтобы -123/4 равнялось -30, а не -31! Было бы странным утверждать, что 4 присутствует в числе 123 30 раз, а в -123 присутствует -31 раз! Мы ожидаем, что изменение знака выражения приведет к изменению знака результата; но это не изменит его модуля.
Если -123/4 равняется -30, тогда чему равен остаток от деления? Он также должен следовать указанному ранее тождеству, поэтому остаток равен -3. Это не каноническое значение, связанное с классом эквивалентности, содержащим -123; каноническое значение равно 1.
Очень важно понимать этот факт при балансировке хеш-таблицы:
int bucketIndex = item.GetHashCode() % bucketCount;
Или при определении, является ли число нечетным:
var oddNumbers = someSequence.Where(x => x % 2 == 1);
Первый пример неверный, поскольку при отрицательном значении хеш-кода мы получим отрицательное значение индекса; второй пример неверный, поскольку в этом случае мы не сможем установить, что -123 является нечетным. Оператор % возвращает не канонический модуль, он возвращает остаток от деления.