Остаток для негативного аргумента ошибочен?


Во многих языках программирования (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)

(при условии, что вычисление обеих частей не приводят к переполнению).

Приведу несколько примеров.

1) Проверка на нечётность обычно выглядит так:

//bool odd = n % 2 == 1; // неправильно!
bool odd = n % 2 != 0;   // довольно искусственно

Но с новым оператором она работает проще:

bool odd = mod(n, 2) == 1; // как и ожидается.

2) Для вычисления 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);

Сработал бы в любом случае.

3) Приведение угла в градусах к каноническому виду (от 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

И т. д.

Author: luchaninov, 2013-06-17

5 answers

Вопрос мне кажется находится скорее в области определения нежели логики.

Если окунуться в историю вопроса то делимое и остаток от деления относятся к известной теореме в теории чисел, о том что любое целое число можно разложить на делимое и остаток от деления - теорема доказанная еще во времена Эвклида. Беда только с тем, что во времена Эвклида люди не знали отрицательных чисел.

Если одно из чисел - делитель или делимое отрицательно, то задача будет иметь 2 решения - с отрицательным и положительным остатком. Вот тут то и возникает момент договоренности/определения. В русском есть 2-значное толкование, а вот в английском языке остаток обозначается 2-мя терминами:

Remainder - остаток от деления (может быть и отрицательным)

Residual - буквально осадок (всегда положительный)

Так что в Java и проч. языках используется деление по модулю в смысле Remainder, а то что предлагает @VladD - это Residual

P.S. Как вычисляется деление по модулю в разных языках можно посмотреть здесь - лишний раз свидетельствует в пользу того, что вопрос не в логике, а в договоренности.

 67
Author: Barmaley, 2013-06-17 17:21:48

А кто сказал, что остаток от деления должен отвечать требованиям, которые выгодны @VladD ?

Открываем стандарт, пункт 5.6. Там четко написано, что делает операция %:

(a/b)*b + a%b эквивалентно a, если только b != 0

То есть, поведение стандартизировано и ожидаемо.

Почему же не сделать остаток всегда положительным? да потому что это условие не будет выполнятся либо нам нужно будет признать, что целочисленное деление отрицательных чисел не подчиняется привычным законам алгебры.

Видимо с этим согласны не только математики, а и производители процессоров, потому что там та же реализация.

 16
Author: KoVadim, 2013-06-17 12:17:42

Я считаю, что тогда рушится логика самого модуля, т.к.:

A / B = C целое (D остаток)

C * B + D = A

В случае с отрицательным числом получаем:

-15 / 2 = -7 (-1)  

Обратное действие:

-7 * 2 + (-1) = -15

Т.е., что хочу сказать, рушится математика, если брать положительный остаток или делать вот так:

-15 / 2 = -8 (+1)

Upd: что насчёт примеров из практики, хм, их нету :) мне как-то не доводилось получать остаток от отрицательного числа :)

 7
Author: IVsevolod, 2020-06-12 12:52:24

Приходится пользоваться таким оператором %, каким его сделали разработчики и как он описан в стандарте, хотя, я знаю две области, где используется остаток от деления - это помехоустойчивое кодирование и криптография. В обоих случаях остаток от деления должен возвращать только положительное целое число.

Это требование основано на теории конечных полей Галуа. Важно понимать - что такое алгебраическая группа, алгебраическое кольцо и поле Галуа (и Вики вам в помощь). Но корректная реализация деления простом в конечном поле - это целый алгоритм похожий на алгоритм Евклида. А ещё следует учесть, что конечные поля существуют не для любого количества аргументов. А деление в расширенных полях Галуа - ещё сложнее - основано на делении многочленов в конечных полях.

Так например рассмотрим поле Галуа из 7 элементов. То есть у нас есть область определения (и область допустимых значений) {0, 1, 2, 3, 4, 5, 6} и операции сложения и умножения по модулю 7. В этом случае: (1/3) mod 7 = 5 потому что (5*3) mod 7 = 1. Однако команда на C даст значение (1/3) % 7 = 0

Так что было бы не плохо, чтобы команда % работала как в математической теории но на практике приходится делать что-то типа этого примера из моей старой программы:

// a/b mod c
long __fastcall TFormEllipticCrypt::sub_div(long a, long b, long c)
{
long d,e,f,g,h,i,j;
d=1; e=0; g=c; j=b;
for (i=0;j>0;i++)
    {
    h = b/g;
    j = b - h*g;
    if (i != 0)
            {
            f=d*h+e;
            e=d;
            d=f;
            }
    b=g;
    g=j;
    }
if (i%2 != 0) e = c - e;
d = (a*e)%c;
return(d);
}

Конечно, бывают и не редко случаи, когда такие сложности излишни.

А кроме возведения деления есть ещё извлечение корней и логарифмов по модулю (в конечных полях и кольцах) которые считаются совершенно иначе, чем в обычной алгебре вещественных чисел и на столько дороги, что на вычислительной сложности их реализации основана стойкость некоторых известных криптосистем (Диффи-Хеллман, Эль Гамаль, DSA, "Укладка ранца", криптография на эллиптических кривых в конечных полях и т.д. и т.п.)

Но гораздо важнее, если стандарт языка принят - его лучше не изменять, а только дополнять, иначе программы написанные за годы и десятки лет ранее окажутся не правильными в новых версиях компиляторов. И без этого хватает танцев с бубном при переводе приложения на более новую версию компилятора, когда из него удаляют "устаревшие" команды. А если команда останется корректной, но даст иной результат - это потребует усилий сравнимых с исправлением "ошибки 2000" в конце минувшего века.

 6
Author: Виктор, 2015-08-26 14:51:23

Я тут подумал и мне кажется что операцию остаток от деления надо принять так как задумал ее автор это его право, а если не согласны с его мнением то делайте собственную операцию остатка или пишите функцию, что вы и сделали). вывод: символ процента всего лишь инструмент а как его использовать каждый решает для себя сам.

 0
Author: perfect, 2013-10-30 15:29:09