Quali sono le regole dell'aritmetica modulare in C?

Question

Nelle classi precedenti, mi è stato insegnato che n % d = r e di pensarci come n = d*q + r, dove d è il divisore, q è il quoziente, e r è il resto (notare che il resto non può mai essere negativo).

Così, per esempio, è -111 mod 1110, perché -111 = -11*-11 + 10 (al contrario di -111 = -11*10 -1, visto che che ci darebbe un resto negativo).

Tuttavia, quando si stampano i risultati di -111 % 11, -1 è il risultato e non 10. Perché? Non è tecnicamente sbagliato?

Answer 1

Per modulo, -1 sarebbe una risposta errata.

L'operatore % di C è un operatore rimanente, non un operatore modulo, e per il resto è consentito 10 o -1.

Answer 2

L'operatore % è implementato in modo tale che a == b * (a/b) + (a % b) è vero, in cui si utilizza la divisione integer.

In questo caso -111/11 è -10, quindi -111 == 11 * -10 + x è soddisfatto da x == -1.

Answer 3

Risposta breve:

La garanzia standard che (a/b)*b + a%b è uguale a a.

In C99, il risultato della divisione / verrà troncato verso zero. Il risultato dell'operatore % sarà certo, in questo caso, -1.

In C89, il risultato della divisione / può essere troncato in entrambi i modi per gli operandi negativi. Quindi il risultato dell'operatore % dipende anche dalla macchina.

lunga risposta:

Da C99 6.5.5

5 Il risultato della/operatore è il quoziente della divisione del primo operando dalla secondo; il risultato dell'operatore% è il resto. In entrambe le operazioni, se il valore di il secondo operando è zero, il comportamento non è definito.

6 Quando gli interi sono divisi, il risultato dell'operatore/è il quoziente algebrico con qualsiasi parte frazionata scartata. Se il quoziente a/b è rappresentabile, l'espressione (a/b) * b + a% b deve essere uguale a; in caso contrario, il comportamento di a/b e a% b è indefinito.

e la nota sulla stessa pagina per spiegare come funziona /, si dice:

Questo è spesso chiamato ‘‘il troncamento verso lo zero’’.

Secondo questa regola, -111/11 può essere solo -10, non 1. Da (a/b)*b + a%b deve essere pari a a, abbiamo -111 % 11 è -1.

Tuttavia, K & R Capitolo 2.5 dà una risposta diversa:

La direzione di troncamento per/e il segno del risultato% sono per operandi negativi dipende dalla macchina, come nel seguito dato ai overflow o underflow.

In base a questo, sia -1 o 10 può essere un risultato legale.

La ragione è in C89 3.3.5:

Quando interi vengono divisi e la divisione è inesatto, se entrambi gli operandi sono positivi il risultato del/operatore è il più grande intero minore del quoziente algebrico e il risultato dell'operatore% è positivo. Se uno degli operandi è negativo, se il risultato dell'operatore/è il più grande intero meno del quoziente algebrico o il più piccolo intero maggiore del quoziente algebrico è definito dall'implementazione, come il segno del risultato dell'operatore%. Se il quoziente a/b è rappresentabile, l'espressione (a/b) * b + a% b deve essere uguale a a.

Si è verificato un cambiamento da C89 a C99.

C99 Rationale 6.5.5 fornisce alcune ragioni storiche:

In C89, divisione di numeri interi che coinvolgono operandi negativi potrebbe arrotondare verso l'alto o verso il basso in modo definito dall'implementazione; l'intento era di evitare di sovraccaricare il codice di runtime per verificare casi speciali e applicare un comportamento specifico. In Fortran, tuttavia, il risultato troncerà sempre verso zero e l'overhead sembra essere accettabile per la comunità di programmazione numerica. Pertanto, C99 richiede ora un comportamento simile, che dovrebbe facilitare il porting del codice da Fortran a C. La tabella in §7.20.6.2 di questo documento illustra la semantica richiesta.

Ed ecco la tabella in §7.20.6.2:

numer denom quot rem 
7  3 2 1 
–7  3 –2 –1 
7  –3 –2 1 
–7  –3 2 –1