Во многих языках программирования (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
и т. д.
Ответы
Ответ 1
Вопрос мне кажется находится скорее в области определения нежели логики.
Если окунуться в историю вопроса то делимое и остаток от деления относятся к известно
теореме в теории чисел, о том что любое целое число можно разложить на делимое и остато
от деления - теорема доказанная еще во времена Эвклида. Беда только с тем, что во времен
Эвклида люди не знали отрицательных чисел.
Если одно из чисел - делитель или делимое отрицательно, то задача будет иметь 2 решени
- с отрицательным и положительным остатком. Вот тут то и возникает момент договоренности/определения
В русском есть 2-значное толкование, а вот в английском
языке остаток обозначается 2-мя терминами:
Remainder - остаток от деления (может быть и отрицательным)
Residual - буквально осадок (всегда положительный)
Так что в Java и проч. языках используется деление по модулю в смысле Remainder
а то что предлагает @VladD - это Residual
P.S. Как вычисляется деление по модулю в разных языках можно посмотреть здесь - лишни
раз свидетельствует в пользу того, что вопрос не в логике, а в договоренности.
Ответ 2
А кто сказал, что остаток от деления должен отвечать требованиям, которые выгодн
@VladD ?
Открываем стандарт, пункт 5.6. Там четко написано, что делает операция %:
(a/b)*b + a%b эквивалентно a, если только b != 0
То есть, поведение стандартизировано и ожидаемо.
Почему же не сделать остаток всегда положительным? да потому что это условие не буде
выполнятся либо нам нужно будет признать, что целочисленное деление отрицательных чисе
не подчиняется привычным законам алгебры.
Видимо с этим согласны не только математики, а и производители процессоров, потом
что там та же реализация.
Ответ 3
Я считаю, что тогда рушиться логика самого модуля, т.к.:
A / B = C целое (D остаток)
C * B + D = A
В случае с отрицательным числом получаем:
-15 / 2 = -7 (-1)
Обратное действие:
-7 * 2 + (-1) = -15
т.е., что хочу сказать, рушиться математика, если брать положительный остаток, ил
делать вот так:
-15 / 2 = -8 (+1)
upd: что на счет примеров из практики, хм, их нету :) мне как то не доводилось получат
остаток от отрицательного числа :)
Ответ 4
Приходится пользоваться таким оператором %, каким его сделали разработчики и ка
он описан в стандарте, хотя, я знаю две области, где используется остаток от делени
- это помехоустойчивое кодирование и криптография. В обоих случаях остаток от делени
должен возвращать только положительное целое число.
Это требование основано на теории конечных полей Галуа. Важно понимать - что тако
алгебраическая группа, алгебраическое кольцо и поле Галуа (и Вики вам в помощь). Н
корректная реализация деления простом в конечном поле - это целый алгоритм похожий н
алгоритм Евклида. А ещё следует учесть, что конечные поля существуют не для любого количеств
аргументов. А деление в расширенных полях Галуа - ещё сложнее - основано на делени
многочленов в конечных полях.
Так например рассмотрим поле Галуа из 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" в конце минувшего века.
Ответ 5
я тут подумал и мне кажется что операцию остаток от деления надо принять так ка
задумал ее автор это его право, а если не согласны с его мнением то делайте собственну
операцию остатка или пишите функцию, что вы и сделали). вывод: символ процента всег
лишь инструмент а как его использовать каждый решает для себя сам.
Комментариев нет:
Отправить комментарий