Алгарытм Эўкліда
У матэматыцы алгарытм Эўкліда — алгарытм вылічэння найбольшага агульнага дзельніка (НАД) двух (звычайна дадатных) цэлых лікаў. НАД двух цэлых лікаў — найбольшы натуральны лік, які дзеліць іх без астачы. Алгарытм названы так у гонар грэчаскага матэматыка Эўкліда, які апісаў яго ў кнігах 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 < 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 павінен аказацца роўным нулю, на гэтым кроку алгарытм спыняецца[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 аднімаецца ад 1071 некалькі разоў, пакуль астатак не стане меншы за 462. Такіх адніманняў будзе два (q0 = 2), у астатку застанецца 147
Затым кратныя 147 аднімаюцца ад 462, пакуль астатак не стане меншы за 147. Такіх адніманняў спатрэбіцца тры (q1 = 3), астатак будзе 21
Потым кратныя 21 аднімаюцца ад 147, пакуль у астатку не застанецца менш чым 21. Такіх адніманняў будзе сем (q2 = 7), пры гэтым у астатку нічога не застанецца
Раз апошні астатак нулявы, алгарытм завяршаецца, даючы лік 21 як найбольшы агульны дзельнік лікаў 1071 і 462. Праверыць адказ можна, вылічыўшы НАД(1071, 462) праз разкладанне лікаў на простыя множнікі. Пройдзеныя крокі можна прадставіць табліцай
| Крок k | Роўнасць | Дзель і астатак |
|---|---|---|
| 0 | Шаблон:Math | Шаблон:Math |
| 1 | Шаблон:Math | Шаблон:Math |
| 2 | Шаблон:Math | Шаблон:Math; алгарытм завяршаецца |
Візуалізацыя
Алгарытм Эўкліда можна візуалізаваць з дапамогай пакрыцця прамавугольнікаў квадратнымі пліткамі[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 і −Шаблон:Sfrac < r ≤ Шаблон:Sfrac,
дзе |b| абазначае абсалютную велічыню ліку b (г.зн. b, калі b дадатны, і −b іначай)[6][7].
Такое дзяленне лёгка выводзіцца са звычайнага дзялення з астачай. Калі q' і r' — дзель і астатак звычайнага дзялення з астачай, тады бяром Шаблон:Nowrap і Шаблон:Nowrap, калі Шаблон:Nowrap, а іначай Шаблон:Nowrap і Шаблон:Nowrap, дзе Шаблон:Nowrap пры Шаблон:Nowrap, і Шаблон:Nowrap пры Шаблон:Nowrap.
У астатнім такі варыянт алгарытма Эўкліда нічым не адрозніваецца ад звычайнага: дастаткова толькі змяніць азначэнне аперацыі «mod» так, каб яна выдавала найменшы абсалютны астатак, і мяняць знак выніку, калі ён адмоўны.
Леапольд Кронекер паказаў, што гэты варыянт патрабуе найменшую колькасць крокаў у параўнанні з любой іншай версіяй алгарытма Эўкліда (г.зн. для любога іншага выбару q і r)[6][7]. Больш агульна, было даказана, што для любых уваходных лікаў a і b, колькасць крокаў будзе найменшая, калі і толькі калі Шаблон:Math выбіраецца так, што дзе — залатое сячэнне[8].