Программистское

[spamsink]

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

А каким должен быть знак остатка, если хотя бы одно из чисел, участвующих в операции, отрицательное?

Кроме очевидных вариантов "всегда неотрицательный", "соответствующий знаку делителя" и "соответствующий знаку делимого" (все эти варианты представлены в разнообразных языках программирования, хотя "всегда неотрицательный" и непопулярен), есть и еще один: знак остатка от деления X на Y, если он не равен нулю, соответствует знаку произведения X на Y. Если бы в языке INTERCAL было целочисленное деление, оно бы, наверное, было определено именно так.

Интересно, можно ли придумать такому определению остатка полезное применение?

Upd: В Architecture Neutral Distribution Format одно из определений деления с остатком именно такое: http://docs.tendra.org/reference/xhtml/guide/ch08.html#S69

Comments

[potan.livejournal.com]

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

[spamsink]

И чему равен остаток от деления 9 на 6 - трем или минус трем?

Этот вариант тоже есть - mod0 в Scheme, но tie break все равно куда-то должен быть.

[potan.livejournal.com]

Обычно используется нечетное основание. Хотя в одном из алгоритмов умножения один из множителей переводится в 4-ричную систему счисления с цифрами -1,0,1,2, пока второй множитель размножается для суммирования.

[potan.livejournal.com]

Хмм
В mzscheme mod0 выдает отрицательное значение

> (require rnrs/base-6)
> (mod0 2 4)
-2

Интересно, зачем?

[spamsink]

Чтобы жизнь мёдом не казалась, наверное.

[spamsink]

Я нашел, где бывает такое определение деления - в ANDF (см. Upd). Неясно, правда, жив ли он еще.

[besisland.livejournal.com]

Делимое = делитель ⋅ ц.частное + остаток.

Где ц.частное есть целочисленное частное; вопрос в том, как его определять в случае отрицательного делимого и/или делителя.

Я считаю необходимым рассматривать целочисленное частное в тесной связи с рациональным частным; так, одному и тому же рациональному частному должно соответствовать одно и то же целочисленное частное.

Так, для одновременно отрицательных делимого и делителя получаем:
−10 / (−3) = 3,(3);
ц.частное = 3 (поскольку ц.частное для 10 / 3 = 3,(3) есть 3);
остаток = −10 − ((−3) ⋅ 3) = −1.

Это умозаключение опровергает правило, согласно которому знак остатка соответствует знаку произведения.

Проблема возникает, если знак делимого противоположен знаку делителя. Для −10 / 3 = −3,(3) за целочисленное частное можно взять как −3, так и −4. Причём я не вижу оснований предпочитать одно другому.

Если ц.частное = −3, то остаток = −10 − (3 ⋅ (−3)) = −1.
Если ц.частное = −4, то остаток = −10 − (3 ⋅ (−4)) = 2.

Для противоположного случая:
10 / (−3) = −3,(3).

Если ц.частное = −3, то остаток = 10 − ((−3) ⋅ (−3)) = 1.
Если ц.частное = −4, то остаток = 10 − ((−3) ⋅ (−4)) = −2.

Видим, что если брать за целочисленное частное, соответствующее рациональному частному −3,(3), число −3, то знак остатка соответствует знаку делимого, а если −4 — то знаку делителя.