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

Question

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

и т. д.

про дробные прогнал, но : http://www.wolframalpha.com/input/?i=17+mod+%287%29 http://www.wolframalpha.com/input/?i=-17+mod+%287%29 — zb', Jun 17 '13 at 12:33
Забавный результат получается, когда делится нацело, а знак разный.
--

Если серьезно, то меня больше устраивает, когда результат совпадает с выработанным схемами процессора. Логичное для задачи поведение наверное лучше явно программировать. — avp, Jun 17 '13 at 13:14
@avp: в таком случае теряется переносимость, разве нет? — VladD, Jun 17 '13 at 16:11
@eicto: Wolfram Alpha даёт как раз тот результат, который я бы хотел. — VladD, Jun 17 '13 at 16:12
@VladD, да, переносимость теряется, точно также, как она теряется при изменении порядка байт в слове, размера указателя и т.п.
Машино- (да и системно-) зависимые части переносимой программы просто надо выделять в отдельные файлы и использовать условную трансляцию (впрочем, это сильно зависит от языка). — avp, Jun 17 '13 at 17:31
@avp: то, что вы говорите, очень в духе C, но не в духе C++. (C++ движется в сторону boost'а, где все системно- и компиляторозависимые штуки спрятаны за «интерфейсом», который перенимает на себя все #ifdef'ы.) — VladD, Jun 17 '13 at 17:41
@VladD, конечно, Си.
Просто в этом я солидарен с Линусом - C++ is a horrible language. — avp, Jun 17 '13 at 19:41
@avp: опасаюсь даже представить, что думает Линус о моём любимом C#. :-) Насчёт критики C++ гораздо более детально здесь. — VladD, Jun 17 '13 at 21:38
@VladD, FQA известная, но весьма длинная и занудная критика С++. Интересно, кто-нибудь ее до конца дочитал?
--

По поводу же C# (мнение Линуса мне неизвестно) - IMHO это просто другой (и похоже хороший) язык, сравнивать его с С++ не стоит. Мне кажется, что основная проблема в нем та же, что и в Java - слишком много классов.

(дискутировать о том, хорошо это или плохо, здесь не удастся - лимит комментариев)

--

А вот опасения RMS по поводу шарпа и free software. — avp, Jun 17 '13 at 22:10
@avp: я дочитал FQA :-) и со многим даже согласен. А насчёт RMS — мне кажется, что Microsoft с тех пор изменились, т.к. потеряли монополию. Вот старшие товарищи подсказывают, что N лет назад самым злым корпоративным монстром была IBM, а сейчас ничего, Линукс поддерживают. В любом случае, это я спорю не с вами, а заочно с RMS. — VladD, Jun 17 '13 at 22:29
Расскажите про ненужность знаний низкоуровневых трюков разработчикам компиляторов, мультимедийных кодеков, игровых движков, демосценерам в конце концов. :) Мы говорим о разной сложности. Не надо мешать в одну кучу сложность системы, алгоритмы, оптимизацию и т.п. Разная сложность — разные инструменты.
В гуе вы будете отображать сразу все сотни тысяч строк или воспользуетесь виртуализацией данных в списке, чтобы отображать только несколько десятков видимых элементов? Покрутил ползунок — нагенерировались сотни строчек, отпустил — сборка мусора. Юзер не заметит задержек. — Kyubey, Feb 27 '15 at 17:01

Barmaley · Accepted Answer · 2013-06-17T17:21:48.370

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

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

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

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

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

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

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

Согласен. А у вас есть примеры полезности именно remainder'а по сравнению с residual? Потому что обратные примеры есть (например, в вопросе). — VladD, Jun 17 '13 at 17:21
Ну конечно: допустим вы взяли кредит и платите равными кусками, затем платите последний транш (остаток) - ясен пень, что знак остатка должен быть равен знаку долга... — Barmaley, Jun 17 '13 at 17:23
@Barmaley: Хм, согласен, пример засчитан.
И правда, не все языки используют остаток как в C. Perl и Python молодцы! :-) — VladD, Jun 17 '13 at 17:35
Вообще-то была принята договоренность, что деление с остатком будет выполняться "неправильно", т.е. выдавать отрицательные числа по одной простой причине: если бы процессор вычислял настоящий правильный остаток, то наш компьютер бы просто жутко тормозил, поэтому остаток на аппаратном уровне (не зависимо от языка) будет отрицательный в случае таковом. — kot_mapku3, Jun 18 '17 at 16:56

KoVadim · Answer 2 · 2013-06-17T12:17:42.323

18

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

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

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

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

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

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

edited Jun 17 '13 at 12:17

answered Jun 17 '13 at 12:16

KoVadim

112,121
6
94
160

1

@KoVadim: а в этом и вопрос: есть ли ситуация, когда существующая имплементация выгодна? Я таких не нашёл, может, вы нашли?
Если мы положим a / b == floor((double)a / (double)b), условие n = q * d + r будет выполняться.
– VladD Jun 17 '13 at 12:20
1

К примеру, в цифровой обработке сигналов некоторые алгоритмы пришлось бы сильно пересмотреть. Загляните в википедию, там есть интересное по этой теме. Кстати, в паскале/делфи знак остатка определяется делимым, а вот в С++ это не определено (по крайней мере по состоянию на 2003). – KoVadim Jun 17 '13 at 12:33
1

@KoVadim: Можете привести пример? Мне, собственно, примеры и интересны. – VladD Jun 17 '13 at 13:07
@KoVadim Извиняюсь за глупый вопрос. А не могли бы ли Вы скинуть ссылку на стандарт ? – Nicholas Essen Feb 27 '15 at 15:35
1

Вы можете его купить или скачать черновик здесь. – KoVadim Feb 27 '15 at 16:47
@NicholasEssen: Или здесь. – VladD Aug 30 '16 at 10:31

score 8 · Answer 3 · edited Jun 12 '20 at 12:52

8

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

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

C * B + D = A

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

-15 / 2 = -7 (-1)

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

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

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

-15 / 2 = -8 (+1)

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

edited Jun 12 '20 at 12:52

Дух сообщества

1

answered Jun 17 '13 at 11:51

IVsevolod

6,744

1
Понял вашу идею. Но почему бы тогда не определить частное как
```
n / d == floor((double)n / (double)d)
```
? У нас получится -15 / 2 = -8 (1).
– VladD Jun 17 '13 at 12:06
1

если к отрицательным числам относиться как к "долгу", то имея долг в 15 условных денег и разделяя его на двоих получим все таки по 7 целых и ещё один "условный деньг" в остатке, а не по 8 целых и один назад.
Хотя если со стороны банка смотреть, то ещё неведомо что лучше.
– KoVadim Jun 17 '13 at 12:36
3

Я так и не понял где рушится математика: 2*(-7)+(-1) = -15
2*(-8)+1 = -15
– Barmaley Jun 17 '13 at 12:38
1

@KoVadim: банк всегда округляет в свою пользу. :-) – VladD Jun 17 '13 at 12:40
1
@Barmaley
я думаю, что логика такая
```
-15/2 = -(15/2) == -(7 + 1/2) == -7 - 1/2 == -7(-1).
```
именно по этому остаток -1.
– KoVadim Jun 17 '13 at 12:45
1

@Barmaley ♦ , а рушится она в этом: -15 / 2 = -7 целых, но никак не -8 целых.
А в случае примера Банк / Долг, с помощью таких махинаций мы получили по -8 долга на двоих, и при этом, кто-то получил прибыль в 1 единицу
– IVsevolod Jun 17 '13 at 13:01
1

@IVsevolod: Логика в обоих случаях одинаковая. -15/2 == -7 означает, что откуда-то возник доход банка в одну единицу. – VladD Jun 17 '13 at 13:07

score 7 · Answer 4 · answered Aug 26 '15 at 14:51

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

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

Так например рассмотрим поле Галуа из 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" в конце минувшего века.

Вопрос скорее не о стандарте — понятно, что если уж стандарт принят, то менять его так просто не стоит. По этой же причине сложно убрать null из C#: программисты и библиотеки полагаются на его существование. Вопрос лишь в том, было ли такое определение операции % ошибкой, и нужно ли существующее поведение в реальности? (И не важно, что исправить ошибку уже невозможно.) — VladD, Aug 26 '15 at 15:02
Когда язык С родился в Bell Lab. В начале 70-х, то мало кто задумывался о его великом будущем. Он позиционировался, как самый быстрый, после Ассемблера. В этой прадигме, такая операция остатка от деления - вполне целесообразна. Я не считаю такой выбор ошибкой. Это операция остатка от деления на бесконечном множестве целых чисел. А то, что в конечных множествах требуются особенные операции - ну так не бывает решений на все случаи жизни. Иначе программисты бы с определённого момента оказались бы более не нужны... — Виктор, Sep 08 '15 at 09:47

score 1 · Answer 5 · answered Oct 30 '13 at 15:29

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

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

5 Answers5

Linked

Related