Modulo (operazione)

In informatica , l' operazione modulo , o operazione mod , è un'operazione binaria che associa a due interi naturali il resto della divisione euclidea del primo per il secondo, il resto della divisione di a per n ( n ≠ 0) si denota un mod n ( a % n in alcuni linguaggi informatici). Quindi 9 mod 4 = 1, perché 9 = 2 × 4 + 1 e 0 ≤ 1 <4, 9 mod 3 = 0,… L'operazione può essere estesa a interi relativi, anche a numeri reali , ma poi i linguaggi di programmazione possono divergere, in particolare un mod n non è più necessariamente positivo o nullo.

In matematica l'uso del termine modulo è diverso anche se collegato: non designa un'operazione ma interviene a caratterizzare una relazione di congruenza su interi (e più in generale per altre congruenze); la parola chiave mod associata è più spesso usata solo per denotare questa congruenza, sebbene un lavoro come Concrete Mathematics la usi anche per denotare l'operazione binaria.

Tre definizioni della funzione modulo

In pratica, x mod y può essere calcolato utilizzando altre funzioni. Così, notando:

x = \ lfloor x \ rfloor + \ {x \}

, con la parte intera inferiore e la parte frazionaria,

\ lfloor x \ rfloor

{\ stile di visualizzazione \ {x \}}

noi abbiamo :

{\ displaystyle a {\ bmod {n}} = a - (\ lfloor a / n \ rfloor \ times n)}

Ad esempio, 9 mod 4 = 9 - ⌊9 / 4⌋ × 4 = 9 - 2 × 4 = 1.

Le differenze vengono visualizzate a seconda dei tipi di variabili utilizzate, che contengono il tipo intero nelle implementazioni comuni. Ma la differenza principale sta nell'interpretazione della parte intera del quoziente, dipendente dal segno del dividendo o da quello del divisore quando questi possono essere negativi:

Utilizzo della parte intera (definizione matematica)

E(z)(notato anche ) è l'intero più grande minore o uguale a z .

\ lfloor z \ rfloor

L'operatore mod restituisce quindi un modulo sempre compreso tra 0 (incluso) e il divisore y (escluso) e che ha lo stesso segno del divisore y :

{\ displaystyle x \ {\ bmod {\}} y = x \ - \ y \ times E {\ begin {pmatrix} {\ frac {x} {y}} \ end {pmatrix}}}

Dividendo	Divisore	Quoziente	Restare
117	17	6	15
–117	17	–7	2
–117	–17	6	–15
117	–17	–7	–2
12,7	3.5	3	2.2

Questa definizione soddisfa le leggi dell'aritmetica modulo , più: x mod - y = - ((- x ) mod y ). È adatto per calcoli ciclici (ad esempio calendario). Il valore modulare restituito è sempre del segno del divisore (il divisore è positivo nella maggior parte dei calcoli ciclici, inclusi i calcoli del calendario).

Utilizzo della funzione 'troncamento della parte decimale' (approssimazione di programmazione)

x % y = x - y * iPart(x / y) Per esempio :

Dividendo	Divisore	Quoziente	Restare
117	17	6	15
–117	17	–6	–15
–117	–17	6	–15
117	–17	–6	15

Il modulo ha lo stesso segno dell'operando sinistro.

Questa definizione verifica la legge: x mod - y = x mod y . Viola la legge ( x + n ) mod n = x mod n .

Confronto in forma tabellare

confronto degli operatori Modulo

		def. matematico		troncamento
Dividendo	Divisore	Quoziente	Restare	Quoziente	Restare	Restare
117	17	6	15	6	15	15
–117	17	–7	2	–6	–15	?
–117	–17	6	–15	6	–15	15
117	–17	–7	–2	–6	15	?
12,7	3.5	3	2.2

Comportamento con operandi non interi

Tutte e tre le definizioni consentono a x e y di essere numeri interi negativi o numeri razionali (o numeri reali in matematica, sebbene i sistemi di calcolo numerico dei computer sappiano lavorare solo su un sottoinsieme di numeri razionali, a causa delle limitazioni di precisione).

Tuttavia in C, C++, PHP e molti linguaggi, l'operatore modo %opera solo su tipi interi. A seconda della lingua, i tipi numerici a volte vengono convertiti implicitamente in numeri interi (per coercizione ).

Comportamento dei linguaggi di programmazione

Le seguenti lingue utilizzano la definizione matematica (1.)

Perl : $a % $nè definito su interi; gli operandi reali vengono troncati verso 0 per coercizione ;
Visual Basic : a Mod nè definito su reali e su interi, e restituisce un intero se entrambi gli operandi sono interi;
Pascal (ISO 7185): a mod nammette solo operandi interi e ndeve essere strettamente positivo;
Excel : MOD(a;n)lavora su numeri reali;
Linguaggio Python : le FAQ spiegano questa scelta con il seguente esempio:

"Se un orologio segna le 10, cosa diceva 200 ore prima?" -190 % 12 == 2È utile; -190 % 12 == -10è un insetto pronto a mordere. "

Le seguenti lingue usano la definizione (2.)

Free Pascal e Delphi consentono solo operandi interi e la definizione del linguaggio specifica: "Il segno del risultato è il segno dell'operando sinistro";
C , C ++ : a % nrichiede operandi interi;
Java : a % nconsente operandi reali;
Javascript : a % nconsente operandi reali;
PHP : $a % $nè definito su interi e restituirà un risultato con lo stesso segno di $a ;
Scilab : modulo(a, n)accetta numeri reali.

Valore di un modulo 0 (valore 'zero')

Nella maggior parte dei linguaggi, l'operazione modulo non genera alcun risultato se il divisore è zero e viene generata un'eccezione aritmetica di divisione per zero.

Equivalenza

Le operazioni modulo possono essere ridotte o estese allo stesso modo delle altre operazioni matematiche.

Identità:
- $(a \, {\ bmod \,} n) \, {\ bmod \,} n = a \, {\ bmod \,} n$
- $n ^ {x} \, {\ bmod \,} n = 0$ per tutti gli interi strettamente positivi . $X$
- Se è un numero primo che non è un divisore di , allora , secondo il piccolo teorema di Fermat . $non$ $B$ $ab ^ {{n-1}} \, {\ bmod \,} n = a \, {\ bmod \,} n$
Inversione:
- $((-a \, {\ bmod \,} n) + (a \, {\ bmod \,} n)) \, {\ bmod \,} n = 0$
- $b ^ {{- 1}} \, {\ bmod \,} n$ è l' inverso modulare , che è impostato se e solo se e sono coprimi , che è il caso quando la porzione sinistra è definita: . $B$ $non$ $((b ^ {{- 1}} \, {\ bmod \,} n) \, (b \, {\ bmod \,} n)) \, {\ bmod \,} n = 1$
Distributività:
- $(a + b) \, {\ bmod \,} n = ((a \, {\ bmod \,} n) + (b \, {\ bmod \,} n)) \, {\ bmod \,} non$
- $ab \, {\ bmod \,} n = ((a \, {\ bmod \,} n) \, (b \, {\ bmod \,} n)) \, {\ bmod \,} n$
- Da dove : ${\ displaystyle a ^ {2} \, {\ bmod {\,}} n = (a \, {\ bmod {\,}} n) ^ {2} \, {\ bmod {\,}} n}$
Divisione (definizione) :, quando l'operando di sinistra è definito. Non definito diversamente. ${\ frac {a} {b}} \, {\ bmod \,} n = ((a \, {\ bmod \,} n) (b ^ {{- 1}} \, {\ bmod \,} n)) \, {\ bmod \,} n$
Moltiplicazione inversa: $((ab \, {\ bmod \,} n) \, (b ^ {{- 1}} \, {\ bmod \,} n)) \, {\ bmod \,} n = a \, {\ bmod \,} n$

Applicazioni

L'operazione modulo consente di eseguire uno spostamento circolare di indici. Infatti, se consideriamo la sequenza di interi contigui da 1 a n , u = (1, 2, 3,…, n - 1, n ), allora possiamo spostarci di p ranghi con:

u ' io = (( u io + p - 1) mod n ) + 1.

Ad esempio, per spostare la sequenza di due (1, 2, 3, 4, 5):

u ' io = (( u io + 1) mod 5) + 1;

noi abbiamo:

u ' 1 = ((1 + 1) mod 5) + 1 = 3
u ' 2 = ((2 + 1) mod 5) + 1 = 4
...
u ' 4 = ((4 + 1) mod 5) + 1 = 1

e quindi u' = (3, 4, 5, 1, 2).

Note e riferimenti

Ronald Graham, Donald Knuth e Oren Patashnik ( trad. Alain Denise), Concrete Mathematics: Foundations for Computer Science , Paris, Vuibert ,2003, 2 ° ed. , xiv + 688 pag. ( ISBN 978-2-7117-4824-2 ), P. 88-89.
Raymond T. Boute , “ La definizione euclidea delle funzioni div e mod ”, ACM Transactions on Programming Languages and Systems , ACM Press (New York, NY, USA), vol. 1, n o 2aprile 1992, pag. 127–144 ( DOI 10.1145 / 128861.128862 , leggi online ), P. 128-129.
Graham, Knuth e Patashnik 2003 , pag. 89, e nota a margine p. 88.
Graham, Knuth e Patashnik 2003 , pag. 88-89, per l'operazione binaria, p.143 per la congruenza. Gli autori usano solo il termine modulo per la relazione di congruenza, ma chiamano l'operazione binaria “mod”.
"Perché -22 // 10 restituisce -3?"
(in) Michaël Van Canneyt, " Guida di riferimento per Free Pascal versione 2.6.0 " ,dicembre 2011.
Dalla ISO C99. In ISO C90, nel caso di un operando negativo, il segno del risultato è stato definito dall'implementazione.