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

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

У сваёй найпрасцейшай форме Эўклідаў алгарытм пачынае з пары няроўных натуральных лікаў. Новую пару ўтвараюць меншы лік і розніца паміж лікамі старой пары. Так працягваецца, пакуль абодва лікі ў новаўтворанай пары не акажуцца роўнымі, гэтае значэнне і будзе найбольшым агульным дзельнікам. Напрыклад, для 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 іначай).

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

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

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

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

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



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

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







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

Паколькі астаткі памяншаюцца з кожным крокам і пры гэтым заўсёды неадмоўныя, у рэшце рэшт на нейкім кроку астатак rN павінен аказацца роўным нулю, на гэтым кроку алгарытм спыняецца. Апошні ненулявы астатак 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, якія могуць аказацца адмоўнымі, калі ўваходныя параметры працэдуры не абмяжоўваюцца дадатнымі лікамі.

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

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

 Лікавы прыклад 

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



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



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



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

Крок kРоўнасцьДзель і астатак 0     1     2    ; алгарытм завяршаецца

 Візуалізацыя 
Алгарытм Эўкліда можна візуалізаваць з дапамогай пакрыцця прамавугольнікаў квадратнымі пліткамі. Дапусцім, што трэба роўна пакрыць 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   і  − < r ≤ ,
дзе |b| абазначае абсалютную велічыню ліку b (г.зн. b, калі b дадатны, і −b іначай).

Такое дзяленне лёгка выводзіцца са звычайнага дзялення з астачай. Калі q'  і r'  — дзель і астатак звычайнага дзялення з астачай, тады бяром  і , калі , а іначай  і , дзе  пры , і  пры .

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

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

 Зноскі 

 Літаратура 









Катэгорыя:Алгарытмы
Катэгорыя:Тэорыя лікаў
Катэгорыя:Дзяленне