Operare Modulo - Modulo operation

În calcul , operația modulo returnează restul sau restul semnat al unei diviziuni , după ce un număr este împărțit la altul (numit modulul operației).

Având în vedere două numere pozitive a și n , un modulo n (abreviat ca un mod n ) este restul diviziunii euclidiană a unui de n , unde a este dividendul și n este împărțitor . Operația modulo se distinge de simbolul mod , care se referă la modulul (sau divizorul) din care funcționează.

De exemplu, expresia „5 mod 2” s-ar evalua la 1, deoarece 5 împărțit la 2 are un coeficient de 2 și un rest de 1, în timp ce „9 mod 3” ar evalua la 0, deoarece împărțirea lui 9 la 3 are un coeficient de 3 și un rest de 0; nu este nimic de scăzut din 9 după înmulțirea de 3 ori 3.

Deși de obicei efectuate cu a și n ambele fiind numere întregi , multe sisteme de calcul permit acum alte tipuri de operanzi numerici. Gama de valori pentru o operație modulo întreagă de n este de la 0 la n - 1 inclusiv ( un mod 1 este întotdeauna 0; un mod 0 este nedefinit, rezultând posibil o eroare de divizare la zero în unele limbaje de programare ). Vezi Aritmetica modulară pentru o convenție mai veche și conexă aplicată în teoria numerelor .

Când exact unul dintre a sau n este negativ, definiția naivă se descompune și limbajele de programare diferă în ceea ce privește modul în care sunt definite aceste valori.

Variante ale definiției

În matematică , rezultatul operației modulo este o clasă de echivalență și orice membru al clasei poate fi ales ca reprezentant ; totuși, reprezentantul obișnuit este cel mai mic reziduu pozitiv , cel mai mic întreg non-negativ care aparține acelei clase (adică restul diviziunii euclidiene ). Cu toate acestea, sunt posibile și alte convenții. Calculatoarele și calculatoarele au diverse modalități de stocare și reprezentare a numerelor; astfel, definiția lor a operației modulo depinde de limbajul de programare sau de hardware-ul de bază .

În aproape toate sistemele de calcul, coeficientul q și restul r a a împărțit la n îndeplinesc următoarele condiții:

${\ displaystyle {\ begin {align} q \, & \ in \ mathbb {Z} \\ a \, & = nq + r \\ | r | & <| n | \ end {align}}}$

( 1 )

Cu toate acestea, acest lucru lasă încă un semn de ambiguitate dacă restul este diferit de zero: apar două opțiuni posibile pentru restul, una negativă și cealaltă pozitivă și două opțiuni posibile pentru coeficient. În teoria numerelor, restul pozitiv este întotdeauna ales, dar în calcul, limbajele de programare aleg în funcție de limbă și semnele lui a sau n . Standardul Pascal și ALGOL 68 , de exemplu, dau un rest pozitiv (sau 0) chiar și pentru divizorii negativi, iar unele limbaje de programare, cum ar fi C90, îl lasă în aplicare dacă oricare dintre n sau a este negativ (vezi tabelul de la § În limbaje de programare pentru detalii). un modulo 0 este nedefinit în majoritatea sistemelor, deși unii îl definesc ca un .

După cum a descris Leijen,

Boute susține că diviziunea euclidiană este superioară celorlalte în ceea ce privește regularitatea și proprietățile matematice utile, deși diviziunea la etaj, promovată de Knuth, este, de asemenea, o bună definiție. În ciuda utilizării sale pe scară largă, diviziunea trunchiată se arată a fi inferioară celorlalte definiții.

-  Daan Leijen, Divizia și modulul pentru informaticieni

Cu toate acestea, diviziunea trunchiată satisface identitatea . ${\ displaystyle (-a) / b = - (a / b) = a / (- b)}$

Notaţie

Unele calculatoare au un buton funcție mod () și multe limbaje de programare au o funcție similară, exprimată ca mod ( a , n ) , de exemplu. Unele acceptă, de asemenea, expresii care utilizează „%”, „mod” sau „Mod” ca operator modul sau rest , cum ar fi a % nsau a mod n.

Pentru medii lipsite de o funcție similară, se poate utiliza oricare dintre cele trei definiții de mai sus.

Capcane comune

Când rezultatul unei operații modulo are semnul dividendului (definiție trunchiantă), poate duce la greșeli surprinzătoare.

De exemplu, pentru a testa dacă un număr întreg este impar , s-ar putea fi înclinat să testăm dacă restul cu 2 este egal cu 1:

bool is_odd(int n) {
    return n % 2 == 1;
}

Dar într-un limbaj în care modulul are semnul dividendului, acest lucru este incorect, deoarece atunci când n (dividendul) este negativ și impar, n mod 2 returnează -1, iar funcția returnează fals.

O alternativă corectă este de a testa dacă restul nu este 0 (deoarece restul 0 este același indiferent de semne):

bool is_odd(int n) {
    return n % 2 != 0;
}

O altă alternativă este de a folosi faptul că pentru orice număr impar, restul poate fi 1 sau -1:

bool is_odd(int n) {
    return n % 2 == 1 || n % 2 == -1;
}

Probleme de performanta

Operațiile Modulo pot fi implementate astfel încât să se calculeze de fiecare dată o divizare cu rest. Pentru cazuri speciale, pe unele hardware există alternative mai rapide. De exemplu, modulul de puteri de 2 poate fi alternativ exprimat ca o operație ȘI bit (presupunând că x este un număr întreg pozitiv sau utilizând o definiție care nu trunchiază):

x % 2n == x & (2n - 1)

Exemple:

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

În dispozitivele și software-urile care implementează operațiuni bitbit mai eficient decât modulul, aceste forme alternative pot duce la calcule mai rapide.

Optimizările compilatorului pot recunoaște expresiile formei în expression % constantcare constanteste o putere de doi și le pot implementa automat ca expression & (constant-1), permițând programatorului să scrie cod mai clar fără a compromite performanța. Această optimizare simplă nu este posibilă pentru limbile în care rezultatul operației modulo are semnul dividendului (inclusiv C ), cu excepția cazului în care dividendul este de tip întreg nesemnat . Acest lucru se datorează faptului că, dacă dividendul este negativ, modulul va fi negativ, în timp ce expression & (constant-1)va fi întotdeauna pozitiv. Pentru aceste limbi, echivalența trebuie utilizată în loc, exprimată utilizând operații OR, NU și ȘI bit. x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)

Optimizările pentru operațiile generale de modul constant există, de asemenea, prin calcularea diviziunii folosind mai întâi optimizarea divizorului constant .

Proprietăți (identități)

Unele operații modulo pot fi luate în calcul sau extinse în mod similar cu alte operații matematice. Acest lucru poate fi util în probele de criptografie , cum ar fi schimbul de chei Diffie-Hellman .

• Identitate:
  • ( a mod n ) mod n = a mod n .
  • n ^x mod n = 0 pentru toate valorile întregi pozitive ale lui x .
  • Dacă p este un număr prim care nu este un divizor al lui b , atunci ab ^{p -1} mod p = a mod p , datorită teoremei mici a lui Fermat .
• Invers:
  • [(- a mod n ) + ( a mod n )] mod n = 0 .
  • b ^-1 mod n denotă inversul multiplicativ modular , care este definit dacă și numai dacă b și n sunt relativ prime , ceea ce este cazul când partea stângă este definită: [( b ^-1 mod n ) ( b mod n ) ] mod n = 1 .
• Distributiv:
  • ( a + b ) mod n = [( a mod n ) + ( b mod n )] mod n .
  • ab mod n = [( a mod n ) ( b mod n )] mod n .
• Diviziune (definiție): A/bmod n = [( a mod n ) ( b ^-1 mod n )] mod n , când partea dreaptă este definită (adică când b și n sunt coprimă ) și nedefinită altfel.
• Multiplicare inversă: [( ab mod n ) ( b ^-1 mod n )] mod n = a mod n .

În limbaje de programare

În plus, multe sisteme de calculatoare oferă o divmodfuncționalitate, care produce coeficientul și restul în același timp. Exemplele includ arhitectura x86 's IDIVinstrucțiune, C limbaj de programare a div()funcției, și Python e divmod()funcția.

Generalizări

Modulo cu offset

Uneori este util ca rezultatul unui modul n să nu se afle între 0 și n - 1 , ci între un număr d și d + n - 1 . În acest caz, d se numește offset. Nu pare să existe o notație standard pentru această operațiune, așa că haideți să folosim provizoriu un mod _d n . Avem astfel următoarea definiție: x = a mod _d n doar în cazul în care d ≤ x ≤ d + n - 1 și x mod n = a mod n . În mod clar, operația obișnuită de modulo corespunde zero offset: a mod n = a mod ₀ n . Funcționarea modulului cu offset este legată de funcția de podea după cum urmează:

${\ displaystyle a \ operatorname {mod} _ {d} n = an \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor.}$

(Pentru a vedea acest lucru, permiteți . Arătăm mai întâi că x mod n = a mod n . În general este adevărat că ( a + bn ) mod n = a mod n pentru toate numerele întregi b ; astfel, acest lucru este valabil și în caz când ; dar asta înseamnă că , ceea ce am vrut să dovedim. Rămâne de arătat că d ≤ x ≤ d + n - 1. Fie k și r numerele întregi astfel încât a - d = kn + r cu 0 ≤ r ≤ n - 1 (vezi diviziunea euclidiană ). Apoi , astfel . Acum ia 0 ≤ r ≤ n - 1 și adaugă d pe ambele părți, obținând d ≤ d + r ≤ d + n - 1. Dar am văzut că x = d + r , deci am terminat. □) ${\ textstyle x = an \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor}$${\ textstyle b = - \! \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor}$${\ textstyle x {\ bmod {n}} = \ left (un \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor \ right) \! {\ bmod {n}} = a {\ bmod {n}}}$${\ textstyle \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor = k}$${\ textstyle x = an \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor = a-nk = d + r}$

Modulo cu compensare un mod _d n este pusă în aplicare în Mathematica ca Mod[a, n, d] .

Implementarea altor definiții modulo folosind trunchierea

În ciuda eleganței matematice a diviziunii planificate a lui Knuth și a diviziunii euclidiene, este, în general, mult mai comun să găsești un modulo trunchiat bazat pe diviziune în limbaje de programare. Leijen furnizează următorii algoritmi pentru calcularea celor două diviziuni având o diviziune întreagă trunchiată:

/* Euclidean and Floored divmod, in the style of C's ldiv() */
typedef struct {
  /* This structure is part of the C stdlib.h, but is reproduced here for clarity */
  long int quot;
  long int rem;
} ldiv_t;

/* Euclidean division */
inline ldiv_t ldivE(long numer, long denom) {
  /* The C99 and C++11 languages define both of these as truncating. */
  long q = numer / denom;
  long r = numer % denom;
  if (r < 0) {
    if (denom > 0) {
      q = q - 1;
      r = r + denom;
    } else {
      q = q + 1;
      r = r - denom;
    }
  }
  return (ldiv_t){.quot = q, .rem = r};
}

/* Floored division */
inline ldiv_t ldivF(long numer, long denom) {
  long q = numer / denom;
  long r = numer % denom;
  if ((r > 0 && denom < 0) || (r < 0 && denom > 0)) {
    q = q - 1;
    r = r + denom;
  }
  return (ldiv_t){.quot = q, .rem = r};
}

Rețineți că pentru ambele cazuri, restul poate fi calculat independent de coeficient, dar nu și invers. Operațiunile sunt combinate aici pentru a economisi spațiu pe ecran, deoarece ramurile logice sunt aceleași.

Vezi si

• Modulo (dezambiguizare) și modulo (jargon) - multe utilizări ale cuvântului modulo , toate care au rezultat din introducerea aritmeticii modulare de către Carl F. Gauss în 1801.
• Modulo (matematică) , utilizare generală a termenului în matematică
• Exponențierea modulară
• Turn (unitate)

Note

Referințe

linkuri externe

• Modulorama , animația unei reprezentări ciclice a tabelelor de înmulțire (explicație în franceză)