Dlaczego liczby wyjściowe C++ są ujemne przy użyciu modulo?

Question

Math:

Jeśli masz równanie takiego:

x = 3 mod 7 

x może być ... -4, 3, 10, 17, ..., lub bardziej ogólnie:

x = 3 + k * 7 

gdzie k może być dowolną liczbą całkowitą. Nie wiem, że operacja modulo jest zdefiniowana dla matematyki, ale pierścień czynnikowy z pewnością jest.

Python:

W Pythonie, zawsze uzyskać wartości nieujemne podczas korzystania % z pozytywnym m:

#!/usr/bin/python 
# -*- coding: utf-8 -*- 

m = 7 

for i in xrange(-8, 10 + 1): 
    print(i % 7) 

Wyniki w:

6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 

C++:

#include <iostream> 

using namespace std; 

int main(){ 
    int m = 7; 

    for(int i=-8; i <= 10; i++) { 
     cout << (i % m) << endl; 
    } 

    return 0; 
} 

wyświetli:

-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 multiplikatywne operatorzy:

The binary/operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of/or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined 74).

i

74) According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero.

Źródło: ISO/IEC 14882:2003(E)

(Nie mogłem znaleźć bezpłatnej wersji ISO/IEC 1539:1991. Czy ktoś wie gdzie można dostać od)

Operacja wydaje się być zdefiniowane następująco:

Pytanie:

czy to ma sens, aby określić ją w taki sposób?

Co to są argumenty dla tej specyfikacji? Czy istnieje miejsce, w którym dyskutują o tym ludzie, którzy tworzą takie standardy? Gdzie mogę przeczytać o przyczynach, dla których zdecydowali się to zrobić w ten sposób?

W większości przypadków, gdy używam modulo, chcę uzyskać dostęp do elementów struktury danych. W tym przypadku muszę się upewnić, że mod zwraca wartość nieujemną. Tak więc, w tym przypadku byłoby dobrze, aby mod zawsze zwracał wartość nieujemną. (Innym zastosowaniem jest Euclidean algorithm. Ponieważ przed użyciem tego algorytmu można uzyskać obie liczby dodatnie, znaczek modulo miałby znaczenie.)

Dodatkowy materiał:

Zobacz Wikipedia do długiej listy co modulo robi w różnych językach.

Answer 1

Na x86 (i innych architektur procesorów), podział całkowitej i są modulo przeprowadzane przez pojedynczą operację, dla wartości niepodpisanych), które generuje zarówno iloraz, jak i pozostałość (dla argumentów o wielkości słowa odpowiednio w AX i DX). Jest to używane w bibliotece C funkcji divmod, która może być zoptymalizowana przez kompilator do pojedynczej instrukcji!

całkowita uwzględnia podział dwóch zasad:

• niecałkowitą ilorazy są zaokrąglone do zera; i
• równanie dividend = quotient*divisor + remainder jest spełnione przez wyniki.

W ten sposób, dzieląc liczbę ujemną przez liczbę dodatnią, iloraz będzie ujemny (lub zerowy).

Więc to zachowanie może być postrzegane jako wynik łańcucha lokalne decyzje:

• zestaw instrukcji procesora konstrukcja optymalizuje dla wspólnej sprawy (dział) nad mniej wspólnego przypadku (modulo);
• Spójność (zaokrąglanie w kierunku zera i przestrzeganie równania podziału) jest preferowana w stosunku do poprawności matematycznej;
• C preferuje efektywność i w sposób uproszczony (zwłaszcza biorąc pod uwagę tendencję do postrzegania C jako "asemblera wysokiego poziomu"); i
• C++ preferuje kompatybilność z C

Answer 2

What are arguments for this specification?

Jednym z celów projektu C++ jest efektywna mapa sprzętu. Jeśli podstawowy sprzęt implementuje dzielenie w sposób, który generuje ujemne reszty, to właśnie otrzymasz, jeśli użyjesz % w C++. To wszystko jest naprawdę ważne.

Is there a place where the people who create such standards discuss about it?

Znajdziesz tu ciekawe dyskusje na comp.lang.C++. Moderowany i, w mniejszym stopniu, comp.lang.C++

Answer 3

Powrót w dzień, ktoś zaprojektowanie zestawu instrukcji x86 zdecydował, że słuszne i dobre do okrągłej liczby całkowitej podziału kierunku zera zamiast zaokrąglić w dół. (Niech pchły tysiąca wielbłądów gniazdują w brodzie matki). Aby zachować pozory poprawności matematycznej, operator REM, który jest wymawiany jako "pozostały", musiał odpowiednio się zachowywać. NIE czytaj: https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzatk/REM.htm

Ostrzegałem cię. Później ktoś robiący specyfikację C zdecydował, że będzie to zgodne z kompilatorem, aby zrobić to we właściwy sposób lub sposób x86. Następnie komitet robiący specyfikację C++ postanowił zrobić to w sposób C. Później jednak, po opublikowaniu tego pytania, komitet C++ postanowił ujednolicić w niewłaściwy sposób. Teraz utknęliśmy z tym. Wielu programistów napisał następującą funkcję lub coś podobnego. Prawdopodobnie zrobiłem to co najmniej kilkanaście razy.

inline int mod(int a, int b) {int ret = a%b; return ret>=0? ret: ret+b; } 

Tu idzie twoja skuteczność.

Te dni Używam zasadniczo następujące, przy czym niektóre type_traits rzeczy rzucony w. (Dzięki Jaśniejsze o komentarz, który dał mi pomysł na poprawę stosując ostatni dzień C++. Patrz niżej.)

<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; 
} 

Prawda: lobbowałem w komitecie normalizacyjnym Pascala, aby modował się we właściwy sposób, dopóki nie ustąpią. Ku mojemu przerażeniu zrobili podział całkowity w niewłaściwy sposób. Więc nawet nie pasują.

EDYCJA: Jaśniej mi dał pomysł. Pracuję nad nowym.

#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); 
    } 
}