Алгарытм Эўкліда

З пляцоўкі Вікіпедыя
Jump to navigation Jump to search

У матэматыцы алгарытм Эўклідаалгарытм вылічэння найбольшага агульнага дзельніка (НАД) двух (звычайна дадатных) цэлых лікаў. НАД двух цэлых лікаў — найбольшы натуральны лік, які дзеліць іх без астачы. Алгарытм названы так у гонар грэчаскага матэматыка Эўкліда, які апісаў яго ў кнігах VII і X сваіх Пачаткаў (каля 300 да н.э.)[1].

У сваёй найпрасцейшай форме Эўклідаў алгарытм пачынае з пары няроўных натуральных лікаў. Новую пару ўтвараюць меншы лік і розніца паміж лікамі старой пары. Так працягваецца, пакуль абодва лікі ў новаўтворанай пары не акажуцца роўнымі, гэтае значэнне і будзе найбольшым агульным дзельнікам. Напрыклад, для 105 і 252 першая ітэрацыя дае пару 105 і 147. Пры паўтарэнні працэдуры атрымліваюцца пары 42 і 105, затым 42 і 63, тады 42 і 21, пакуль лікі ў пары не стануць роўнымі аднаму значэнню, ліку 21, які і ёсць НАД пачатковай пары цэлых лікаў.

Пачаткі апісваюць алгарытм для натуральных лікаў і геаметрычных даўжынь. У 19-м і 20-м стст. былі распрацаваны абагульненні алгарытма Эўкліда. Алгарытм дазваляе эфектыўна прыводзіць дробы да нескарачальнага выгляду. Ён з'яўляецца ключавым элементам у многіх крыптаграфічных алгарытмах і пратаколах, па якіх ажыццяўляецца сувязь паміж вузламі ў абароненых сетках. Нарэшце, Эўклідаў алгарытм можа служыць інструментам для доказу тэарэм у сучаснай тэорыі лікаў і арыфметыцы.

Апісанне[правіць | правіць зыходнік]

Асноўная ідэя алгарытма заключаецца ў тым, што для цэлых лікаў a і b мноства іх агульных дзельнікаў такое самае, як і мноства агульных дзельнікаў b і a − bq для любога цэлага q. І праўда, калі d — агульны дзельнік a і b, то існуюць (па азначэнні дзельніка) цэлыя лікі e і f, такія што a = ed і b = fd. Адсюль вынікае, што a − bq = ed − fdq = d(e − fq) і d дзеліць a − bq. Доказ таго, што кожны агульны дзельнік b і a − bq дзеліць таксама a, праводзіцца тым жа шляхам: a = (a − bq) + bq.

Алгарытм Эўкліда замяняе пару (a, b) на (b, a − bq) (ад гэтага мноства агульных дзельнікаў не мяняецца) і паўтарае гэтае дзеянне, пакуль урэшце не з'явіцца пара з нулявым лікам. Каб алгарытм гарантавана завяршыўся за канечную колькасць крокаў, лікі q выбіраюцца так, каб максімум абсалютных велічынь двух лікаў строга памяншаўся з кожным крокам.

Няхай (g, 0) — канчатковы вынік гэтай працэдуры. Мноства агульных дзельнікаў пры гэтым не змянілася, і таму агульныя дзельнікі зыходных лікаў a і b дакладна такія ж, як і ў лікаў g і 0, і такім чынам, супадаюць з дзельнікамі ліку g (паколькі x·0 = 0 для любых x, то 0 дзеліцца на любы цэлы лік). Адпаведна, найбольшы агульны дзельнік лікаў a і b ёсць g, калі g > 0, і −g іначай.

Існуе некалькі варыянтаў алгарытма, якія адрозніваюцца выбарам q на кроках.

У першапачатковым Эўклідавым алгарытме мяркуецца, што ўсе лікі дадатныя (адмоўных лікаў тады яшчэ не ведалі), і на кожным кроку найбольшы натуральны лік замяняўся на розніцу лікаў (г.зн. заўсёды выбіралася q = 1 і, каб першы з лікаў быў большым, пры неабходнасці перамена месцамі). Першапачатковы алгарытм спыняецца, калі атрымліваюцца два роўныя лікі (наступны крок даў бы пару (g, 0)). Урэшце рэшт алгарытм завяршыцца, бо найбольшы ў пары лік строга памяншаецца з кожным крокам.

З-за невысокай эфектыўнасці зыходны варыянт Эўклідавага алгарытма ўжываецца толькі ў адукацыйных мэтах. Для практычных вылічэнняў звычайна выкарыстоўваецца варыянт, заснаваны на дзяленні з астачай.

Дзяленне з астачай[правіць | правіць зыходнік]

Дзяленне з астачай — арыфметычная аперацыя, якая для кожнай пары цэлых лікаў a і b, дзе b ≠ 0, дае два цэлыя лікі q, дзель, і r, астачу, такія што

a = bq + r and 0 ≤ r < |b|,

дзе |b| абазначае абсалютную велічыню b (г.зн. b, калі b дадатны, і −b іначай).

Тэарэма, на якой заснавана азначэнне дзялення з астачай, сцвярджае, што існуюць толькі адна дзель і адзін астатак[2].

Дзяленне з астачай звычайна ажыццяўляецца ў слупок.

Калі дзелі не патрэбны, як у выпадку са звычайным алгарытмам Эўкліда, дзяленне з астаткам можна замяніць аперацыяй прывядзення па модулю, якая дае толькі астатак. Звычайна гэта аперацыя абазначаецца «mod»:

r = a mod b.

Працэдура[правіць | правіць зыходнік]

Алгарытм Эўкліда праходзіць у некалькі этапаў такім чынам, што выхад кожнага кроку выкарыстоўваецца як уваход для наступнага. Хай k ёсць цэлы лік, які лічыць крокі алгарытму, пачынаючы з нуля. Такім чынам, першы крок адпавядае k = 0, наступны крок адпавядае k = 1, і г.д.

Кожны крок пачынаецца з двума неадмоўнымі астаткамі rk−1 і rk−2. Паколькі алгарытм гарантуе, што астаткі з кожным крокам няўхільна памяншаюцца, rk−1 меншы чым яго папярэднік rk−2. Мэта k-га кроку — знайсці дзель qk і астатак rk такія, што задавальняецца роўнасць:

rk−2 = qk rk−1 + rk

дзе rk < rk−1. Іншымі словамі, кратныя меншага ліку rk−1 аднімаюцца ад большага ліку rk−2, пакуль астатак не стане меншы чым rk−1.

На пачатковым кроку (k = 0) астаткі r−2 і r−1 раўняюцца a і b, лікам, для якіх шукаецца НАД. На наступным кроку (k = 1), астаткі роўныя b і астатку r0 ад пачатковага кроку, і г.д. Такім чынам, алгарытм можна запісаць наступнай паслядоўнасцю роўнасцей

a = q0 b + r0
b = q1 r0 + r1
r0 = q2 r1 + r2
r1 = q3 r2 + r3

Каля лік a меншы за b, першы крок алгарытма проста мяняе лікі месцамі. Напрыклад, калі a < b, пачатковая дзель q0 раўняецца нулю, а астатак r0 роўны a. Такім чынам, rk меншы чым яго папярэднік rk−1 для любых k ≥ 0.

Паколькі астаткі памяншаюцца з кожным крокам і пры гэтым заўсёды неадмоўныя, у рэшце рэшт на нейкім кроку астатак rN павінен аказацца роўным нулю, на гэтым кроку алгарытм спыняецца[3]. Апошні ненулявы астатак rN−1 і ёсць найбольшы агульны дзельнік a і b. Нумар кроку N абавязкова канечны, бо існуе толькі канечная колькасць неадмоўных цэлых лікаў паміж пачатковым астаткам r0 і нулём.

У псеўдакодзе алгарытм можна запісаць так (улічваючы, што дзелі qi не выкарыстоўваюцца яўна):

function gcd(a, b)
    r0 := a
    r1 := b
    i := 1
    while ri ≠ 0
       ri+1 := ri-1 mod ri
       i := i + 1
    if i ≤ 2 then return |ri-1|
    return ri-1

Перадапошні радок патрэбен на выпадак, калі апошні ненулявы астатак роўны a ці b, якія могуць аказацца адмоўнымі, калі ўваходныя параметры працэдуры не абмяжоўваюцца дадатнымі лікамі.

Запіс алгарытма можна яшчэ больш спрасціць, бо захоўваць прамежкавыя астаткі няма патрэбы (тут мяркуецца, што ўваходныя лікі неадмоўныя)[4]:

function gcd(a, b)
    while b ≠ 0
       r := a mod b
       a := b
       b := r
    return a

Лікавы прыклад[правіць | правіць зыходнік]

Анімацыя, на якой паступова меншыя квадраты дабаўляюцца, каб поўнасцю пакрыць прамавугольнік.
Анімаваная ілюстрацыя алгарытма Эўкліда, заснаванага на адыманні. Пачатковы зялёны прамавугольнік мае памеры a = 1071 і b = 462. Квадратныя памерам 462×462 аранжавыя пліткі дабаўляюцца пакуль не застанецца зялёны 462×147 прамавугольнік. Зялёны 462×147 прамавугольнік пакрываецца квадратнымі 147×147 сінімі пліткамі, пакуль не застаецца зялёны 21×147 прамавугольнік. Зялёны 21×147 прамавугольнік поўнасцю пакрываецца квадратнымі 21×21 чырвонымі пліткамі. Такім чынам, 21 ёсць найбольшы агульны дзельнік 1071 і 462.

Каб праілюстраваць алгарытм Эўкліда, знойдзем найбольшы агульны дзельнік лікаў a = 1071 і b = 462. Спачатку лік 462 аднімаецца ад 1071 некалькі разоў, пакуль астатак не стане меншы за 462. Такіх адніманняў будзе два (q0 = 2), у астатку застанецца 147

1071 = 2 × 462 + 147.

Затым кратныя 147 аднімаюцца ад 462, пакуль астатак не стане меншы за 147. Такіх адніманняў спатрэбіцца тры (q1 = 3), астатак будзе 21

462 = 3 × 147 + 21.

Потым кратныя 21 аднімаюцца ад 147, пакуль у астатку не застанецца менш чым 21. Такіх адніманняў будзе сем (q2 = 7), пры гэтым у астатку нічога не застанецца

147 = 7 × 21 + 0.

Раз апошні астатак нулявы, алгарытм завяршаецца, даючы лік 21 як найбольшы агульны дзельнік лікаў 1071 і 462. Праверыць адказ можна, вылічыўшы НАД(1071, 462) праз разкладанне лікаў на простыя множнікі. Пройдзеныя крокі можна прадставіць табліцай

Крок k Роўнасць Дзель і астатак
0 1071 = q0 462 + r0 q0 = 2 and r0 = 147
1 462 = q1 147 + r1 q1 = 3 and r1 = 21
2 147 = q2 21 + r2 q2 = 7 and r2 = 0; алгарытм завяршаецца

Візуалізацыя[правіць | правіць зыходнік]

Алгарытм Эўкліда можна візуалізаваць з дапамогай пакрыцця прамавугольнікаў квадратнымі пліткамі[5]. Дапусцім, што трэба роўна пакрыць a-на-b-прамавульнік квадратнымі пліткамі. Няхай a — большы з двух лікаў. Спачатку спрабуем залажыць прамавугольнік квадратнымі пліткамі b-на-b. Але застаецца непакрыты астаткавы r0-на-b прамавугольнік, дзе r0 < b. Тады спрабуем пакрыць астаткавы прамавугольнік квадратамі r0-на-r0. Застаецца другі астаткавы прамавугольнік r1-на-r0, які мы спрабуем залажыць квадратамі r1-на-r1, і г.д. Паслядоўнасць заканчваецца, калі не застаецца астаткавага прамавугольніка, г.зн. квадратныя пліткі роўна пакрываюць папярэдні астаткавы прамавугольнік. Даўжыня старон найменшай квадратнай пліткі і ёсць НАД даўжынь старон пачатковага прамавугольніка. Напрыклад, самая маленькая квадратная плітка на суседнім рысунку мае памер 21-на-21 (паказана чырвоным), і 21 ёсць НАД лікаў 1071 і 462, памераў пачаткова прамавугольніка (на рысунку зялёны).

Варыянт з найменшымі абсалютнымі астаткамі[правіць | правіць зыходнік]

Варыянт дзялення з астаткам, т.зв. дзяленне з найменшым абсалютным астаткам, заключаецца ў дапушчэнні адмоўных астаткаў і выбары дзелі такім чынам, каб астатак меў як мага меншую абсалютную велічыню. Пры такім дзяленні для кожнай пары цэлых лікаў a і b такіх, што b ≠ 0, існуе роўна адна пара цэлых q і r, такіх што

a = bq + r   і  −|b|2 < r ≤ |b|2,

дзе |b| абазначае абсалютную велічыню ліку b (г.зн. b, калі b дадатны, і −b іначай)[6][7].

Такое дзяленне лёгка выводзіцца са звычайнага дзялення з астачай. Калі q' і r' — дзель і астатак звычайнага дзялення з астачай, тады бяром q = q' і r = r' , калі 2r' ≤ |b|, а іначай q = q' + e і r = r'eb, дзе e = 1 пры b > 0, і e = −1 пры b < 0.

У астатнім такі варыянт алгарытма Эўкліда нічым не адрозніваецца ад звычайнага: дастаткова толькі змяніць азначэнне аперацыі «mod» так, каб яна выдавала найменшы абсалютны астатак, і мяняць знак выніку, калі ён адмоўны.

Леапольд Кронекер паказаў, што гэты варыянт патрабуе найменшую колькасць крокаў у параўнанні з любой іншай версіяй алгарытма Эўкліда (г.зн. для любога іншага выбару q і r)[6][7]. Больш агульна, было даказана, што для любых уваходных лікаў a і b, колькасць крокаў будзе найменшая, калі і толькі калі qk выбіраецца так, што дзе залатое сячэнне[8].

Зноскі[правіць | правіць зыходнік]

  1. Heath, Thomas L. (1956) [1925]. The Thirteen Books of Euclid's Elements (2nd ed.). Dover Publications. 
  2. Cohn 1962, pp. 104–110
  3. Stark 1978, p. 18
  4. Knuth 1997, pp. 319–320
  5. Kimberling C (1983). "A Visual Euclidean Algorithm". Mathematics Teacher 76: 108–109. 
  6. 6,0 6,1 Ore 1948, p. 43
  7. 7,0 7,1 Stewart, B. M. (1964). Theory of Numbers (2nd ed.). New York: Macmillan. pp. 43–44. 
  8. Lazard, D. (1977). "Le meilleur algorithme d'Euclide pour K[X] et Z" (in French). Comptes Rendus Acad. Sci. (Paris) 284: 1-4. 

Літаратура[правіць | правіць зыходнік]