Modulo (drift)

Inden for datalogi er modulo-operationen , eller mod operation , er en binær operation, som associerer med to naturlige heltal den resten af den euklidiske division af den første af den anden, den resterende del af opdelingen af en af n ( n er ≠ 0) betegnes en mod n ( a % n på nogle computersprog). Således er 9 mod 4 = 1, fordi 9 = 2 × 4 + 1 og 0 ≤ 1 <4, 9 mod 3 = 0, ... Operationen kan udvides til relative heltal eller endda til reelle tal, men så kan programmeringssprogene afvige, især er et mod n ikke længere nødvendigvis positivt eller nul.

I matematik er brugen af udtrykket modulo forskellig, selvom det er forbundet: det betegner ikke en operation, men griber ind for at karakterisere en kongruensrelation på heltal (og mere generelt for andre kongruenser); det tilknyttede mod- nøgleord bruges oftest kun til at betegne denne kongruens, selvom et værk som Concrete Mathematics også bruger det til at betegne den binære operation.

Tre definitioner af modulo-funktionen

I praksis kan x mod y beregnes ved hjælp af andre funktioner. Således bemærker:

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

, med den nederste hele del og den brøkdel,

\ lfloor x \ rfloor

{\ displaystyle \ {x \}}

vi har :

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

For eksempel 9 mod 4 = 9 - ⌊9 / 4⌋ × 4 = 9 - 2 × 4 = 1.

Forskelle vises afhængigt af de anvendte variabler, som indeholder heltalstypen i almindelige implementeringer. Men den største forskel ligger i fortolkningen af kvotientens heltal afhængigt af tegnet på udbyttet eller deleren, når disse kan være negative:

Brug af heltal (matematisk definition)

E(z)(også bemærket ) er det største heltal mindre end eller lig med z .

\ lfloor z \ rfloor

Modoperatoren returnerer derefter en modulo altid mellem 0 (inkluderet) og divisoren y (ekskluderet), og som har det samme tegn som divisoren y :

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

Udbytte	Opdeler	Kvotient	Bliv
117	17	6	15
–117	17	–7	2
–117	–17	6	–15
117	–17	–7	–2
12.7	3.5	3	2.2

Denne definition opfylder lovene for modulo-aritmetik plus: x mod - y = - ((- - x ) mod y ). Det er velegnet til cykliske beregninger (for eksempel kalender). Den returnerede modulværdi er altid tegnet på divisoren (divisoren er positiv i de fleste cykliske beregninger, inklusive kalenderberegninger).

Brug af funktionen 'decimal del trunkering' (programmering tilnærmelse)

x % y = x - y * iPart(x / y) For eksempel :

Udbytte	Opdeler	Kvotient	Bliv
117	17	6	15
–117	17	–6	–15
–117	–17	6	–15
117	–17	–6	15

Modulen har samme tegn som den venstre operand.

Denne definition verificerer loven: x mod - y = x mod y . Det overtræder loven ( x + n ) mod n = x mod n .

Sammenligning i tabelform

sammenligning af Modulo-operatører

		def. matematisk		trunkering
Udbytte	Opdeler	Kvotient	Bliv	Kvotient	Bliv	Bliv
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

Adfærd med ikke-heltal operander

Alle tre definitioner tillader, at x og y er negative heltal eller rationelle tal (eller reelle tal i matematik, selvom computerens numeriske beregningssystemer kun ved, hvordan man arbejder på en delmængde af rationelle tal på grund af begrænsningspræcision).

Men i C, C ++, PHP og mange sprog fungerer operatøren modeller %kun på heltalstyper. Afhængigt af sproget konverteres numeriske typer undertiden implicit til heltal (ved tvang ).

Opførsel af programmeringssprog

Følgende sprog bruger den matematiske definition (1.)

Perl : $a % $ner defineret på heltal; de virkelige operander afkortes mod 0 ved tvang ;
Visual Basic : a Mod ndefineres på reelle og på heltal og returnerer et heltal, hvis begge operander er heltal;
Pascal (ISO 7185): a mod ntillader kun heltalsoperander og nskal være strengt positive;
Excel : MOD(a;n)fungerer på reelle tal;
Python-sprog : Ofte stillede spørgsmål forklarer dette valg med følgende eksempel:

"Hvis et ur siger klokken 10, hvad sagde det 200 timer før?" -190 % 12 == 2Er nyttigt; -190 % 12 == -10er en fejl klar til at bide. "

Følgende sprog bruger definition (2.)

Gratis Pascal og Delphi tillader kun hele operander, og sprogdefinitionen specificerer: "Tegnet på resultatet er tegn på venstre operand";
C , C ++ : a % nanmoder heltal operander;
Java : a % ntillader rigtige operander;
Javascript : a % ntillader rigtige operander;
PHP : $a % $ner defineret på heltal og returnerer et resultat med samme tegn som $a ;
Scilab : modulo(a, n)accepterer reelle tal.

Værdi af en modulo 0 (værdi 'nul')

På de fleste sprog genererer modulo- operationen intet resultat, hvis divisoren er nul, og der genereres en opdeling med nul aritmetisk undtagelse.

Ækvivalens

Modulo-operationer kan reduceres eller udvides på samme måde som andre matematiske operationer.

Identitet:
- $(a \, {\ bmod \,} n) \, {\ bmod \,} n = a \, {\ bmod \,} n$
- $n ^ {x} \, {\ bmod \,} n = 0$ for alle strengt positive heltal . $x$
- Hvis er et primtal som ikke er en divisor af , derefter , efter at Fermats lille sætning . $ikke$ $b$ $ab ^ {{n-1}} \, {\ bmod \,} n = a \, {\ bmod \,} n$
Baglæns:
- $((-a \, {\ bmod \,} n) + (a \, {\ bmod \,} n)) \, {\ bmod \,} n = 0$
- $b ^ {{- 1}} \, {\ bmod \,} n$ er den modulære inverse , som er sat, hvis og kun hvis og er indbyrdes primiske , hvilket er tilfældet, når den venstre del er defineret: . $b$ $ikke$ $((b ^ {{- 1}} \, {\ bmod \,} n) \, (b \, {\ bmod \,} n)) \, {\ bmod \,} n = 1$
Distributivitet:
- $(a + b) \, {\ bmod \,} n = ((a \, {\ bmod \,} n) + (b \, {\ bmod \,} n)) \, {\ bmod \,} ikke$
- $ab \, {\ bmod \,} n = ((a \, {\ bmod \,} n) \, (b \, {\ bmod \,} n)) \, {\ bmod \,} n$
- Hvorfra : ${\ displaystyle a ^ {2} \, {\ bmod {\,}} n = (a \, {\ bmod {\,}} n) ^ {2} \, {\ bmod {\,}} n}$
Opdeling (definition) : når venstre operand er defineret. Ikke defineret på anden måde. ${\ frac {a} {b}} \, {\ bmod \,} n = ((a \, {\ bmod \,} n) (b ^ {{- 1}} \, {\ bmod \,} n)) \, {\ bmod \,} n$
Omvendt multiplikation: $((ab \, {\ bmod \,} n) \, (b ^ {{- 1}} \, {\ bmod \,} n)) \, {\ bmod \,} n = a \, {\ bmod \,} n$

Ansøgninger

Moduloperationen gør det muligt at udføre et cirkulært skift af indekser. Faktisk, hvis vi betragter rækkefølgen af sammenhængende heltal fra 1 til n , u = (1, 2, 3, ..., n - 1, n ), så kan vi skifte med p rækker med:

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

For eksempel at skifte sekvensen med to (1, 2, 3, 4, 5):

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

vi har:

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

og derfor er u ' = (3, 4, 5, 1, 2).

Noter og referencer

Ronald Graham, Donald Knuth og Oren Patashnik ( overs. Alain Denise), Concrete Mathematics: Foundations for Computer Science , Paris, Vuibert ,2003, 2 nd ed. , xiv + 688 s. ( ISBN 978-2-7117-4824-2 ), s. 88-89.
Raymond T. Boute , " Den euklidiske definition af funktionerne div og mod ", ACM-transaktioner på programmeringssprog og -systemer , ACM Press (New York, NY, USA), bind. 1, nr . 2April 1992, s. 127–144 ( DOI 10.1145 / 128861.128862 , læs online ), s. 128-129.
Graham, Knuth og Patashnik 2003 , s. 89 og randnote s. 88.
Graham, Knuth og Patashnik 2003 , s. 88-89, for den binære operation, s.143 for kongruensen. Forfatterne bruger kun udtrykket modulo for kongruensrelationen, men kalder den binære operation "mod".
"Hvorfor returnerer -22 // 10 -3?"
(in) Michaël Van Canneyt, " Referencevejledning til gratis Pascal version 2.6.0 " ,december 2011.
Siden ISO C99. I ISO C90, i tilfælde af en negativ operand, blev tegnet på resultatet defineret af implementeringen.