Остаток для отрицательного аргумента ошибочен?
1,00
р.
Во многих языках программирования (C, C++, C#, Java, различные диалекты Паскаля, PHP, JavaScript) есть оператор вычисления остатка. Он действует очевидным, единственно верным образом для положительных значений аргумента (17 % 5 == 2), но для отрицательного делимого и положительного делителя он даёт отрицательный результат:
-17 % 5 == -2
Обычное применение оператора %, однако — для вычисления хэшей, индексов в кольцевом буфере, а также вычисление канонического представителя группы чисел, то есть, для представления отношения эквивалентности. Например, номер дня недели естественным образом вычисляется как остаток от деления «глобального» номера дня на 7. Проверка числа на нечётность также определяется остатком при делении на 2.
Однако, оператор % в том виде, как он реализован в упомянутых языках, непригоден без дополнительной обработки: нужна функция наподобие
int mod(int n, int d) { int result = n % d if (sign(result) * sign(d) < 0) result += d return result }
которая обеспечивает положительный результат при положительном делителе.
У такой функции, в отличие от %, есть полезный инвариант:
mod(n + k * d, d) == mod(n, d)
(при условии, что вычисление обеих частей не приводят к переполнению).
Приведу несколько примеров.
Проверка на нечётность обычно выглядит так: //bool odd = n % 2 == 1 // неправильно! bool odd = n % 2 != 0 // довольно искусственно
Но с новым оператором она работает проще:
bool odd = mod(n, 2) == 1 // как и ожидается.
Для вычисления bucket'а в хэш-таблице тоже применяется остаток: int bucketIdx = object.GetHashCode() % buckets.Count if (bucketIdx < 0) bucketIdx += buckets.Count
или так (код из .NET 4.0)
int positiveHashCode = object.GetHashCode() & 7FFFFFFF int bucketIdx = positiveHashCode % buckets.Count
В то же время
int bucketIdx = mod(object.GetHashCode(), buckets.Count)
сработал бы в любом случае.
Приведение угла в градусах к каноническому виду (от 0 до 360): mod(angle, 360)
В радианах: mod(angle, 2*PI)
То же самое с % выглядит гораздо более тяжеловесно.
Внимание, вопрос: Нужен ли кому-то оператор % в том виде, как он определён в языке? Не лучше было бы, чтобы оператор % возвращал значение как у mod? Я предполагаю, что всякий раз, когда используется оператор %, на самом деле имеется в виду именно mod, и либо входные аргументы всегда положительны, либо используется поправка при отрицательном делимом, либо программа содержит баг.
Есть ли у кого-то примеры (из практики или теоретические), когда нужно именно существующее поведение оператора %?
Двое отвечающих справедливо замечают, что частное q и остаток r при делении n на d должны удовлетворять условию
n == q * d + r
Для того, чтобы это работало, можно переопределить и деление так, чтобы округление выполнялось всегда вниз: q == floor((double)n / (double)d). При этом нужное соотношение будет автоматически выполняться:
4 / 3 == 1 4 % 3 == 1 4 = 1 * 3 + 1 3 / 3 == 1 3 % 3 == 0 3 = 1 * 3 + 0 2 / 3 == 0 2 % 3 == 2 2 = 0 * 3 + 2 1 / 3 == 0 1 % 3 == 1 1 = 0 * 3 + 1 0 / 3 == 0 0 % 3 == 0 0 = 0 * 3 + 0 -1 / 3 == -1 -1 % 3 == 2 -1 = -1 * 3 + 2 -2 / 3 == -1 -2 % 3 == 1 -2 = -1 * 3 + 1
и т. д.
P. S.: На гитхабе .NET недавно появилось предложение ввести «хороший» оператор %%, который бы исправлял недостатки оператора %, но оно, к сожалению, было отвергнуто. Тем не менее, будет добавлено новое API, при помощи которого обсуждаемый вариант вычисления остатка будет доступен.
Ответ
Вопрос мне кажется находится скорее в области определения нежели логики.
Если окунуться в историю вопроса то делимое и остаток от деления относятся к известной теореме в теории чисел, о том что любое целое число можно разложить на делимое и остаток от деления - теорема доказанная еще во времена Эвклида. Беда только с тем, что во времена Эвклида люди не знали отрицательных чисел.
Если одно из чисел - делитель или делимое отрицательно, то задача будет иметь 2 решения - с отрицательным и положительным остатком. Вот тут то и возникает момент договоренности/определения. В русском есть 2-значное толкование, а вот в английском языке остаток обозначается 2-мя терминами:
Remainder - остаток от деления (может быть и отрицательным)
Residual - буквально осадок (всегда положительный)
Так что в Java и проч. языках используется деление по модулю в смысле Remainder, а то что предлагает @VladD - это Residual
P.S. Как вычисляется деление по модулю в разных языках можно посмотреть здесь - лишний раз свидетельствует в пользу того, что вопрос не в логике, а в договоренности.
-17 % 5 == -2
Обычное применение оператора %, однако — для вычисления хэшей, индексов в кольцевом буфере, а также вычисление канонического представителя группы чисел, то есть, для представления отношения эквивалентности. Например, номер дня недели естественным образом вычисляется как остаток от деления «глобального» номера дня на 7. Проверка числа на нечётность также определяется остатком при делении на 2.
Однако, оператор % в том виде, как он реализован в упомянутых языках, непригоден без дополнительной обработки: нужна функция наподобие
int mod(int n, int d) { int result = n % d if (sign(result) * sign(d) < 0) result += d return result }
которая обеспечивает положительный результат при положительном делителе.
У такой функции, в отличие от %, есть полезный инвариант:
mod(n + k * d, d) == mod(n, d)
(при условии, что вычисление обеих частей не приводят к переполнению).
Приведу несколько примеров.
Проверка на нечётность обычно выглядит так: //bool odd = n % 2 == 1 // неправильно! bool odd = n % 2 != 0 // довольно искусственно
Но с новым оператором она работает проще:
bool odd = mod(n, 2) == 1 // как и ожидается.
Для вычисления bucket'а в хэш-таблице тоже применяется остаток: int bucketIdx = object.GetHashCode() % buckets.Count if (bucketIdx < 0) bucketIdx += buckets.Count
или так (код из .NET 4.0)
int positiveHashCode = object.GetHashCode() & 7FFFFFFF int bucketIdx = positiveHashCode % buckets.Count
В то же время
int bucketIdx = mod(object.GetHashCode(), buckets.Count)
сработал бы в любом случае.
Приведение угла в градусах к каноническому виду (от 0 до 360): mod(angle, 360)
В радианах: mod(angle, 2*PI)
То же самое с % выглядит гораздо более тяжеловесно.
Внимание, вопрос: Нужен ли кому-то оператор % в том виде, как он определён в языке? Не лучше было бы, чтобы оператор % возвращал значение как у mod? Я предполагаю, что всякий раз, когда используется оператор %, на самом деле имеется в виду именно mod, и либо входные аргументы всегда положительны, либо используется поправка при отрицательном делимом, либо программа содержит баг.
Есть ли у кого-то примеры (из практики или теоретические), когда нужно именно существующее поведение оператора %?
Двое отвечающих справедливо замечают, что частное q и остаток r при делении n на d должны удовлетворять условию
n == q * d + r
Для того, чтобы это работало, можно переопределить и деление так, чтобы округление выполнялось всегда вниз: q == floor((double)n / (double)d). При этом нужное соотношение будет автоматически выполняться:
4 / 3 == 1 4 % 3 == 1 4 = 1 * 3 + 1 3 / 3 == 1 3 % 3 == 0 3 = 1 * 3 + 0 2 / 3 == 0 2 % 3 == 2 2 = 0 * 3 + 2 1 / 3 == 0 1 % 3 == 1 1 = 0 * 3 + 1 0 / 3 == 0 0 % 3 == 0 0 = 0 * 3 + 0 -1 / 3 == -1 -1 % 3 == 2 -1 = -1 * 3 + 2 -2 / 3 == -1 -2 % 3 == 1 -2 = -1 * 3 + 1
и т. д.
P. S.: На гитхабе .NET недавно появилось предложение ввести «хороший» оператор %%, который бы исправлял недостатки оператора %, но оно, к сожалению, было отвергнуто. Тем не менее, будет добавлено новое API, при помощи которого обсуждаемый вариант вычисления остатка будет доступен.
Ответ
Вопрос мне кажется находится скорее в области определения нежели логики.
Если окунуться в историю вопроса то делимое и остаток от деления относятся к известной теореме в теории чисел, о том что любое целое число можно разложить на делимое и остаток от деления - теорема доказанная еще во времена Эвклида. Беда только с тем, что во времена Эвклида люди не знали отрицательных чисел.
Если одно из чисел - делитель или делимое отрицательно, то задача будет иметь 2 решения - с отрицательным и положительным остатком. Вот тут то и возникает момент договоренности/определения. В русском есть 2-значное толкование, а вот в английском языке остаток обозначается 2-мя терминами:
Remainder - остаток от деления (может быть и отрицательным)
Residual - буквально осадок (всегда положительный)
Так что в Java и проч. языках используется деление по модулю в смысле Remainder, а то что предлагает @VladD - это Residual
P.S. Как вычисляется деление по модулю в разных языках можно посмотреть здесь - лишний раз свидетельствует в пользу того, что вопрос не в логике, а в договоренности.
