Modulo (provoz)
Ve vědě o počítačích je operace modulo , nebo mod operace , je binární operace, která se spojuje s dvěma přírodními celých čísel zbytkových z euklidovské rozdělení prvního do druhého, zbytek dělení o n ( n * 0) se označuje se mod n ( a % n v některých počítačových jazycích). Tedy 9 mod 4 = 1, protože 9 = 2 × 4 + 1 a 0 ≤ 1 <4, 9 mod 3 = 0,… Operaci lze rozšířit na relativní celá čísla nebo dokonce na reálná čísla, Ale pak se programovací jazyky mohou rozcházet, zejména v mod n není nutně pozitivní nebo nula.
V matematice je použití termínu modulo odlišné, i když je spojeno: neurčuje operaci, ale zasahuje do charakterizace kongruenčního vztahu na celá čísla (a obecněji pro jiné kongruence); přidružené klíčové slovo mod se nejčastěji používá pouze k označení této kongruence, ačkoli práce jako Concrete Mathematics ji také používá k označení binární operace.
Tři definice funkce modulo
V praxi lze x mod y vypočítat pomocí jiných funkcí. Berouce na vědomí:
X=⌊X⌋+{X}{\ displaystyle x = \ lfloor x \ rfloor + \ {x \}}Se v dolní
celou část a nepatrná část,
⌊X⌋{\ displaystyle \ lfloor x \ rfloor}{X}{\ displaystyle \ {x \}}my máme :
Namodne=Na-(⌊Na/ne⌋×ne){\ displaystyle a {\ bmod {n}} = a - (\ lfloor a / n \ rfloor \ krát n)}.
Například 9 mod 4 = 9 - ⌊9 / 4⌋ × 4 = 9-2 × 4 = 1.
Rozdíly se objevují v závislosti na typech použitých proměnných, které v běžných implementacích obsahují celočíselný typ. Hlavní rozdíl však spočívá ve výkladu celé části kvocientu v závislosti na znaménku dividendy nebo znaménka dělitele, pokud mohou být záporné:
Použití celočíselné části (matematická definice)
E(z)(také uvedeno ) je největší celé číslo menší nebo rovno z .
⌊z⌋{\ displaystyle \ lfloor z \ rfloor}Operátor mod poté vrátí modulo vždy mezi 0 (zahrnuto) a dělitelem y (vyloučeno) a má stejné znaménko jako dělitel y :
X mod y=X - y×E(Xy){\ displaystyle x \ {\ bmod {\}} y = x \ - \ y \ krát E {\ begin {pmatrix} {\ frac {x} {y}} \ end {pmatrix}}}Dividenda |
Rozdělovač |
Kvocient |
Pobyt
|
---|
117 |
17 |
6 |
15
|
–117 |
17 |
–7 |
2
|
–117 |
–17 |
6 |
–15
|
117 |
–17 |
–7 |
–2
|
12.7 |
3.5 |
3 |
2.2
|
Tato definice splňuje zákony modulo aritmetiky plus: x mod - y = - ((- x ) mod y ). Je vhodný pro cyklické výpočty (například kalendář). Vrácená modulární hodnota je vždy znaménkem dělitele (dělitel je kladný ve většině cyklických výpočtů, včetně výpočtů kalendáře).
Použití funkce zkrácení desetinné části (programování aproximace)
x % y = x - y * iPart(x / y)
Například :
Dividenda |
Rozdělovač |
Kvocient |
Pobyt
|
---|
117 |
17 |
6 |
15
|
–117 |
17 |
–6 |
–15
|
–117 |
–17 |
6 |
–15
|
117 |
–17 |
–6 |
15
|
Modulo má stejné znaménko jako levý operand.
Tato definice ověřuje zákon: x mod - y = x mod y . Porušuje zákon ( x + n ) mod n = x mod n .
Srovnání v tabulkové formě
srovnání operátorů Modulo
|
def. matematický |
zkrácení |
funkční euklidovský
|
---|
Dividenda |
Rozdělovač |
Kvocient |
Pobyt |
Kvocient |
Pobyt |
|
Pobyt
|
---|
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
|
Chování s necelými operandy
Všechny tři definice umožňují x a y být záporná celá čísla nebo racionální čísla (nebo reálná čísla v matematice, i když počítačové numerické výpočetní systémy vědí, jak pracovat pouze na podmnožině racionálních čísel, kvůli přesnosti omezení).
V C, C ++, PHP a mnoha jazycích však operátor modnebo %operuje pouze na celočíselných typech. V závislosti na jazyce jsou numerické typy někdy implicitně převedeny na celá čísla ( donucením ).
Chování programovacích jazyků
Následující jazyky používají matematickou definici (1.)
-
Perl : $a % $nje definován na celá čísla; skutečné operandy jsou zkráceny na 0 nátlakem ;
-
Visual Basic : a Mod nje definován na reálných a celých číslech a vrací celé číslo, pokud jsou oba operandy celá čísla;
-
Pascal (ISO 7185): povoluje a mod npouze celočíselné operandy a nmusí být přísně pozitivní;
-
Excel : MOD(a;n)pracuje na reálných číslech;
-
Jazyk Python : Nejčastější dotazy vysvětlují tuto volbu na následujícím příkladu:
„Pokud hodiny říkají 10 hodin, co řekly 200 hodin předtím?“ -190 % 12 == 2Je užitečné; -190 % 12 == -10je chyba připravená kousnout. "
Následující jazyky používají definici (2.)
-
Free Pascal a Delphi povolují pouze celé operandy a definice jazyka specifikuje: "Znaménko výsledku je znaménko levého operandu";
-
C , C ++ : a % npožadovat celočíselné operandy;
-
Java : a % numožňuje skutečné operandy;
-
Javascript : a % numožňuje skutečné operandy;
-
PHP : $a % $nje definován na celá čísla a vrátí výsledek se stejným znaménkem jako $a ;
-
Scilab : modulo(a, n)přijímá reálná čísla.
Hodnota modulo 0 (hodnota „nula“)
Ve většině jazyků operace modulo nevytvoří žádný výsledek, pokud je dělitel nulový a vygeneruje se dělení nulou aritmetickou výjimkou.
Rovnocennost
Modulové operace lze zmenšit nebo rozšířit stejným způsobem jako jiné matematické operace.
- Identita:
- (Namodne)modne=Namodne{\ displaystyle (a \, {\ bmod {\,}} n) \, {\ bmod {\,}} n = a \, {\ bmod {\,}} n}
-
neXmodne=0{\ displaystyle n ^ {x} \, {\ bmod {\,}} n = 0}pro všechna přísně kladná celá čísla .X{\ displaystyle x}
- Pokud je prvočíslo , které není dělitel of a pak , podle k Malá Fermatova věta .ne{\ displaystyle n}b{\ displaystyle b}Nabne-1modne=Namodne{\ displaystyle ab ^ {n-1} \, {\ bmod {\,}} n = a \, {\ bmod {\,}} n}
- Zvrátit:
- ((-Namodne)+(Namodne))modne=0{\ displaystyle ((-a \, {\ bmod {\,}} n) + (a \, {\ bmod {\,}} n)) \, {\ bmod {\,}} n = 0}
-
b-1modne{\ displaystyle b ^ {- 1} \, {\ bmod {\,}} n}je modulární inverze , který je nastaven, jestliže a pouze v případě, a jsou coprime , což je případ, kdy je levá část definovanou: .b{\ displaystyle b}ne{\ displaystyle n}((b-1modne)(bmodne))modne=1{\ displaystyle ((b ^ {- 1} \, {\ bmod {\,}} n) \, (b \, {\ bmod {\,}} n)) \, {\ bmod {\,}} n = 1}
- Distribuce:
- (Na+b)modne=((Namodne)+(bmodne))modne{\ displaystyle (a + b) \, {\ bmod {\,}} n = ((a \, {\ bmod {\,}} n) + (b \, {\ bmod {\,}} n) ) \, {\ bmod {\,}} n}
- Nabmodne=((Namodne)(bmodne))modne{\ displaystyle ab \, {\ bmod {\,}} n = ((a \, {\ bmod {\,}} n) \, (b \, {\ bmod {\,}} n)) \, {\ bmod {\,}} n}
- Odkud : Na2modne=(Namodne)2modne{\ displaystyle a ^ {2} \, {\ bmod {\,}} n = (a \, {\ bmod {\,}} n) ^ {2} \, {\ bmod {\,}} n}
- Dělení (definice) :, když je definován levý operand. Není definováno jinak.Nabmodne=((Namodne)(b-1modne))modne{\ displaystyle {\ frac {a} {b}} \, {\ bmod {\,}} n = ((a \, {\ bmod {\,}} n) (b ^ {- 1} \, { \ bmod {\,}} n)) \, {\ bmod {\,}} n}
- Obrácené násobení: ((Nabmodne)(b-1modne))modne=Namodne{\ displaystyle ((ab \, {\ bmod {\,}} n) \, (b ^ {- 1} \, {\ bmod {\,}} n)) \, {\ bmod {\,}} n = a \, {\ bmod {\,}} n}
Aplikace
Operace modulo umožňuje provádět kruhový posun indexů. Pokud vezmeme v úvahu posloupnost souvislých celých čísel od 1 do n , u = (1, 2, 3,…, n - 1, n ), můžeme se posunout o p řady s:
u ' i = (( u i + p - 1) mod n ) + 1.
Například posunout sekvenci o dvě (1, 2, 3, 4, 5):
u ' i = (( u i + 1) mod 5) + 1;
my máme:
-
u ' 1 = (((1 + 1) mod 5) + 1 = 3
-
u ' 2 = (((2 + 1) mod 5) + 1 = 4
- ...
-
u ' 4 = (((4 + 1) mod 5) + 1 = 1
a proto u ' = (3, 4, 5, 1, 2).
Poznámky a odkazy
-
Ronald Graham, Donald Knuth a Oren Patashnik ( překlad Alain Denise), Concrete Mathematics: Foundations for Computer Science , Paris, Vuibert ,2003, 2 nd ed. , xiv + 688 str. ( ISBN 978-2-7117-4824-2 ), str. 88-89.
-
Raymond T. Boute , „ Euklidovská definice funkcí div a mod “, ACM Transaction on Programming Languages and Systems , ACM Press (New York, NY, USA), sv. 1, n O 2Dubna 1992, str. 127–144 ( DOI 10.1145 / 128861.128862 , číst online ), str. 128-129.
-
Graham, Knuth a Patashnik 2003 , str. 89 a okrajová poznámka str. 88.
-
Graham, Knuth a Patashnik 2003 , str. 88-89, pro binární operaci, str.143 pro kongruenci. Autoři používají pouze pojem modulo pro kongruenční vztah, ale binární operaci nazývají „mod“.
-
„Proč -22 // 10 vrací -3?“
-
(in) Michaël Van Canneyt, „ Referenční příručka pro Free Pascal verze 2.6.0 “ ,prosince 2011.
-
Od ISO C99. V ISO C90 byla v případě záporného operandu znaménko výsledku definováno implementací.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">