Почему С++ выводит отрицательные числа при использовании 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. Кто-нибудь знает, где ее получить?)

Операция, похоже, определяется следующим образом:

Вопрос:

Имеет ли смысл определять это так?

Каковы аргументы для этой спецификации? Есть ли место, где люди, которые создают такие стандарты, обсуждают это? Где я могу что-то прочитать о причинах, почему они решили сделать это таким образом?

В большинстве случаев, когда я использую 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);
    }
}