Operació mòdul

De Viquipèdia
Salta a: navegació, cerca
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 dóna 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[modifica | modifica el codi]

Operadors mòdul enters en diversos llenguatges de programació
Llenguatge Operador El resultat té el mateix signe que el...
ActionScript % Dividend
Ada mod Divisor
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ó
div Dividend
C++ (ISO 1998) % Segons la implementació[1]
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
%% Divisor[3]
ColdFusion %, MOD Dividend
Common Lisp mod Divisor
rem Dividend
D % Dividend[4]
Dart % Sempre positiu
remainder() Dividend
Eiffel \\ Dividend
Erlang rem Dividend
Euphoria mod Divisor
remainder Dividend
F# % Dividend
FileMaker Mod Divisor
Forth mod Segons la implementació
Fortran mod Dividend
modulo Divisor
Frink mod Divisor
GML (Game Maker) mod Dividend
GDScript % Dividend
Go % Dividend
Haskell mod Divisor
rem Dividend
Haxe % Dividend
J |~ Divisor
Java % Dividend
Math.floorMod Divisor
JavaScript % Dividend
Julia mod Divisor
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
rem Dividend
Maxima mod Divisor
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
%% 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
rem Dividend
Python % Divisor
math.fmod Dividend
Racket remainder Dividend
RealBasic MOD Dividend
R %% Divisor
REXX // Dividend
RPG %REM Dividend
Ruby %, modulo() Divisor
remainder() Dividend
Rust % Dividend
Scala % Dividend
Scheme modulo Divisor
remainder Dividend
Scheme R6RS mod Sempre positiu[5]
mod0 El més pròxim a zero[5]
Seed7 mod Divisor
rem Dividend
SenseTalk modulo Divisor
rem Dividend
Smalltalk \\ Divisor
rem: Dividend
SQL (SQL:1999) mod(x,y) Dividend
Standard ML mod Divisor
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
rem Dividend
Visual Basic Mod Dividend
Xbase++ % Dividend
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
remainder El més pròxim a zero
C++ (ISO 1998) std::fmod Dividend
C++ (ISO 2011) std::fmod Dividend
std::remainder El més pròxim a zero
C# % Dividend
Common Lisp mod Divisor
rem Dividend
D % Dividend
Dart % Sempre positiu
remainder() Dividend
F# % Dividend
Fortran mod Dividend
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
math.fmod Dividend
REXX // Dividend
Ruby %, modulo() Divisor
remainder() Dividend
Scheme R6RS flmod Sempre positiu
flmod0 El més pròxim a zero
Standard ML Real.rem Dividend
Swift % Dividend
Xbase++ % Dividend
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à

 

 

 

 

(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.
  • 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 tant d'acord amb 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.
  • Raymond T. Boute[8] descriu la definició euclidiana en la qual el residu és sempre no-negatiu, 0 ≤ r, i per tant és consistent amb l'algorisme de divisió euclidiana. Aquesta convenció està simbolitzada per Sempre positiu a la taula. En aquest cas,
o equivalentment
on sgn és la funció signe, i per tant
.
  • 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[modifica | modifica el codi]

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 dóna 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[modifica | modifica el codi]

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[modifica | modifica el codi]

É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 % 2n == x & (2n - 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[modifica | modifica el codi]

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:
    • per a tots els valors enters positius de .
    • Si és un nombre primer que no és un divisor de , llavors , a causa del petit teorema de Fermat.
  • Invers:
    • denota l'invers multiplicatiu modular, que està definit si i només si i són coprimers, que és el cas en què el primer terme està definit: .
  • Distributivitat:
  • Divisió (definició): , quan el segon terme està definit, i indefinit altrament.
  • Invers multiplicatiu:

Notes[modifica | modifica el codi]

  1. Tal com està implementat en ACUCOBOL, Micro Focus COBOL, i possiblement altres.
  2. 2,0 2,1 El divisor ha de ser positiu, altrament no està definit.
  3. 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.
  4. 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[modifica | modifica el codi]

  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")
  2. open-std.org, section 6.5.5
  3. CoffeeScript operators
  4. «Expressions». D Programming Language 2.0. Digital Mars. [Consulta: 29 juliol 2010].
  5. 5,0 5,1 r6rs.org
  6. «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.".
  7. Knuth, Donald. E.. The Art of Computer Programming. Addison-Wesley, 1972. ISBN 0-201-89683-4. 
  8. 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.
  9. Leijen, Daan. «Division and Modulus for Computer Scientists» (PDF), 03-12-2001. [Consulta: 25 desembre 2014].
  10. Horvath, Adam. «Faster division and modulo operation - the power of two», 05-07-2012.

Vegeu també[modifica | modifica el codi]