spamsink: (Default)
[personal profile] spamsink


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

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

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

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

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

Date: 2010-06-07 08:12 am (UTC)
From: [identity profile] potan.livejournal.com
Почему для положительных чисел обязательно положительный? Например, для симметричных систем счисления (в компьютере Сетунь используется) очень полезен и отрицательный - там нужен минимльный по модулю.

Date: 2010-06-07 08:30 am (UTC)
From: [identity profile] spamsink.livejournal.com
И чему равен остаток от деления 9 на 6 - трем или минус трем?

Этот вариант тоже есть - mod0 в Scheme, но tie break все равно куда-то должен быть.
Edited Date: 2010-06-07 08:32 am (UTC)

Date: 2010-06-07 09:17 am (UTC)
From: [identity profile] potan.livejournal.com
Обычно используется нечетное основание. Хотя в одном из алгоритмов умножения один из множителей переводится в 4-ричную систему счисления с цифрами -1,0,1,2, пока второй множитель размножается для суммирования.

Date: 2010-06-07 09:21 am (UTC)
From: [identity profile] potan.livejournal.com
Хмм
В mzscheme mod0 выдает отрицательное значение
> (require rnrs/base-6)
> (mod0 2 4)
-2

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

Date: 2010-06-07 09:20 pm (UTC)
From: [identity profile] spamsink.livejournal.com
Чтобы жизнь мёдом не казалась, наверное.

Date: 2010-06-11 04:45 am (UTC)
From: [identity profile] spamsink.livejournal.com
Я нашел, где бывает такое определение деления - в ANDF (см. Upd). Неясно, правда, жив ли он еще.

Date: 2010-06-15 11:31 pm (UTC)
From: [identity profile] 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 — то знаку делителя.
Page generated Feb. 23rd, 2019 11:59 am
Powered by Dreamwidth Studios