Почему С++ выводит отрицательные числа при использовании modulo?
Math
Если у вас есть такое уравнение:
x = 3 mod 7
x может быть... -4, 3, 10, 17,... или более обычно:
x = 3 + k * 7
где k может быть любым целым числом. Я не знаю, что модульная операция определена для математики, но факторное кольцо, безусловно, есть.
Python
В Python вы всегда получите неотрицательные значения, когда используете %
с положительным m
:
#!/usr/bin/python
# -*- coding: utf-8 -*-
m = 7
for i in xrange(-8, 10 + 1):
print(i % 7)
Результаты в:
6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3
С++:
#include <iostream>
using namespace std;
int main(){
int m = 7;
for(int i=-8; i <= 10; i++) {
cout << (i % m) << endl;
}
return 0;
}
Будет выводиться:
-1 0 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 0 1 2 3
ISO/IEC 14882: 2003 (E) - 5.6 Мультипликативные операторы:
Двоичный/оператор дает частное, а двоичный оператор% дает остаток от деления первого выражения на второй. Если второй операнд/или% равен нулю, поведение undefined; в противном случае (a/b) * b + a% b равно a. Если оба операнда неотрицательный, тогда остаток неотрицателен; если нет, знак остаток определяется реализацией 74).
и
74). Согласно работам по пересмотру ISO C, предпочтительный алгоритм для целочисленного деления следует правилам, определенным в стандарт ISO Fortran, ISO/IEC 1539: 1991, в котором всегда округляется до нуля.
Источник: ISO/IEC 14882: 2003 (E)
(Я не мог найти бесплатную версию ISO/IEC 1539:1991
. Кто-нибудь знает, где ее получить?)
Операция, похоже, определяется следующим образом:
![enter image description here]()
Вопрос:
Имеет ли смысл определять это так?
Каковы аргументы для этой спецификации? Есть ли место, где люди, которые создают такие стандарты, обсуждают это? Где я могу что-то прочитать о причинах, почему они решили сделать это таким образом?
В большинстве случаев, когда я использую modulo, я хочу получить доступ к элементам структуры данных. В этом случае я должен убедиться, что мода возвращает неотрицательное значение. Таким образом, для этого случая было бы хорошо, что мода всегда возвращала неотрицательное значение.
(Еще одно использование: Евклидовой алгоритм. Поскольку вы могли бы сделать оба числа положительными, прежде чем использовать этот алгоритм, имеет значение знак modulo.)
Дополнительный материал:
См. Wikipedia для длинного списка того, что modulo делает на разных языках.
Ответы
Ответ 1
В x86 (и других архитектурах процессоров) целочисленное деление и модуляция выполняются одной операцией idiv
(div
для неподписанных значений), которая производит как частное, так и остальное (для аргументов размера слова, в AX
и DX
соответственно). Это используется в библиотечной функции C divmod
, которая может быть оптимизирована компилятором для одной инструкции!
Целочисленное деление учитывает два правила:
- Нецелые числа округлены до нуля; и
- уравнение
dividend = quotient*divisor + remainder
выполняется результатами.
Соответственно, при делении отрицательного числа на положительное число, фактор будет отрицательным (или нулевым).
Таким образом, это поведение можно рассматривать как результат цепочки локальных решений:
- Конструкция набора инструкций процессора оптимизируется для общего случая (деления) по менее распространенному случаю (по модулю);
- Согласованность (округление до нуля и соблюдение уравнения деления) предпочтительнее математической корректности;
- C предпочитает эффективность и простоту (особенно учитывая тенденцию рассматривать C как "ассемблер высокого уровня" ); и
- С++ предпочитает совместимость с C.
Ответ 2
Каковы аргументы для этой спецификации?
Одной из целей дизайна С++ является эффективное отображение аппаратного обеспечения. Если базовое оборудование реализует деление таким образом, что создает отрицательные остатки, то что вы получите, если используете %
в С++. Это все, что есть на самом деле.
Есть ли место, где люди, которые создают такие стандарты, обсуждают это?
Вы найдете интересные обсуждения на comp.lang.С++. moderated и, в меньшей степени, comp.lang.С++
Ответ 3
В свое время кто-то, проектировавший набор команд x86, решил, что правильно и хорошо округлять целочисленное деление в сторону нуля, а не округлять в меньшую сторону. (Пусть бороды тысячи верблюдов гнездятся в его материнской бороде.) Чтобы сохранить некоторое подобие математической корректности, оператор REM, который произносится как "остаток", должен был вести себя соответствующим образом. НЕ читайте это: https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzatk/REM.htm
Я предупреждал тебя. Позже кто-то, кто занимался спецификацией C, решил, что компилятору будет целесообразно сделать это правильно или x86. Затем комитет, выполняющий спецификацию C++, решил сделать это C-способом. Еще позже, после того, как этот вопрос был опубликован, комитет C++ решил стандартизировать неправильный путь. Теперь мы застряли с этим. Многие программисты написали следующую функцию или что-то в этом роде. Я, вероятно, делал это по крайней мере дюжину раз.
inline int mod(int a, int b) {int ret = a%b; return ret>=0? ret: ret+b; }
Там идет ваша эффективность.
В эти дни я использую, по существу, следующее, с добавлением некоторых вещей type_traits. (Спасибо Clearer за комментарий, который дал мне идею для улучшения с использованием последнего дня C++. См. Ниже.)
<strike>template<class T>
inline T mod(T a, T b) {
assert(b > 0);
T ret = a%b;
return (ret>=0)?(ret):(ret+b);
}</strike>
template<>
inline unsigned mod(unsigned a, unsigned b) {
assert(b > 0);
return a % b;
}
Истинный факт: я лоббировал комитет по стандартам Pascal, чтобы сделать мод правильно, пока они не уступили. К моему ужасу, они делали целочисленное деление в неправильном направлении. Так что они даже не совпадают.
РЕДАКТИРОВАТЬ: Яснее дал мне идею. Я работаю над новым.
#include <type_traits>
template<class T1, class T2>
inline T1 mod(T1 a, T2 b) {
assert(b > 0);
T1 ret = a % b;
if constexpr ( std::is_unsigned_v<T1>)
{
return ret;
} else {
return (ret >= 0) ? (ret) : (ret + b);
}
}