Проходя операцию по модулю (проспект, в который я вошел, исследуя разницу между rem
иmod
), я наткнулся на:
В математике результатом операции по модулю является остаток от евклидова деления. Однако возможны и другие соглашения. Компьютеры и калькуляторы имеют различные способы хранения и представления чисел; таким образом, их определение операции по модулю зависит от языка программирования и / или базового оборудования.
Вопросов:
- Проходя евклидово деление, я обнаружил, что остаток этой операции всегда положительный (или 0). Какое ограничение базового компьютерного оборудования заставляет разработчиков языков программирования отличаться от математики?
- У каждого языка программирования есть предопределенное или неопределенное правило, согласно которому результат операции по модулю получает свой знак. Какое обоснование принимается при разработке этих правил? И если проблема связана с базовым оборудованием, не должны ли правила меняться в соответствии с этим, независимо от языка программирования?
programming-languages
language-design
math
arithmetic
design-decisions
Кровоточащие пальцы
источник
источник
(-3)/2 == -1
. Это определение может быть полезным. Когда вы хотите%
соответствовать этому разделению,x == (x/y)*y + x % y
вы в конечном итоге получаете определение%
используемого в C #.Ответы:
Аппаратное обеспечение всех современных компьютеров является достаточно мощным для реализации модовых операций любого знака без какого-либо (или тривиального) влияния на производительность. Это не причина.
Общее ожидание большинства компьютерных языков состоит в том, что (div div) * b + (a mod b) = a. Другими словами, div и mod, рассматриваемые вместе, делят число на части, которые можно надежно соединить снова. Это требование явно указано в стандарте C ++. Концепция тесно связана с индексацией многомерных массивов. Я использовал это часто.
Из этого видно, что div и mod сохранят знак a, если b положительно (как обычно).
Некоторые языки предоставляют функцию rem (), которая связана с модом и имеет другое математическое обоснование. Мне никогда не нужно было использовать это. Смотрите, например, frem () в Gnu C. [отредактировано]
источник
rem(a,b)
это более вероятно,mod(a,b)
если оно положительное илиmod(a,b) + b
нет.(a div b) * b + (a mod b) = a
- это очень много. На самом деле, вопреки тому, как Википедия описывает расширение ее до отрицательных чисел в евклидовом делении (особенно «остаток - единственное из четырех чисел, которое никогда не может быть отрицательным»), меня смущает, потому что меня всегда учили, что остаток может быть отрицательным в каждом классе математики на этом уровне.Для программирования, как правило, вы хотите
X == (X/n)*n + X%n
; поэтому, как определяется по модулю, зависит от того, как было определено целочисленное деление.Имея это в виду, вы действительно спрашиваете: « Какое обоснование используется, когда дизайнеры языка программирования решают, как работает целочисленное деление? »
Есть на самом деле около 7 вариантов:
Теперь посмотрим
-( (-X) / n) == X/n
. Я хотел бы, чтобы это было правдой, поскольку все остальное кажется непоследовательным (это верно для плавающей запятой) и нелогичным (вероятная причина ошибок, а также потенциально пропущенная оптимизация). Это делает нежелательными первые 2 варианта целочисленного деления (округления до бесконечности).Все варианты «округления до ближайшего» являются болью в шее для программирования, особенно когда вы делаете что-то вроде растровых изображений (например
offset = index / 8; bitNumber = index%8;
).Это оставляет округление до нуля «потенциально наиболее разумным» выбором, что подразумевает, что по модулю возвращается значение с тем же знаком, что и у числителя (или нуля).
Примечание: вы также заметите, что большинство процессоров (все процессоры, о которых я знаю) делят целочисленное деление таким же образом «с округлением до нуля». Это, вероятно, будет по тем же причинам.
источник
(a+b*c)/b == a % b
иa >> n == a / 2 ** n
, для которого напольное деление имеет вменяемое поведение.1 >> -2 == a / 2 ** (-2)
).(a + b * c) % b == a % b
, т. Е.%
Оператор является делителем-периодическим в делимом, что часто важно. Например, с разделением по этажамday_count % 7
дает вам день недели, но с усеченным разделением, это разбивает на даты до эпохи.Во-первых, я повторю, что модуль b должен быть равен a - b * (a div b), и если язык этого не обеспечивает, вы попадаете в ужасный математический беспорядок. Это выражение a - b * (a div b) фактически является тем, сколько реализаций вычисляет по модулю b.
Есть несколько возможных обоснований. Во-первых, вам нужна максимальная скорость, поэтому div b определяется как то, что обеспечивает используемый процессор. Если в вашем процессоре есть инструкция "div", тогда div b - это то, что делает эта команда div (если это что-то не совсем безумное).
Во-вторых, вам нужно определенное математическое поведение. Давайте сначала предположим, что b> 0. Вполне разумно, что вы хотите, чтобы результат div b был округлен до нуля. Итак, 4 дел 5 = 0, 9 дел 5 = 1, -4 дел 5 = -0 = 0, -9 дел 5 = -1. Это дает вам (-a) div b = - (a div b) и (-a) по модулю b = - (по модулю b).
Это вполне разумно, но не идеально; например (a + b) div b = (a div b) + 1 не выполняется, скажем, если a = -1. При фиксированном b> 0 обычно есть (b) возможные значения для такого, что div b дает тот же результат, за исключением того, что есть 2b - 1 значения a от -b + 1 до b-1, где div b равно 0 Это также означает, что модуль b будет отрицательным, если a отрицателен. Мы бы хотели, чтобы по модулю b всегда было число в диапазоне от 0 до b-1.
С другой стороны, также вполне разумно просить, чтобы при прохождении последовательных значений a модуль b проходил через значения от 0 до b-1, а затем снова начинался с 0. И запросить, чтобы (a + b) div b было (div div) + 1. Чтобы достичь этого, вы хотите, чтобы результат div b был округлен до -infinity, поэтому -1 div b = -1. Опять же, есть недостатки. (-a) div b = - (div b) не выполняется. Повторное деление на два или на любое число b> 1 в конечном итоге не даст вам результат 0.
Поскольку существуют конфликты, языки должны будут решить, какой набор преимуществ для них важнее, и принять соответствующее решение.
Для отрицательного b большинство людей не могут понять, какими должны быть div и b по модулю b, поэтому простой способ - определить, что div b = (-a) div (-b) и по модулю b = (-a) по модулю (-b), если b <0, или что является естественным результатом использования кода для положительного значения b.
источник