[Перевод] Mod и остаток — не одно и то же
Приготовьтесь, вас ждёт крайне педантичная статья, которая вполне может спасти вас на собеседовании или сэкономить несколько часов при вылавливании бага в продакшне!
Я сейчас активно работаю над вторым сезоном «Руководства для самозванца» и пишу о шифре RSA для SSH, который, очевидно, является самым загружаемым фрагментом кода в истории IT.
Кто придумал этот шифр, как он работает, почему работает и будет ли работать в будущем. Хочется полностью разобраться в этой истории. Я не криптоманьяк и вижу, как других буквально засасывает в эту область. Сейчас я раскопал одну чертовски интересную историю. Я также очень хорош в метафорах.
В любом случае: на прошлой неделе я узнал что-то странное и хочу поделиться: оказывается, mod и остаток от деления — не одно и то же. Но мне это тоже интересно, потому что повсюду есть маленькие норки, а меня как сороку привлекают блестящие штучки в глубоких норках. Действительно забавно то, что некоторые читатели при этих словах выпрыгивают со своих кресел и орут: «А ведь именно это я всегда пытался сказать вам и всем остальным!»
Это для вас. Позовите ребят из секты «mod не остаток»!
Я должен был изучить это, как и в прошлый раз, когда всплыла такая тема. Это одна из тех вещей, которые ты знаешь, но не запоминаешь. Когда вы применяете mod, то делите одно число на другое и берёте остаток. Итак: 5 mod 2 будет 1, потому что 5/2=2 с остатком 1.
Большинство языков программирования используют %
для обозначения такой операции: 5 % 2 = 1
. Термин mod означает операцию modulo, с модулем 2 в данном случае.
Вот где мы попадаем в странную серую область.
Помню, как учил это в школе, а потом забыл. Существует тип математики, называемый «модульной арифметикой», которая имеет дело с циклическими структурами. Самый простой способ представить это — циферблат с циклом 12. Для математика циферблат — это mod 12
. Если хотите понять, можно ли равномерно разделить 253 часа на дни, то можете применить операцию 253 mod 24
, результатом будет 13, поэтому ответ «нет»! Мы можем ответить «да» только если результат 0.
Это будет 6 + 16 mod 12
, то есть 10. Другой вопрос, который вы можете задать: «Если я выеду в 6 вечера, сколько времени будет по приезду через 16 часов?».
Это специальные функции, которые позволяют легко вычислить что-то в одном направлении, но не в обратном. Криптографы любят 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 или вращали часы против часовой стрелки, что даёт тот же результат. Модуль равен -12, и мы не можем игнорировать или изменить его, умножив на -1, поскольку модульная арифметика так не работает.
Потому что в таком случае мы будем двигаться назад и постоянно уменьшать результат, пока не достигнем -12, и в этот момент сделаем прыжок +12, а modulo так не работает. Почему не начать метки с -1, двигаясь к -2, и т.д.?
Прежде чем назвать меня сумасшедшим и начать гуглить тему: это известный факт. На самом деле MDN (Mozilla Developer Network) даже дошла до того, чтобы назвать %
операцией «остатка» (remainder), а не modulo:
Он всегда принимает знак делимого. Оператор remainder возвращает остаток от деления одного операнда на другой.
Вот что Эрик Липперт, один из богов C#, говорит о modulo в C#:
Оператор % не является каноническим оператором modulus, это оператор остатка. Однако это совсем не то, что оператор % реально делает в C#.
А как на вашем языке?
Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:
- Я представляю, как этот вопрос займёт меня врасплох на собеседовании.
- Я представляю, как этот попадёт в продакшн, а разработчики будут несколько часов выяснять, почему математика не работает.
Это также забавный факт на случай, если рядом появится ваш педантичный друг-программист.