Mod и остаток — не одно и то же
Приготовьтесь, вас ждёт крайне педантичная статья, которая вполне может спасти вас на собеседовании или сэкономить несколько часов при вылавливании бага в продакшне!
Я сейчас активно работаю над вторым сезоном «Руководства для самозванца» и пишу о шифре 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 и простой остаток одинаковы, когда числа положительны, но отличаются в случае отрицательных чисел.
Рассмотрим такую задачу:
Каково значение x ? Делим числа и получаем 7 как остаток от 12. Это верный ответ. Как насчет такого:
Используя обычную математику, мы можем умножить -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:
Вот что Эрик Липперт, один из богов C#, говорит о modulo в C#:
А как на вашем языке?
Ну и что?
Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:
Оператор 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 (Visual Basic)
result
Обязательный. Любая числовая переменная или свойство.
number1
Обязательный. Произвольное числовое выражение.
number2
Обязательный. Произвольное числовое выражение.
Поддерживаемые типы
все числовые типы. К ним относятся типы без знака и тип с плавающей запятой и Decimal .
Результат
Результат — остаток number1 number2 от деления на. Например, выражение 14 Mod 4 принимает значение 2.
Существует разница между остатком и остатком в математике с различными результатами для отрицательных чисел. Mod оператор в Visual Basic, оператор платформа .NET Framework op_Modulus и базовая инструкция Mod IL выполняют операцию остатка.
Результат Mod операции удерживает знак делимого, number1 и поэтому он может быть положительным или отрицательным. Результат всегда находится в диапазоне (- number2 , number2 ), исключающем. Пример:
Remarks
number1 Если или number2 является значением с плавающей запятой, то возвращается остаток от деления с плавающей запятой. Тип данных результата является наименьшим типом данных, который может содержать все возможные значения, являющиеся результатом деления с типами number1 данных и number2 .
Если number1 или number2 имеет значение number1 , оно считается нулевым.
К связанным операторам относятся следующие.
оператор \ (Visual Basic) возвращает целочисленное частное от деления. Например, выражение 14 \ 4 принимает значение 3.
оператор/(Visual Basic) возвращает полное частное, включая остаток, в виде числа с плавающей запятой. Например, результатом вычисления выражения 14 / 4 является 3,5.
Попыток деления на ноль
Если number2 значение равно нулю, поведение Mod оператора зависит от типа данных операндов:
- Целочисленное деление вызывает исключение, DivideByZeroException Если number2 не может быть определено во время компиляции и вызывает ошибку BC30542 Division by zero occurred while evaluating this expression во время компиляции, если number2 во время компиляции значение равно нулю.
- Деление с плавающей запятой возвращает Double.NaN .
Эквивалентная формула
Выражение a Mod b эквивалентно любой из следующих формул:
Точность чисел с плавающей запятой
При работе с числами с плавающей запятой Помните, что они не всегда имеют точное десятичное представление в памяти. Это может привести к непредвиденным результатам некоторых операций, таких как сравнение значений и Mod оператор. Дополнительные сведения см. в разделе Устранение неполадок типов данных.
Перегрузка
Mod Оператор можно Mod , то есть класс или структура может переопределить его поведение. Если код применяется Mod к экземпляру класса или структуры, включающей такую перегрузку, убедитесь, что вы понимаете его переопределенное поведение. Для получения дополнительной информации см. Operator Procedures.
Пример 1
В следующем примере оператор используется Mod для деления двух чисел и возврата только остатка. Если любое число является числом с плавающей запятой, результатом является число с плавающей запятой, представляющее остаток.
Пример 2
В следующем примере показана потенциальная неточность операндов с плавающей запятой. В первой инструкции операнды имеют Double значение, а 0,2 — бесконечно повторяющуюся двоичную дробь с хранимым значением 0.20000000000000001. Во второй инструкции символ D типа литерала принуждает оба операнда к Decimal , и 0,2 имеет точное представление.