miniatura|Funcions quocient () i residu () 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, (el dividend) i (el divisor), a mòdul n (abreujat com ) é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 o bé 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 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ó. "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ó" ( "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") div Dividend C (ISO 1999) %, div Dividendopen-std.org, section 6.5.5 C++ (ISO 2011) %, div Dividend C# % Dividend CLARION % Dividend Clojure mod Divisor COBOLTal com està implementat en ACUCOBOL, Micro Focus COBOL, i possiblement altres. FUNCTION MOD Divisor CoffeeScript % Dividend %% DivisorCoffeeScript operators ColdFusion %, MOD Dividend Common Lisp mod Divisor rem Dividend D % Dividend 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 DivisorEl divisor ha de ser positiu, altrament no està definit. MUMPS # Divisor NASMNASMX % Operador mòdul sense signe %% Operador mòdul amb signe Oberon MOD Divisor OCaml mod Dividend Occam \ Dividend Pascal (Delphi) mod Dividend Pascal (ISO-7185 and ISO-10206) mod Sempre positiu Perl % DivisorHabitualment, 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. 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 R⁶RS mod Sempre positiur6rs.org mod0 El més pròxim a zero 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 BasicModDividend 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. "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.". 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 R⁶RS 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 i el residu de dividit per satisfà
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.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. 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 , i per tant, d'acord amb l'equació (), 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 descriu la divisió arrodonida ( floored division) on el quocient ve definit per la funció part entera , i per l'equació (), 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 descriu la definició euclidiana en la qual el residu és sempre no-negatiu, i, per tant, és consistent amb l'algorisme de divisió euclidiana. Aquesta convenció està simbolitzada per Sempre negatiu a la taula. En aquest cas,
o equivalentment
on és la funció signe, i per tant . Common Lisp també defineix la divisió arrodonida i la divisió entera per dalt ( ceiling-division), on la divisió ve donada per i respectivament. IEEE 754 defineix una funció residu on el quocient és 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,
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ó , 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 % 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.
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:
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
Referències
Vegeu també Mòdul (desambiguació) Exponenciació modular
Categoria:Informàtica teòrica Categoria:Aritmètica modular Categoria:Teoria d'anells