Operació mòdul

Funcions quocient (vermell) i residu (verd) emprant diferents algorismes

En informàtica, l'operació mòdul troba el residu de la divisió d'un nombre entre un altre (aquest residu també se sol anomenar mòdul).

Donats dos nombres positius, $a$ (el dividend) i $n$ (el divisor), a mòdul n (abreujat com a mod n) és el residu de la divisió euclidiana de a entre n. Per exemple, l'expressió "5 mod 2" té com a resultat 1, perquè 5 dividit entre 2 dona un quocient de 2 i un residu d'1, mentre que "9 mod 3" té com a resultat 0, perquè la divisió de 9 entre 3 té un quocient de 3 i un residu de 0; no cal restar res de 9 després de multiplicar 3 per 3. Noteu que si es realitza la divisió amb una calculadora convencional, no es mostrarà el resultat indicat anteriorment, sinó que s'expressarà el quocient en forma de fracció decimal.

Encara que aquesta operació acostuma a realitzar-se entre dos nombres naturals, molts sistemes de computació permeten altres tipus d'operands numèrics. El rang de nombres que pot adoptar el mòdul va des de 0 fins a n − 1. (n mod 1 sempre és 0; n mod 0 no està definit, causant un error "Divisió per zero" en els llenguatges de programació).

Quan $a$ o bé $n$ són negatius, la definició intuïtiva que hem vist no es pot aplicar, i els diferents llenguatges de programació ofereixen diferents resultats.

Càlcul del residu per a l'operació mòdul

Operadors mòdul enters en diversos llenguatges de programació
Llenguatge	Operador	El resultat té el mateix signe que el...
ActionScript	`%`	Dividend
Ada	`mod`	Divisor
Ada	`rem`	Dividend
ASP	`Mod`	Indefinit
ALGOL-68	`÷×, mod`	Sempre positiu
AMPL	`mod`	Dividend
APL	`\|`	Divisor
AppleScript	`mod`	Dividend
Assemblador x86	`IDIV`	Dividend
AWK	`%`	Dividend
BASIC	`Mod`	Indefinit
bash	`%`	Dividend
bc	`%`	Dividend
C (ISO 1990)	`%`	Segons la implementació
C (ISO 1990)	`div`	Dividend
C++ (ISO 1998)	`%`	Segons la implementació^[1]
C++ (ISO 1998)	`div`	Dividend
C (ISO 1999)	`%`, `div`	Dividend^[2]
C++ (ISO 2011)	`%`, `div`	Dividend
C#	`%`	Dividend
CLARION	`%`	Dividend
Clojure	`mod`	Divisor
COBOL^{[nota 1]}	`FUNCTION MOD`	Divisor
CoffeeScript	`%`	Dividend
CoffeeScript	`%%`	Divisor^[3]
ColdFusion	`%, MOD`	Dividend
Common Lisp	`mod`	Divisor
Common Lisp	`rem`	Dividend
D	`%`	Dividend^[4]
Dart	`%`	Sempre positiu
Dart	remainder()	Dividend
Eiffel	`\\`	Dividend
Erlang	`rem`	Dividend
Euphoria	`mod`	Divisor
Euphoria	`remainder`	Dividend
F#	`%`	Dividend
FileMaker	`Mod`	Divisor
Forth	`mod`	Segons la implementació
Fortran	`mod`	Dividend
Fortran	`modulo`	Divisor
Frink	`mod`	Divisor
GML (Game Maker)	`mod`	Dividend
GDScript	`%`	Dividend
Go	`%`	Dividend
Haskell	`mod`	Divisor
Haskell	`rem`	Dividend
Haxe	`%`	Dividend
J	`\|~`	Divisor
Java	`%`	Dividend
Java	`Math.floorMod`	Divisor
JavaScript	`%`	Dividend
Julia	`mod`	Divisor
Julia	`rem`	Dividend
LibreOffice	`=MOD()`	Divisor
Lua 5	`%`	Divisor
Lua 4	`mod(x,y)`	Divisor
Liberty BASIC	`MOD`	Dividend
MathCAD	`mod(x,y)`	Divisor
Maple	`e mod m`	Sempre positiu
Mathematica	`Mod`	Divisor
MATLAB	`mod`	Divisor
MATLAB	`rem`	Dividend
Maxima	`mod`	Divisor
Maxima	`remainder`	Dividend
Maya Embedded Language	`%`	Dividend
Microsoft Excel	`=MOD()`	Divisor
Minitab	`MOD`	Divisor
mksh	`%`	Dividend
Modula-2	`MOD`	Divisor^{[nota 2]}
MUMPS	`#`	Divisor
NASM NASMX	`%`	Operador mòdul sense signe
NASM NASMX	`%%`	Operador mòdul amb signe
Oberon	`MOD`	Divisor^{[nota 2]}
OCaml	`mod`	Dividend
Occam	`\`	Dividend
Pascal (Delphi)	`mod`	Dividend
Pascal (ISO-7185 and ISO-10206)	`mod`	Sempre positiu
Perl	`%`	Divisor^{[nota 3]}
PHP	`%`	Dividend
PIC Basic Pro	`\\`	Dividend
PL/I	`mod`	Divisor (ANSI PL/I)
PowerShell	`%`	Dividend
Progress	`modulo`	Dividend
Prolog (ISO 1995)	`mod`	Divisor
Prolog (ISO 1995)	`rem`	Dividend
Python	`%`	Divisor
Python	`math.fmod`	Dividend
Racket	`remainder`	Dividend
RealBasic	`MOD`	Dividend
R	`%%`	Divisor
REXX	`//`	Dividend
RPG	`%REM`	Dividend
Ruby	`%, modulo()`	Divisor
Ruby	`remainder()`	Dividend
Rust	`%`	Dividend
Scala	`%`	Dividend
Scheme	`modulo`	Divisor
Scheme	`remainder`	Dividend
Scheme R⁶RS	`mod`	Sempre positiu^[5]
Scheme R⁶RS	`mod0`	El més pròxim a zero^[5]
Seed7	`mod`	Divisor
Seed7	`rem`	Dividend
SenseTalk	`modulo`	Divisor
SenseTalk	`rem`	Dividend
Smalltalk	`\\`	Divisor
Smalltalk	`rem:`	Dividend
SQL (SQL:1999)	`mod(x,y)`	Dividend
Standard ML	`mod`	Divisor
Standard ML	`Int.rem`	Dividend
Stata	`mod(x,y)`	Sempre positiu
Swift	`%`	Dividend
Tcl	`%`	Divisor
Torque Game Engine	`%`	Dividend
Turing	`mod`	Divisor
Verilog (2001)	`%`	Dividend
VHDL	`mod`	Divisor
VHDL	`rem`	Dividend
Visual Basic	`Mod`	Dividend
Xbase++	`%`	Dividend
Xbase++	`Mod()`	Divisor
Z3 theorem prover	`div`, `mod`	Sempre positiu

Operadors mòdul en coma flotant en diversos llenguatges de programació
Llenguatge	Operador	El resultat té el mateix signe que el...
C (ISO 1990)	`fmod`	Dividend^[6]
C (ISO 1999)	`fmod`	Dividend
C (ISO 1999)	`remainder`	El més pròxim a zero
C++ (ISO 1998)	`std::fmod`	Dividend
C++ (ISO 2011)	`std::fmod`	Dividend
C++ (ISO 2011)	`std::remainder`	El més pròxim a zero
C#	`%`	Dividend
Common Lisp	`mod`	Divisor
Common Lisp	`rem`	Dividend
D	`%`	Dividend
Dart	`%`	Sempre positiu
Dart	remainder()	Dividend
F#	`%`	Dividend
Fortran	`mod`	Dividend
Fortran	`modulo`	Divisor
Go	`math.Mod`	Dividend
Haskell (GHC)	`Data.Fixed.mod'`	Divisor
Java	`%`	Dividend
JavaScript	`%`	Dividend
Microsoft Excel	`=MOD()`	Divisor
OCaml	`mod_float`	Dividend
Perl	`POSIX::fmod`	Dividend
Perl6	`%`	Divisor
PHP	`fmod`	Dividend
Python	`%`	Divisor
Python	`math.fmod`	Dividend
REXX	`//`	Dividend
Ruby	`%, modulo()`	Divisor
Ruby	`remainder()`	Dividend
Scheme R⁶RS	`flmod`	Sempre positiu
Scheme R⁶RS	`flmod0`	El més pròxim a zero
Standard ML	`Real.rem`	Dividend
Swift	`%`	Dividend
Xbase++	`%`	Dividend
Xbase++	`Mod()`	Divisor

En matemàtiques, el resultat de l'operació mòdul és el residu de la divisió euclidiana, encara que són possibles altres convencions. Els ordinadors i les calculadores tenen diferents maneres d'emmagatzemar i representar els nombres, i per tant la seva definició de l'operació mòdul depèn del llenguatge de programació i/o del maquinari subjacent.

En gairebé tots els sistemes de computació, el quocient $q$ i el residu $r$ de $a$ dividit per $n$ satisfà

${\begin{aligned}q\,&\in \mathbb {Z} \\a\,&=nq+r\\|r|\,&<|n|.\end{aligned}}$

(1)

Tot i aquestes condicions, encara existeix una ambigüitat respecte al signe si el residu és diferent de zero: hi ha dues opcions possibles per al residu, una amb signe negatiu i l'altra amb signe positiu, i també hi ha dues opcions per al quocient. En teoria de nombres, hom acostuma a escollir el residu amb signe positiu, però l'elecció dels llenguatges de programació depèn del llenguatge i dels signes de a i/o n.^{[nota 4]} Les implementacions estàndard de Pascal i Algol68 proporcionen un residu positiu (o 0) fins i tot per a divisors negatius, i alguns llenguatges de programació, com C90, deixen l'elecció del signe del residu a cada implementació, en el cas on n o a són negatius (vegeu la taula per a més detalls). L'operació a mòdul 0 resta indefinida per a la majoria de sistemes, encara que alguns d'ells la defineixen per tal que el resultat sigui a.

Moltes implementacions empren la divisió truncada, on es defineix el quocient per truncament $q = trunc(a / n)$ , i per tant, d'acord amb l'equació (1), el residu hauria de tenir el mateix signe que el dividend. El quocient s'arrodoneix cap a zero: igual al primer enter en la direcció del zero des del quocient racional exacte.

r=a-n\operatorname {trunc} \left({\frac {a}{n}}\right)

Donald Knuth^[7] descriu la divisió arrodonida ((anglès) floored division) on el quocient ve definit per la funció part entera $q = ⌊ a / n ⌋$ , i per l'equació (1), el residu hauria de tenir el mateix signe que el divisor. A causa del comportament de la funció part entera, el quocient sempre s'arrodoneix cap a baix, fins i tot si és negatiu.

r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor

Raymond T. Boute^[8] descriu la definició euclidiana en la qual el residu és sempre no-negatiu, $0 \leq r$ , i per tant és consistent amb l'algorisme de divisió euclidiana. Aquesta convenció està simbolitzada per Sempre negatiu
a la taula. En aquest cas,

n>0\Rightarrow q=\left\lfloor {\frac {a}{n}}\right\rfloor

n<0\Rightarrow q=\left\lceil {\frac {a}{n}}\right\rceil

o equivalentment

q=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor

on

sgn

és la funció signe, i per tant

r=a-|n|\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor

.

Common Lisp també defineix la divisió arrodonida i la divisió entera per dalt ((anglès) ceiling-division), on la divisió ve donada per $q = round(a / n)$ i $q = ceil(a / n)$ respectivament.
IEEE 754 defineix una funció residu on el quocient és $a / n$ arrodonit cap a la convenció més propera. Per tant, el signe del residu s'escull per tal que sigui el més pròxim a zero.

Com descriu Leijen,

«	(anglès) Boute argues that Euclidean division is superior to the other ones in terms of regularity and useful mathematical properties, although floored division, promoted by Knuth, is also a good definition. Despite its widespread use, truncated division is shown to be inferior to the other definitions.	(català) Boute argumenta que la divisió euclidiana és superior a les altres, en termes de regularitat i utilitat de les seves propietats matemàtiques, encara que la divisió arrodonida, recomanada per Knuth, també és una bona definició. Tot i el seu ús generalitzat, s'ha vist que la divisió truncada és inferior a les altres definicions.	»
— Daan Leijen, Division and Modulus for Computer Scientists^[9]

Malentesos comuns

Quan el resultat de l'operaciò mòdul té el signe del dividend, de vegades pot portar a resultats sorprenents.

Per exemple, per comprovar si un nombre és senar, hom podria pensar a comprovar si el residu de la divisió entre 2 dona 1:

bool es_senar(int n) {
 return n % 2 == 1;
}

Però en un llenguatge on el mòdul té el signe del dividend, aquesta implementació és incorrecta, perquè quan n (el dividend) és negatiu i senar, n % 2 retorna −1, i la funció retorna fals.

Una alternativa correcta és comprovar que el residu no és 0 (perquè un residu 0 és independent del signe dels operands):

bool es_senar(int n) {
 return n % 2 != 0;
}

O bé tenint en compte que, per a un nombre senar, el residu pot ser 1 o −1:

bool es_senar(int n) {
 return n % 2 == 1 || n % 2 == -1;
}

Expressió de l'operació mòdul

Algunes calculadores tenen un botó de funció mod() , i molts llenguatges de programació tenen una funció mod() o similar, expressada com mod(a, n), per exemple. Alguns suporten també expressions que usen "%", "mod", o "Mod" com a operador mòdul o residu, com

a % n

o

a mod n

o equivalentment, en entorns que no disposen d'una funció mod() (notem que 'int' retorna la part entera de a/n):

a - (n * int(a/n)).

Cost computacional

És possible implementar les operacions mòdul de manera que, a cada pas, es calculi una divisió amb residu. Però en casos especials, existeixen alternatives més ràpides sobre certs tipus de maquinari. Per exemple, el residu de potències de 2 també es pot expressar en forma d'operació AND bit a bit:

x % 2ⁿ == x & (2ⁿ - 1).

Exemples (suposant que x és un enter positiu):

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7.

En dispositus i programes que implementen les operacions bit a bit de forma més ràpida que les operacions mòdul, aquestes alternatives proporcionen càlculs més ràpids.^[10]

Els compiladors optimitzadors poden reconèixer expressions de la forma expressió % constant on constant és una potència de 2, i llavors implementar-les com expressió & (constant-1). Això permet al programador escriure codi més senzill i sense penalitzar el rendiment. (Nota: Aquesta aproximació no funciona per a llenguatges on el residu té el signe del dividend –com ara C–, perquè si el dividend és negatiu, llavors el residu serà negatiu, però expressió & (constant-1) sempre retornarà un resultat positiu; de tal manera que cal fer un tractament especial per al cas on el dividend pot ser negatiu.)

Equivalències

Algunes operacions mòdul es poden factoritzar o desenvolupar, de la mateixa manera que altres operacions matemàtiques. Això pot ser útil en demostracions de criptografia, com l'intercanvi de claus Diffie-Hellman.

Identitat:
- $(a\,{\bmod {\,}}n)\,{\bmod {\,}}n=a\,{\bmod {\,}}n$
- $n^{x}\,{\bmod {\,}}n=0$ per a tots els valors enters positius de $x$ .
- Si $n$ és un nombre primer que no és un divisor de $b$ , llavors $ab^{n-1}\,{\bmod {\,}}n=a\,{\bmod {\,}}n$ , a causa del petit teorema de Fermat.
Invers:
- $((-a\,{\bmod {\,}}n)+(a\,{\bmod {\,}}n))\,{\bmod {\,}}n=0$
- $b^{-1}\,{\bmod {\,}}n$ denota l'invers multiplicatiu modular, que està definit si i només si $b$ i $n$ són coprimers, que és el cas en què el primer terme està definit: $((b^{-1}\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n=1$ .
Distributivitat:
- $(a+b)\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)+(b\,{\bmod {\,}}n))\,{\bmod {\,}}n$
- $ab\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n$
Divisió (definició): ${\frac {a}{b}}\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n$ , quan el segon terme està definit, i indefinit altrament.
Invers multiplicatiu: $((ab\,{\bmod {\,}}n)\,(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n=a\,{\bmod {\,}}n$

Notes

↑ Tal com està implementat en ACUCOBOL, Micro Focus COBOL, i possiblement altres.
↑ ^2,0 ^2,1 El divisor ha de ser positiu, altrament no està definit.
↑ Habitualment, Perl utilitza una aritmètica per al càlcul de l'operador mòdul que és independent de màquina. Vegeu la documentació de Perl per a excepcions i exemples.
↑ Des d'un punt de vista matemàtic, aquestes són només dues opcions d'entre el nombre infinit d'opcions per a la desigualtat satisfeta pel residu.

Referències

↑ «ISO/IEC 14882:2003 : Programming languages -- C++». ISO, IEC, 2003.. "l'operador binari % proporciona el residu de la divisió de la primera expressió entre la segona. [...] Si tots dos operands són no-negatius, llavors el residu és no-negatiu; altrament, el signe del residu depèn de la implementació" ((anglès) "the binary % operator yields the remainder from the division of the first expression by the second. .... If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined")
↑ open-std.org, section 6.5.5
↑ CoffeeScript operators
↑ «Expressions». D Programming Language 2.0. Digital Mars. [Consulta: 29 juliol 2010].
↑ ^5,0 ^5,1 r6rs.org
↑ «ISO/IEC 9899:1990 : Programming languages -- C». ISO, IEC, 1990.. "The fmod function returns the value x - i * y, for some integer i such that, if y is nonzero, the result as the same sign as x and magnitude less than the magnitude of y.".
↑ Knuth, Donald. E.. The Art of Computer Programming. Addison-Wesley, 1972. ISBN 0-201-89683-4.
↑ Boute, Raymond T. «The Euclidean definition of the functions div and mod». ACM Transactions on Programming Languages and Systems (TOPLAS). ACM Press (New York, NY, USA), 14, 2, abril 1992, pàg. 127–144. DOI: 10.1145/128861.128862.
↑ Leijen, Daan. «Division and Modulus for Computer Scientists» (PDF), 03-12-2001. [Consulta: 25 desembre 2014].
↑ Horvath, Adam. «Faster division and modulo operation - the power of two», 05-07-2012.

Vegeu també

[3] Tal com està implementat en ACUCOBOL, Micro Focus COBOL, i possiblement altres.

[divpos-6] 2,0 ^2,1 El divisor ha de ser positiu, altrament no està definit.

[7] Habitualment, Perl utilitza una aritmètica per al càlcul de l'operador mòdul que és independent de màquina. Vegeu la documentació de Perl per a excepcions i exemples.

[10] Des d'un punt de vista matemàtic, aquestes són només dues opcions d'entre el nombre infinit d'opcions per a la desigualtat satisfeta pel residu.

[1] «ISO/IEC 14882:2003 : Programming languages -- C++». ISO, IEC, 2003.. "l'operador binari % proporciona el residu de la divisió de la primera expressió entre la segona. [...] Si tots dos operands són no-negatius, llavors el residu és no-negatiu; altrament, el signe del residu depèn de la implementació" ((anglès) "the binary % operator yields the remainder from the division of the first expression by the second. .... If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined")

[C99-2] -std.org, section 6.5.5

[CoffeeScript-4] CoffeeScript operators

[5] «Expressions». D Programming Language 2.0. Digital Mars. [Consulta: 29 juliol 2010].

[r6rs-8] 5,0 ^5,1 r6rs.org

[9] «ISO/IEC 9899:1990 : Programming languages -- C». ISO, IEC, 1990.. "The fmod function returns the value x - i * y, for some integer i such that, if y is nonzero, the result as the same sign as x and magnitude less than the magnitude of y.".

[11] Knuth, Donald. E.. The Art of Computer Programming. Addison-Wesley, 1972. ISBN 0-201-89683-4.

[12] Boute, Raymond T. «The Euclidean definition of the functions div and mod». ACM Transactions on Programming Languages and Systems (TOPLAS). ACM Press (New York, NY, USA), 14, 2, abril 1992, pàg. 127–144. DOI: 10.1145/128861.128862.

[13] Leijen, Daan. «Division and Modulus for Computer Scientists» (PDF), 03-12-2001. [Consulta: 25 desembre 2014].

[14] Horvath, Adam. «Faster division and modulo operation - the power of two», 05-07-2012.

[1]

[2]

[nota 1]

[3]

[4]

[nota 2]

[nota 3]

[5]

[6]

[nota 4]

[7]

[8]

[9]

[10]