Хабрахабр

[Перевод] 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#.

А как на вашем языке?
Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:

  1. Я представляю, как этот вопрос займёт меня врасплох на собеседовании.
  2. Я представляю, как этот попадёт в продакшн, а разработчики будут несколько часов выяснять, почему математика не работает.

Это также забавный факт на случай, если рядом появится ваш педантичный друг-программист.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть