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

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

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

r_k−2 = q_k r_k−1 + r_k

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

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

a = q₀ b + r₀
b = q₁ r₀ + r₁
r₀ = q₂ r₁ + r₂
r₁ = q₃ r₂ + r₃
…

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

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

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

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. Такіх адніманняў будзе два (q₀ = 2), у астатку застанецца 147

1071 = 2 × 462 + 147.

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

462 = 3 × 147 + 21.

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

147 = 7 × 21 + 0.

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

Візуалізацыя

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

Варыянт з найменшымі абсалютнымі астаткамі

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

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

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

Такое дзяленне лёгка выводзіцца са звычайнага дзялення з астачай. Калі 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). Больш агульна, было даказана, што для любых уваходных лікаў a і b, колькасць крокаў будзе найменшая, калі і толькі калі q_k выбіраецца так, што ${\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\approx 0.618,}$  дзе ${\displaystyle \varphi }$  — залатое сячэнне.