Modulo (käyttö)

In Computer Science , The modulo-operaation , tai mod toiminta , on binaarinen laskutoimitus, joka assosioituu kaksi luonnollista kokonaislukua loput on jakoyhtälö ensimmäisen toisen, loput jako mukaan n ( n ≠ 0) on merkitty mod n ( a % n joillakin tietokonekielillä). Siten 9 mod 4 = 1, koska 9 = 2 × 4 + 1 ja 0 ≤ 1 <4, 9 mod 3 = 0, ... Operaatio voidaan laajentaa suhteellisiin kokonaislukuihin tai jopa reaalilukuihin , Mutta sitten ohjelmointikieliä voi poiketa, erityisesti mod n ei ole enää välttämättä positiivinen tai nolla.

Vuonna matematiikan käyttö termi modulo on erilainen, vaikka se liittyy: se ei nimetä operaation mutta ensimmäisten toimenpiteiden luonnehtimaan kongruenssi suhde on kokonaislukuja (ja yleisemmin muiden congruences); siihen liittyvää mod- avainsanaa käytetään useimmiten vain tämän yhtäläisyyden merkitsemiseen, vaikka konkreettisen matematiikan kaltainen työ käyttää sitä myös binaaritoiminnon merkitsemiseen.

Kolme modulo-funktion määritelmää

Käytännössä x mod y voidaan laskea käyttämällä muita toimintoja. Täten toteaa:

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

, Jossa alempi koko osa ja murto-osa,

\ lfloor x \ rfloor

{\ displaystyle \ {x \}}

meillä on :

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

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

Erot näkyvät käytettyjen muuttujien tyyppien mukaan, jotka sisältävät kokonaislukutyypin tavallisissa toteutuksissa. Mutta suurin ero on osamäärän kokonaisluvun tulkinnassa riippuen osingon merkistä tai jakajan merkistä, kun nämä voivat olla negatiivisia:

Lukuosan käyttö (matemaattinen määritelmä)

E(z)(huomattu myös ) on suurin kokonaisluku, joka on pienempi tai yhtä suuri kuin z .

\ lfloor z \ rfloor

Mod-operaattori palauttaa sitten moduulin aina 0: n (sisältyy) ja jakajan y (poissuljettu) väliin ja jolla on sama merkki kuin jakajalla y :

{\ displaystyle x \ {\ bmod {\}} y = x \ - \ y \ kertaa E {\ alkaa {pmatrix} {\ frac {x} {y}} \ end {pmatrix}}}

Osinko	Jakaja	Osamäärä	Pysyä
117	17	6	15
–117	17	–7	2
–117	–17	6	–15
117	–17	–7	–2
12.7	3.5	3	2.2

Tämän määritelmän täyttää lakien moduloaritmetiikkaa lisäksi: X mod - y = - ((- x ) mod y ). Se soveltuu syklisiin laskelmiin (esimerkiksi kalenteri). Palautettu modulaarinen arvo on aina jakajan merkki (jakaja on positiivinen useimmissa syklisissä laskelmissa, mukaan lukien kalenterilaskelmat).

'Desimaaliosan katkaisu' -toiminnon käyttäminen (likiarvon ohjelmointi)

x % y = x - y * iPart(x / y) Esimerkiksi :

Osinko	Jakaja	Osamäärä	Pysyä
117	17	6	15
–117	17	–6	–15
–117	–17	6	–15
117	–17	–6	15

Modulolla on sama merkki kuin vasemmalla operandilla.

Tämä määritelmä varmistaa lain: x mod - y = x mod y . Se rikkoo lakia ( x + n ) mod n = x mod n .

Vertailu taulukkomuodossa

Modulo-operaattoreiden vertailu

		def. matemaattinen		katkaisu
Osinko	Jakaja	Osamäärä	Pysyä	Osamäärä	Pysyä	Pysyä
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

Käyttäytyminen ei-kokonaislukuisten operandien kanssa

Kaikki kolme määritelmää sallivat x: n ja y : n olla negatiivisia kokonaislukuja tai rationaalilukuja (tai reaalilukuja matematiikassa, vaikka atk-numeeriset laskentajärjestelmät tietävätkin, kuinka työskennellä rationaalilukujen osajoukolla rajoitusten tarkkuuden vuoksi).

Operaattori modtai operaattori C tai C ++, PHP ja monilla kielillä %toimii kuitenkin vain kokonaislukutyypeillä. Kielestä riippuen numeeriset tyypit muunnetaan toisinaan implisiittisesti kokonaislukuiksi ( pakottamalla ).

Ohjelmointikielien käyttäytyminen

Seuraavat kielet käyttävät matemaattista määritelmää (1.)

Perl : $a % $nmääritetään kokonaisluvuille; todelliset operandit katkaistaan kohti 0 pakottamalla ;
Visual Basic : a Mod nmääritetään reaaleissa ja kokonaisluvuissa ja palauttaa kokonaisluvun, jos molemmat operandit ovat kokonaislukuja;
Pascal (ISO 7185): a mod nhyväksyy vain kokonaisluvuoperandit, ja sen non oltava ehdottomasti positiivinen;
Excel : MOD(a;n)toimii todellisilla numeroilla;
Python-kieli : UKK selittää tämän valinnan seuraavalla esimerkillä:

"Jos kello sanoo kello 10, mitä se sanoi 200 tuntia ennen?" -190 % 12 == 2On hyödyllinen; -190 % 12 == -10on vika valmis puremaan. "

Seuraavat kielet käyttävät määritelmää (2.)

Vapaa Pascal ja Delphi sallivat vain kokonaiset operandit, ja kielimääritelmä täsmentää: "Tuloksen merkki on vasemman operandin merkki";
C , C ++ : a % npyydä kokonaislukuoperandeja;
Java : a % nsallii todelliset operandit;
Javascript : a % nsallii oikeat operandit;
PHP : $a % $nmääritetään kokonaisluvuille ja palauttaa tuloksen samalla merkillä kuin $a ;
Scilab : modulo(a, n)hyväksyy todelliset luvut.

Moduulin arvo 0 (arvo 'nolla')

Useimmilla kielillä modulo- operaatio ei tuota tulosta, jos jakaja on nolla, ja jako nollalla aritmeettinen poikkeus syntyy.

Vastaavuus

Modulotoimintoja voidaan pienentää tai laajentaa samalla tavalla kuin muita matemaattisia operaatioita.

Henkilöllisyys:
- $(a \, {\ bmod \,} n) \, {\ bmod \,} n = a \, {\ bmod \,} n$
- $n ^ {x} \, {\ bmod \,} n = 0$ kaikille ehdottomasti positiivisille kokonaisluvuille . $x$
- Jos on alkuluku , joka ei ole jakaja on , sitten mukaan Fermat'n pieni lause . $ei$ $b$ $ab ^ {{n-1}} \, {\ bmod \,} n = a \, {\ bmod \,} n$
Käänteinen:
- $((-a \, {\ bmod \,} n) + (a \, {\ bmod \,} n)) \, {\ bmod \,} n = 0$
- $b ^ {{- 1}} \, {\ bmod \,} n$ on modulaarinen käänteinen , joka asetetaan, jos ja vain jos , ja ovat keskenään jaottomia , joka on silloin, kun osan vasemmalta on määritelty: . $b$ $ei$ $((b ^ {{- 1}} \, {\ bmod \,} n) \, (b \, {\ bmod \,} n)) \, {\ bmod \,} n = 1$
Jakelukyky:
- $(a + b) \, {\ bmod \,} n = ((a \, {\ bmod \,} n) + (b \, {\ bmod \,} n)) \, {\ bmod \,} ei$
- $ab \, {\ bmod \,} n = ((a \, {\ bmod \,} n) \, (b \, {\ bmod \,} n)) \, {\ bmod \,} n$
- Mistä : ${\ displaystyle a ^ {2} \, {\ bmod {\,}} n = (a \, {\ bmod {\,}} n) ^ {2} \, {\ bmod {\,}} n}$
Jako (määritelmä) :, kun vasen operandi on määritelty. Ei määritelty toisin. ${\ frac {a} {b}} \, {\ bmod \,} n = ((a \, {\ bmod \,} n) (b ^ {{- 1}} \, {\ bmod \,} n)) \, {\ bmod \,} n$
Käänteinen kertolasku: $((ab \, {\ bmod \,} n) \, (b ^ {{- 1}} \, {\ bmod \,} n)) \, {\ bmod \,} n = a \, {\ bmod \,} n$

Sovellukset

Modulotoiminto mahdollistaa indeksien pyöreän siirron. Todellakin, jos tarkastellaan vierekkäisten kokonaislukujen järjestystä 1: stä n: ään , u = (1, 2, 3,…, n - 1, n ), voimme siirtyä p- riveillä:

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

Esimerkiksi sekvenssin siirtäminen kahdella (1, 2, 3, 4, 5):

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

meillä on:

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

ja siksi u ' = (3, 4, 5, 1, 2).

Huomautuksia ja viitteitä

Ronald Graham, Donald Knuth ja Oren Patashnik ( käännös Alain Denise) , Betonimatematiikka : Tietotekniikan perusteet , Pariisi, Vuibert ,2003, 2 nd ed. , xiv + 688 Sivumäärä ( ISBN 978-2-7117-4824-2 ), s. 88-89.
Raymond T. Boute , " Funktioiden div ja mod euklidinen määritelmä ", ACM Transactions on Programming Languages and Systems , ACM Press (New York, NY, USA), voi. 1, n o 2Huhtikuu 1992, s. 127–144 ( DOI 10.1145 / 128861.128862 , lue verkossa ), s. 128 - 129.
Graham, Knuth ja Patashnik 2003 , s. 89 ja reunanumero s. 88.
Graham, Knuth ja Patashnik 2003 , s. 88–89, binääritoimintoa varten, s. 143 kongruenssia varten. Kirjoittajat käyttävät vain termiä modulo kongruenssisuhteeseen, mutta kutsuvat binääritoimintoa "mod".
"Miksi -22 // 10 palauttaa -3?"
(in) Michaël Van Canneyt, " Viiteoppaan Free Pascal versio 2.6.0 " ,joulukuu 2011.
Koska ISO C99. ISO C90 -standardissa negatiivisen operandin tapauksessa tuloksen merkki määritettiin toteutuksen avulla.