По следам наших выступлений

[spamsink]

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

Оказывается, случаи разные бывают, и небезызвестный компилятор с Паскаля по ошибке вычисляет остаток именно так при оптимизации константных выражений:

 PASCAL COMPILER 15.0 (15.02.82)
 00001    1  0 PROGRAM MAIN(OUTPUT);
 00001    2  1 VAR P5, M5, P3, M3: INTEGER;
 00007    3  2 BEGIN
 00010    4  2  P5:=5; P3:=3; M5:=-5; M3:=-3;
 00014    5  2  WRITELN(’           5 MOD 3 |-5 MOD 3 | 5 MOD -3 |-5 MOD -3’);
 00017    6  2  WRITELN(’ CONST’, 5 MOD 3, -5 MOD 3, 5 MOD (-3), -5 MOD (-3));
 00032    7  2  WRITELN(’  VAR ’, P5 MOD P3, M5 MOD P3, P5 MOD M3, M5 MOD M3);
 00063    8  0  END.
           *EXECUTE
           5 MOD 3 |-5 MOD 3 | 5 MOD -3 |-5 MOD -3
 CONST         2        -2        -1         1
  VAR          2         1        -1        -2

Извините, если кого обидел.

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

Если тебе надо пройти 5 метров на юг трехметровыми шагами, а ты стоишь лицом к северу, то логично будет, если остаток пути надо делать
- или всегда в ту же сторону света, в какую делал шаги; неважно лицом вперед или пятился (сделал один шаг на юг, и еще надо 2 метра на юг, знак остатка равен знаку делимого),
- или всегда вперед (сделал два шага пятясь, и еще метр вперед, знак остатка равен знаку делителя),
- или, так уж и быть, всегда на север (остаток всегда неотрицательный).

А вот логика, что если ты ходил вперед, то остаток должен быть к северу, а если пятился, то к югу (знак остатка равен знаку частного), мне была бы непонятна.

Comments

[juan_gandhi]

По мне так оно и должно быть неотрицательным. Помню, специально принимал меры. Раз уж определено для отрицательных (смысла не вижу).

Остроконечники против тупоконечников

[malobukov]

Это известный камень преткновения. Операция с отрицательными аргументами не имеет особого смысла, каждый компилятор должен её как-то имплементировать, вот и получается разброд и шатание. Где-то знак результата как у числителя, где-то как у знаменателя, где-то всегда положительный, где-то вообще implementation dependent.

[rwalk]

А по-моему это как раз самое логичное определение. Пусть А и Р целые, и Р не делит А. Если А и Р положительны, то остаток от деления А на P это разумеется А-КР, если А заключено между KР и (К+1)Р. Далее, естественно перенести это определение на случай и отрицательных К (так кто, если разница двух чисел кратна Р, то их остатки при делении на Р одинаковы). Наконец, все то же определение в случае отрицательного Р даст отрицательные остатки. В Паскале именно так и сделано.

А вообще напоминает мой любимый анекдот про отрицательную посещаемость лекций: сидят на лекции два студента; вдруг трое встают и выходят. Профессор вздыхает и говорит: ну вот, сейчас еще один придет, тогда вообще ни одного не останется.

[spamsink]

См. апдейт.

Re: Остроконечники против тупоконечников

[spamsink]

Implementation dependent всё равно один из этих трех вариантов, или есть другие случаи?
Также см. апдейт.

[spamsink]

А чего бы это А должно быть заключено между КР и (К+1)Р, что за магическая константа 1?
А не между КР и (К+A/abs(A))P?

Также см. апдейт.

Re: Остроконечники против тупоконечников

[malobukov]

Я читаю implementation dependent как "может быть что угодно, хочешь нужный тебе знак - ставь его сам".

То есть это не так страшно, как undefined behavior, но просто раз проверить и надеяться на то, что так будет всегда - опрометчиво.

Re: Остроконечники против тупоконечников

[spamsink]

Implementation dependent means that a certain construct differs from platform to platform but in a defined, well-specified manner.

[juan_gandhi]

Через шаги как бы убедительно. Но шаги-то у тебя тоже положительные. Даже если ты задом идешь.

[sab123]

Джава считает остаток именно так (что было для меня сюрпризом).

[spamsink]

Абсолютное значение частного отвечает на вопрос, сколько полных шагов надо сделать, а знак - надо их делать вперед или назад.

[spamsink]

Именно как? https://en.wikipedia.org/wiki/Modulo_operation
Java:

	%	Dividend
Math.floorMod	Divisor

И в чем сюрприз?

[rwalk]

Есть такая магическая константа в арифметике - на ней аксиоматика Пеано построена.

[sab123]

Остаток имеет знак делимого. Сюрприз в том, что в процессоре остаток от деления всегда положительный.

[spamsink]

В каком это процессоре остаток от деления всегда положительный? Не в х86 уж точно: Non-integral results are truncated (chopped) towards 0. The sign of the remainder is always the same as the sign of the dividend.

[spamsink]

Ну есть, но чем +1 лучше, чем sign(A), не объяснено.

[sab123]

Гм, да? Значит я неправильно запомнил.