Нюансы Python #2: деление и остаток
Вы отлично знакомы с арифметическими операциями в Python? Тогда попробуйте вычислить результат следующих выражений, не запуская интерпретатор:
5 // -2
-5 // 2
5 % -2
-5 % 2
Если у вас получилось -3, -3, -1 и 1, то снимаю перед вами шляпу. А если нет, то добро пожаловать в основную часть поста, где мы подробно разберём, почему получился именно такой результат.
Прочитать материал в более удобном виде, с форматированием и интерактивными примерами кода, можно здесь.
Про разные подходы
В математике «поделить a на b с остатком» означает «найти такие числа q и r, что будет выполняться равенство b*q + r = a».
a - делимое;
b - делитель;
q - неполное частное;
r - остаток.
Например:
11 / 4 = 2, остаток 3.
4 * 2 + 3 = 11
7 / 2 = 3, остаток 1.
2 * 3 + 1 = 7
14 / 5 = 2, остаток 4.
5 * 2 + 4 = 14
А если остаток отрицательный?
В математике принято считать, что остаток должен быть неотрицательным, то есть должно выполняться неравенство 0 <= r < b. Но ведь физически никто не мешает нам сделать так:
11 / 4 = 2, остаток 3
11 / 4 = 3, остаток -1
Равенство b*q + r = a по-прежнему выполняется, а остаток по модулю по-прежнему меньше делителя.
Конечно, если делимое и делитель положительные, то такой выбор остатка выглядит странновато. Но давайте поработаем с отрицательными числами:
11 / -4 = -2, остаток 3
11 / -4 = -3, остаток -1
Какой из этих вариантов правильный? На самом деле, оба. Просто существуют разные подходы к делению с остатком:
- деление с округлением вниз;
- евклидово деление (привычное, как в математике).
Деление с округлением к нулю
«Округлить a к нулю» означает взять первое целое число, которое идёт на числовой прямой сразу после a по направлению к нулю.
Давайте поделим 11 на -4 и -11 на 4. В обоих случаях получится -2.75. Если округлить к нулю, то будет -2.
Теперь посчитаем остаток. Из формулы b*q + r = a выводится, что r = a - b*q. В первом случае: r = 11 - (-4)*(-2) = 11 - 8 = 3, во втором случае: r = -11 - 4*(-2) = -11 - (-8) = -3.
То есть если мы округляем результат деления к нулю, то получаем следующую картину:
11 / -4 = -2, остаток 3
-11 / 4 = -2, остаток -3
При делении с округлением к нулю знак остатка всегда совпадает со знаком делимого, а от знака делителя вообще никак не зависит.
Деление с округлением вниз
«Округлить a вниз» означает взять первое целое число, которое идёт на числовой прямой сразу после a по направлению к минус бесконечности.
Если мы округляем результат деления вниз, то получаем следующую картину:
11 / -4 = -3, остаток -1
-11 / 4 = -3, остаток 1
Теперь знак остатка совпадает со знаком делителя, а от знака делимого не зависит.
Евклидово деление
Это классический подход, который используется в математике. В нём остаток должен всегда быть положительным, а куда для этого нужно округлять неполное частное - уже не имеет значения.
11 / -4 = -2, остаток 3
-11 / 4 = -3, остаток 1
Какой подход используется в Python?
На интуитивном уровне многие считают, что деление нацело (оператор //) сводится к отбрасыванию дробной части. То есть из 2.4 получаем 2, а из -2.4 получаем -2. Это деление с округлением к нулю, и остаток считается соответствующим образом, то есть его знак совпадает со знаком делимого. Во многих языках, от Pascal до C#, используется именно этот подход.
Но создатель Python, Гвидо ван Россум, выбрал другой подход: результат целочисленного деления всегда округляется вниз. За использование деления с округлением вниз в информатике также выступал Дональд Кнут, известный математик и автор книги «Искусство программирования».
Соответственно, в Python -5 // 2 - это -3, а не -2. Знак остатка при этом совпадает со знаком делителя.
Почему именно деление с округлением вниз?
Всё дело в ситуациях, в которых на практике используются операторы // и %.
Например, представьте себе поле размером NxM пикселей. Оно разбито на блоки размером 4х4 точки каждый.
Будем работать со следующими сущностями:
1. Координаты конкретной точки на поле, например, (-38, 11);2. Номер конкретного блока. Например, блок (0, 0) - это тот, в левом нижнем углу которого находится начало координат. Справа от него блок с позицией (1, 0), а сверху - (0, 1);
3. Координаты точки внутри блока. Если ширина блока - 4х4, то координаты точки внутри блока могут меняться от (0, 0) (нижний левый угол) до (3, 3) (верхний правый угол).
И теперь представим, что у нас есть координаты какой-то точки на поле, например, (-38, 11). Как узнать, в каком блоке находится эта точка и какую конкретно позицию внутри блока она занимает? Довольно легко, если в языке используется деление с округлением вниз:
Все результаты не влезли в скриншот, к сожалению. Запустить этот код онлайн можно здесь.
Обратите внимание на то, что с отрицательными координатами всё работает абсолютно корректно. А если бы использовалось деление с округлением к нулю, то для координат (-6, -8) мы получили бы некорректные результаты:
Координаты: (-6, -8)
Позиция блока: (-1, -2)
Позиция пикселя в блоке: (2, 0)
Очевидно, что координата x: -6 никак не может находиться в блоке, имеющем позицию x: -1, потому что ширина блока - 4 пикселя.
Какой подход лучше?
Любой.
Цель статьи не в том, чтобы сказать, что в Python используется хороший или плохой подход. Споры на тему того, как нужно правильно делить, идут уже давно, и навряд ли завершатся в обозримом будущем. Гвидо ван Россум и Дональд Кнут считают, что в программировании удобнее использовать деление с округлением вниз, а другие не менее именитые программисты могут считать, что лучше использовать деление с округлением к нулю или даже евклидово деление.
Поэтому просто запомните, что в Python при делении с остатком результат округляется в меньшую сторону, а не к нулю, и что остаток всегда имеет тот же знак, что и делитель.
