Մոդուլո գործողություն

Մոդուլո գործողություն, թվաբանության մեջ վերադարձնում է բաժանման արդյունքում ստացված մնացորդը՝ նշանով, կամ առանց նշանի։

Տրված են երկու դրական թվեր՝ a և n: a մոդուլո n-ը (համակարգչային գիտության մեջ՝ a mod n) Էվկլիդյան բաժանման մնացորդն է՝ a-ն n-ի բաժանելիս, որտեղ a-ն բաժանելին է, իսկ n-ը՝ բաժանարարը։

Օրինակ, 5 mod 2 արտահայտության արժեքը 1 է, քանի որ 5-ը բաժանված է 2-ի, ունի քանորդ՝ 2, իսկ մնացորդը՝ 1, մինչդեռ «9 mod 3» արտահայտության արժեքը 0 է, քանի որ 9-ը բաժանված է 3-ի, ունի քանորդ՝ 3 և մնացորդ՝ 0 (3-ը 3-ի բազմապատկելուց հետո,երբ պատասխանը հանում ենք 9-ից, ստացվում է 0)։

Սովորաբար այս գործողությունը կատարվում է այնպիսի a-ով և n-ով, որ երկուսն էլ լինեն ամբողջ թվեր, սակայն շատ հաշվողական համակարգեր այժմ թույլ են տալիս a-ի և n-ի այլ տեսակներ։ n-ի ամբողջ թվային մոդուլային գործողության արժեքների միջակայքը 0-ից n-1-ն է ներառյալ (mod 1-ը միշտ 0 է, mod 0-ն որոշված չէ, ինչը կարող է հանգեցնել զրոյով բաժանման սխալի որոշ ծրագրավորման լեզուներում)։

Երբ a-ից կամ n-ից մեկը բացասական է, սահմանումը խախտվում է, և ծրագրավորման լեզուները տարբերվում են նրանով, թե ինչպես են սահմանում համակարգչի տված պատասխանը այդ իրավիճակում։

Սահմանման տարբերակներ
Մաթեմատիկայում մոդուլո գործողության արդյունքը համարժեքության դաս է (ինչպես օրինակ mod 5 գործողության համար դաս 0 = {0, 5, 10, 15, …}, դաս1 = {1, 6, 11, 16, …} և այլն), և դասի ցանկացած անդամ կարող է ընտրվել որպես դասի ներկայացնող անդամ։ Այնուամենայնիվ, սովորաբար, որպես ներկայացնող ընտրվում է նվազագույն ոչ բացասական ամբողջ թիվը, որը պատկանում է այդ դասին։ Այնուամենայնիվ, հնարավոր են այլ սահմանումներ։

Համակարգիչներն ու հաշվիչներն ունեն թվեր պահելու և ներկայացնելու տարբեր եղանակներ, հետևաբար, մոդուլային գործողության նրանց սահմանումը կախված է ծրագրավորման լեզվից կամ համակարգչի սարքախմբից։

Գրեթե բոլոր հաշվողական համակարգերում q գործակիցը և a-ն բաժանած n-ի մնացորդ r-ը բավարարում են հետևյալ պայմաններին.
 

Այնուամենայնիվ, սա դեռևս թողնում է նշանի անորոշություն, եթե մնացորդը զրոյական չէ. տեղի է ունենում մնացորդի համար երկու հնարավոր ընտրություն, մեկը բացասական, մյուսը դրական, և երկու հնարավոր ընտրություն գործակիցի համար։ Թվերի տեսության մեջ միշտ ընտրվում է դրական մնացորդը, իսկ հաշվարկում ծրագրավորման լեզուները ընտրում են՝ կախված լեզվից և a-ի կամ n-ի նշաններից։ Ստանդարտ Pascal-ը և ALGOL 68-ը, օրինակ, տալիս են դրական մնացորդ (կամ 0) նույնիսկ բացասական բաժանարարների համար, իսկ որոշ ծրագրավորման լեզուներ, ինչպիսին է C90-ը, թողնում են այն իմպլեմենտացիային, երբ n-ից կամ a-ից որևէ մեկը բացասական՝ a mod 0-ն որոշված չէ համակարգերի մեծ մասում, թեև ոմանք այն սահմանում են որպես a՝

Լեյջենն ասել է․
{{Քաղվածք|Բուտը պնդում է, որ էվկլիդեսյան բաժանումը գերազանցում է մյուսներին օրինաչափության և օգտակար մաթեմատիկական հատկությունների առումով, թեև դեպի ներքև կլորացումով բաժանումը, որի կողմնակիցն է Կնուտը, նույնպես լավ սահմանում է։ Չնայած դրա լայն տարածմանը, կոտորակային մասը կտրելով բաժանումը զիջում է մյուս սահմանումներին։|Division and Modulus for Computer Scientists}}

Այնուամենայնիվ կոտորակային մասը կտրելով բաժանումը բավարարում է այս նույնությանը .

Նշանը
Որոշ հաշվիչներ ունեն mod() ֆունկցիայի կոճակ, և շատ ծրագրավորման լեզուներ ունեն նմանատիպ ֆունկցիա, որն արտահայտվում է հիմնականում, որպես mod(a, n)։ Ոմանք որպես նշան օգտագործում են «%», «mod» կամ «Mod» նշանները՝ որպես մոդուլ կամ մնացորդային օպերատոր, օրինակ՝ % n կամ mod n:

Ֆունկցիան չունեցող միջավայրերը կարող են օգտագործել վերը նշված երեք սահմանումներից որևէ մեկը։

Տարածված սխալներ
Երբ մոդուլային գործողության արդյունքն ունի բաժանելիի նշանը (կոտորակային մասը կտրելով բաժանման սահմանում), դա կարող է հանգեցնել սխալների։

Օրինակ, ստուգելու համար, թե արդյոք ամբողջ թիվը կենտ է, կարելի է հակված լինել ստուգելու, թե արդյոք այդ թիվը 2-ի բաժանելիս մնացորդը հավասար է 1-ի։

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

Այն լեզուներում, որտեղ մնացորդը ունի բաժանելիի նշանը, այս ալգորիթմը կտա սխալ պատասխան, որովհետև, երբ n-ը բաժանելին է և կենտ է,  mod 2 -ը կվերադարձնի −1 և վերևի ֆունկցիան կվերադարձնի false։

Այս խնդիրի լուծման համար ալգորթիմի ճիշտ ալտերնատիվն է ստուգելը, որ մնացորդը 0 չէ (քանի որ, զույգ թվերը 2-ի բաժանելիս մնացորդը 0 է անկախ նշանից)։

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

Մեկ ուրիշ տարբերակ է ստուգելը, որ մնացորդը կամ 1 է, կամ -1։

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

Ավելի պարզ ալտերնատիվ է վերաբերվելը n% 2-ի արդյունքին, որպես բուլյան արժեք, որտեղ ցանկացած ոչ զրոյական պատասխան վերադարձնում է true:

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

Կատարողականության խնդիրներ
Մոդուլային գործողությունները կարող են իրականացվել այնպես, որ ամեն անգամ հաշվարկվը կատարվի մնացորդով բաժանումով։ Հատուկ դեպքերի համար, որոշ սարքավորումների վրա, կան ավելի արագացված տարբերակներ։ Օրինակ, 2-ի աստիճանների մնացորդը կարող է հաշվվել որպես բիթային AND գործողություն (ենթադրելով, որ x-ը դրական ամբողջ թիվ է կամ օգտագործել բոլոր սահմանումները բացի կոտորակային մասը կտրելով բաժանման սահմանումից)։
x % 2n == x & (2n - 1)

Օրինակներ։

Սարքերում և ծրագրերում, որոնք ավելի արդյունավետ են իրականացնում բիթային գործողությունները, քան մոդուլոն, այս այլընտրանքային ձևերը կարող են արագացնել հաշվարկները։

Կոմպիլյատորների օպտիմիզացիաները կարող են ճանաչել  գործողությունը, որտեղ հաստատունը երկուսի աստիճան է և ավտոմատ կերպով իրականացնել դրանք որպես ՝ թույլ տալով ծրագրավորողին գրել ավելի հստակ կոդ՝ առանց կատարողականությունը վատացնելու։ Այս պարզ օպտիմիզացիան հնարավոր չէ այն լեզուների համար, որոնցում մոդուլային գործողության արդյունքն ունի բաժանելիի նշան (ներառյալ C), բացառությամբ այն դեպքերի, երբ բաժանելին առանց նշանկի ամբողջ թիվ չէ։ Դա պայմանավորված է նրանով, որ եթե բաժանելին բացասական է, մոդուլը բացասական կլինի, մինչդեռ  արտահայտությունը միշտ դրական կլինի։ Այս լեզուների համար համարժեքը x % 2n == x < 0? x | ~(2n - 1): x & (2n - 1) -ն է,որը օգտագործում է բիթային OR, NOT և AND գործողությունները։

Հատկություններ
Որոշ մոդուլո գործողություններ կարող են ֆակտորիզացվել և վերլուծվել, ինչպես այլ մաթեմատիկական գործողությունները։ Սա կարող է օգտակար լինել գաղտնագրության ապացույցների մեջ, օրինակ օգտագործվում է Դիֆֆի-Հելլմանի բանալու փոխանակման մեջ։ Այս հատկություններից որոշները պահանջում են, որ -ն և -ը լինեն ամբողջ թվեր․
 Նույնականություն․
 .
  -ի բոլոր դրական արժեքների համար.
 Եթե -ն պարզ թիվ է, որը -ի բաժանարար չէ, then , ըստ Ֆերմայի փոքր թեորեմի.
 Հակադարձ․
 :
  նշանակում է մոդուլային բազմապատկվող հակադարձ, որը սահմանվում է, այն և միայն այն դեպքում, երբ b-ն և n-ը համեմատաբար պարզ են, որը տեղի ունի, երբ ձախ կողմը սահմանված է։ :
 Բաշխական․
 .
 .
 Բաժանում (սահմանում)․ , երբ աջ մասը լավ սահմանված է (երբ -ն և -ը փոխադարձաբար պարզ են)։
 Հակադարձ բազմապատկում․ .

Ծրագրավորման լեզուներում

Շատ համակարգչային համակարգեր ապահովում են  ֆունկցիոնալություն, որը վերադարձնում է քանորդը և մնացորդը միաժամանակ։ Օրինակները ներառում են x86 ճարտարապետության  հրահանգը, C ծրագրավորման լեզվի  ֆունկցիան և Python-ի  ֆունկցիան։

Ընդհանրացումներ

Մոդուլոն լրացյալով
Երբեմն օգտակար է, որ մոդուլոյի արդյունքը ընկած լինի ոչ թե 0-ի և n-1-ի, այլ d-ի և d + n-1-ի միջև։ Այդ դեպքում d-ն կոչվում է լրացյալ''։ Թվում է, թե այս գործողության համար ստանդարտ նշում չկա, ուստի եկեք պայմանականորեն օգտագործենք -ը։ Այսպիսով, մենք ունենք հետևյալ սահմանումը. , երբ d ≤ x ≤ d + n − 1 և x mod n = a mod n: Ակնհայտ է, որ սովորական մոդոյի գործողությունը համապատասխանում է զրո լրացյալին. : Լրացյալով մոդուլոյի աշխատանքը կապված է դեպի ներքև կլորացման ֆունկցիայի հետ հետևյալ կերպ.

Լրացյալով մոդուլոն  իմպլեմենտացված է Mathematica լեզվում, որպես  .

Մոդուլո գործողության իմպլեմենտացիան, օգտագործելով կոտորակային մասը կտրելով բաժանում 
Չնայած Կնութի Դեպի ներքև կլորացումով բաժանման և Էվկլիդյան բաժանման մաթեմատիկական գեղեցությանը, ծրագրավորման լեզուներում ընդհանուր առմամբ շատ ավելի տարածված է բաժանման վրա հիմնված մոդուլ գտնելը։ Լեյջենը տրամադրում է հետևյալ ալգորիթմները կոտորակային մասը կտրելով ամբողջ թվի բաժանումը հաշվարկելու համար.

/* 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};
}

Երկու դեպքում էլ մնացորդը կարող է հաշվարկվել քանորդից անկախ, բայց ոչ հակառակը։

Ծանոթագրություններ

Նշումներ

Արտաքին հղումներ
 Modulorama, բազմապատկման աղյուսակների անիմացիոն ցուցադրում (բացատրված է ֆրանսերենով)

Ծրագրավորում
Բաժանում
Տեսական ինֆորմատիկա
Ամառային երիտասարդական վիքիճամբարի հոդվածներ