Прагляд зыходнага тэксту старонкі Алгарытм Эўкліда

У [[матэматыка|матэматыцы]] '''алгарытм Эўкліда''' — [[алгарытм]] вылічэння [[найбольшы агульны дзельнік|найбольшага агульнага дзельніка]] (НАД) двух (звычайна [[Дадатны лік|дадатных]]) [[Цэлы лік|цэлых лікаў]]. НАД двух цэлых лікаў — найбольшы [[натуральны лік]], які [[дзяленне з астачай|дзеліць іх без астачы]]. Алгарытм названы так у гонар [[матэматыка ў Старажытнай Грэцыі|грэчаскага матэматыка]] [[Эўклід]]а, які апісаў яго ў кнігах VII і X сваіх ''[[Пачаткі Эўкліда|Пачаткаў]]'' (каля 300 да н.э.)<ref>{{cite book |first=Thomas L. |last=Heath |title=The Thirteen Books of Euclid's Elements |url=https://archive.org/details/nlsiu.513.hea-1.34462 |edition=2nd |orig-year=1925 |year=1956 |publisher=Dover Publications}}</ref>.

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

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

== Апісанне ==

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

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

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

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

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

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

=== Дзяленне з астачай ===
{{асноўны артыкул|Дзяленне з астачай}}

Дзяленне з астачай — [[арыфметычная аперацыя]], якая для кожнай пары цэлых лікаў ''a'' і ''b'', дзе ''b''&nbsp;≠&nbsp;0, дае два цэлыя лікі ''q'', ''дзель'', і ''r'', ''астачу'', такія што
: ''a''&nbsp;=&nbsp;''bq''&nbsp;+&nbsp;''r'' and 0&nbsp;≤&nbsp;''r''&nbsp;<&nbsp;|''b''|,
дзе |''b''| абазначае абсалютную велічыню ''b'' (г.зн. ''b'', калі ''b'' дадатны, і &minus;''b'' іначай).

Тэарэма, на якой заснавана азначэнне [[дзяленне з астачай|дзялення з астачай]], сцвярджае, што існуюць толькі адна дзель і адзін астатак<ref name="Cohn_1962">{{Harvnb|Cohn|1962|pp=104–110}}</ref>.

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

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

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

Кожны крок пачынаецца з двума неадмоўнымі астаткамі ''r''<sub>''k''&minus;1</sub> і ''r''<sub>''k''&minus;2</sub>. Паколькі алгарытм гарантуе, што астаткі з кожным крокам няўхільна памяншаюцца, ''r''<sub>''k''&minus;1</sub> меншы чым яго папярэднік ''r''<sub>''k''&minus;2</sub>. Мэта ''k''-га кроку — знайсці [[няпоўная дзель|дзель]] ''q''<sub>''k''</sub> і [[астача ад дзялення|астатак]] ''r''<sub>''k''</sub> такія, што задавальняецца роўнасць:

: {{math|1=''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}}

дзе ''r''<sub>''k''</sub>&nbsp;<&nbsp;''r''<sub>''k''&minus;1</sub>. Іншымі словамі, кратныя меншага ліку ''r''<sub>''k''&minus;1</sub> аднімаюцца ад большага ліку ''r''<sub>''k''&minus;2</sub>, пакуль астатак не стане меншы чым ''r''<sub>''k''&minus;1</sub>.

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

: {{math|1=''a'' = ''q''<sub>0</sub> ''b'' + ''r''<sub>0</sub>}}
: {{math|1=''b'' = ''q''<sub>1</sub> ''r''<sub>0</sub> + ''r''<sub>1</sub>}}
: {{math|1=''r''<sub>0</sub> = ''q''<sub>2</sub> ''r''<sub>1</sub> + ''r''<sub>2</sub>}}
: {{math|1=''r''<sub>1</sub> = ''q''<sub>3</sub> ''r''<sub>2</sub> + ''r''<sub>3</sub>}}
: {{math|1=…}}

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

Паколькі астаткі памяншаюцца з кожным крокам і пры гэтым заўсёды неадмоўныя, у рэшце рэшт на нейкім кроку астатак ''r''<sub>''N''</sub> павінен аказацца роўным нулю, на гэтым кроку алгарытм спыняецца<ref>{{Harvnb|Stark|1978|p=18}}</ref>. Апошні ненулявы астатак ''r''<sub>''N''−1</sub> і ёсць найбольшы агульны дзельнік ''a'' і ''b''. Нумар кроку ''N'' абавязкова канечны, бо існуе толькі канечная колькасць неадмоўных цэлых лікаў паміж пачатковым астаткам ''r''<sub>0</sub> і нулём.

У псеўдакодзе алгарытм можна запісаць так (улічваючы, што дзелі ''q''<sub>''i''</sub> не выкарыстоўваюцца яўна):
 '''function''' gcd(''a'', ''b'')
     ''r''<sub>0</sub> := ''a''
     ''r''<sub>1</sub> := ''b''
     ''i'' := 1
     '''while''' ''r''<sub>''i''</sub> ≠ 0
        ''r''<sub>''i''+1</sub> := ''r''<sub>''i''-1</sub> '''mod''' ''r''<sub>''i''</sub>
        ''i'' := ''i'' + 1
     '''if''' ''i'' ≤ 2 '''then return''' |''r''<sub>''i''-1</sub>|
     '''return''' ''r''<sub>''i''-1</sub>

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

Запіс алгарытма можна яшчэ больш спрасціць, бо захоўваць прамежкавыя астаткі няма патрэбы (тут мяркуецца, што ўваходныя лікі неадмоўныя)<ref>{{harvnb|Knuth|1997|pp=319–320}}</ref>:

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

=== Лікавы прыклад ===
[[Выява:Euclidean algorithm 1071 462.gif|upright|thumb|alt=Анімацыя, на якой паступова меншыя квадраты дабаўляюцца, каб поўнасцю пакрыць прамавугольнік.|Анімаваная ілюстрацыя алгарытма Эўкліда, заснаванага на адыманні. Пачатковы зялёны прамавугольнік мае памеры ''a''&nbsp;=&nbsp;1071 і ''b''&nbsp;=&nbsp;462. Квадратныя памерам 462&times;462 аранжавыя пліткі дабаўляюцца пакуль не застанецца зялёны 462&times;147 прамавугольнік. Зялёны 462&times;147 прамавугольнік пакрываецца квадратнымі 147&times;147 сінімі пліткамі, пакуль не застаецца зялёны 21&times;147 прамавугольнік. Зялёны 21&times;147 прамавугольнік поўнасцю пакрываецца квадратнымі 21&times;21 чырвонымі пліткамі. Такім чынам, 21 ёсць найбольшы агульны дзельнік 1071 і 462.]]

Каб праілюстраваць алгарытм Эўкліда, знойдзем найбольшы агульны дзельнік лікаў ''a''&nbsp;=&nbsp;1071 і ''b''&nbsp;=&nbsp;462. Спачатку лік 462 аднімаецца ад 1071 некалькі разоў, пакуль астатак не стане меншы за 462. Такіх адніманняў будзе два (''q''<sub>0</sub>&nbsp;=&nbsp;2), у астатку застанецца 147

: {{math|1=1071 = 2 × 462 + 147.}}

Затым кратныя 147 аднімаюцца ад 462, пакуль астатак не стане меншы за 147. Такіх адніманняў спатрэбіцца тры (''q''<sub>1</sub>&nbsp;=&nbsp;3), астатак будзе 21

: {{math|1=462 = 3 × 147 + 21.}}

Потым кратныя 21 аднімаюцца ад 147, пакуль у астатку не застанецца менш чым 21. Такіх адніманняў будзе сем (''q''<sub>2</sub>&nbsp;=&nbsp;7), пры гэтым у астатку нічога не застанецца

: {{math|1=147 = 7 × 21 + 0.}}

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

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
!Крок ''k''!!Роўнасць!!Дзель і астатак
|-
| 0 || {{math|1=1071 = ''q''<sub>0</sub> 462 + ''r''<sub>0</sub>}} || {{math|1=''q''<sub>0</sub> = 2 and ''r''<sub>0</sub> = 147}}
|-
| 1 || {{math|1=462 = ''q''<sub>1</sub> 147 + ''r''<sub>1</sub>}} || {{math|1=''q''<sub>1</sub> = 3 and ''r''<sub>1</sub> = 21}}
|-
| 2 || {{math|1=147 = ''q''<sub>2</sub> 21 + ''r''<sub>2</sub>}} || {{math|1=''q''<sub>2</sub> = 7 and ''r''<sub>2</sub> = 0}}; алгарытм завяршаецца
|}

=== Візуалізацыя ===
Алгарытм Эўкліда можна візуалізаваць з дапамогай пакрыцця прамавугольнікаў квадратнымі пліткамі<ref name="Kimberling_1983">{{cite journal | author = Kimberling C | year = 1983 | title = A Visual Euclidean Algorithm | url = https://archive.org/details/sim_mathematics-teacher_1983-02_76_2/page/108 | journal = Mathematics Teacher | volume = 76 | pages = 108–109}}</ref>. Дапусцім, што трэба роўна пакрыць ''a''-на-''b''-прамавульнік квадратнымі пліткамі. Няхай ''a'' — большы з двух лікаў. Спачатку спрабуем залажыць прамавугольнік квадратнымі пліткамі ''b''-на-''b''. Але застаецца непакрыты астаткавы ''r''<sub>0</sub>-на-''b'' прамавугольнік, дзе ''r''<sub>0</sub>&nbsp;<&nbsp;''b''. Тады спрабуем пакрыць астаткавы прамавугольнік квадратамі ''r''<sub>0</sub>-на-''r''<sub>0</sub>. Застаецца другі астаткавы прамавугольнік ''r''<sub>1</sub>-на-''r''<sub>0</sub>, які мы спрабуем залажыць квадратамі ''r''<sub>1</sub>-на-''r''<sub>1</sub>, і г.д. Паслядоўнасць заканчваецца, калі не застаецца астаткавага прамавугольніка, г.зн. квадратныя пліткі роўна пакрываюць папярэдні астаткавы прамавугольнік. Даўжыня старон найменшай квадратнай пліткі і ёсць НАД даўжынь старон пачатковага прамавугольніка. Напрыклад, самая маленькая квадратная плітка на суседнім рысунку мае памер 21-на-21 (паказана чырвоным), і 21 ёсць НАД лікаў 1071 і 462, памераў пачаткова прамавугольніка (на рысунку зялёны).

=== Варыянт з найменшымі абсалютнымі астаткамі ===
Варыянт дзялення з астаткам, т.зв. ''дзяленне з найменшым абсалютным астаткам'', заключаецца ў дапушчэнні адмоўных астаткаў і выбары дзелі такім чынам, каб астатак меў як мага меншую абсалютную велічыню. Пры такім дзяленні для кожнай пары цэлых лікаў ''a'' і ''b'' такіх, што ''b''&nbsp;≠&nbsp;0, існуе роўна адна пара цэлых ''q'' і ''r'', такіх што
: ''a''&nbsp;=&nbsp;''bq''&nbsp;+&nbsp;''r'' &nbsp;&nbsp;і&nbsp;&nbsp;&minus;{{sfrac|{{!}}''b''{{!}}|2}}&nbsp;<&nbsp;''r''&nbsp;≤&nbsp;{{sfrac|{{!}}''b''{{!}}|2}},
дзе |''b''| абазначае абсалютную велічыню ліку ''b'' (г.зн. ''b'', калі ''b'' дадатны, і &minus;''b'' іначай)<ref name="Ore_least_abs_remainders" >{{Harvnb|Ore|1948|p=43}}</ref><ref name="Stewart_1964">{{cite book | last = Stewart |first=B. M. | year = 1964 | title = Theory of Numbers | url = https://archive.org/details/theorynumbers00stew | edition = 2nd | publisher = Macmillan | location = New York | pages = [https://archive.org/details/theorynumbers00stew/page/n53 43]–44 | lccn = 64010964}}</ref>.

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

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

[[Леапольд Кронекер]] паказаў, што гэты варыянт патрабуе найменшую колькасць крокаў у параўнанні з любой іншай версіяй алгарытма Эўкліда (г.зн. для любога іншага выбару ''q'' і ''r'')<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" />. Больш агульна, было даказана, што для любых уваходных лікаў ''a'' і ''b'', колькасць крокаў будзе найменшая, калі і толькі калі {{math|''q''<sub>''k''</sub>}} выбіраецца так, што <math>\left |\frac{r_{k+1}}{r_k}\right |<\frac{1}{\varphi}\approx 0.618,</math> дзе <math>\varphi</math> — [[залатое сячэнне]]<ref>{{cite journal |last=Lazard |first=D. |year=1977 |title=Le meilleur algorithme d'Euclide pour ''K''[''X''] ''et'' '''Z''' |trans-title=Best Euclidean algorithm for ''K''[''X''] and '''Z''' |language=fr |journal=Comptes Rendus Acad. Sci. |location=Paris |volume=284 |pages=1-4}}</ref>.

== Зноскі ==
{{reflist|2}}

== Літаратура ==
* {{кніга |аўтар=Виноградов И. М. |загаловак=Основы теории чисел |спасылка=http://www.mccme.ru/free-books/djvu/vinogradov.djvu}}
* {{кніга |аўтар=Курант Р., Роббинс Г. |частка=Дополнение к главе I, § 4. |загаловак=Что такое математика? |nodot=1 |выданне=3-e изд., испр. и доп |месца=М. |год=2001 |старонак=568 |спасылка=http://www.mccme.ru/free-books/pdf/kurant.htm}}
* {{артыкул |аўтар=Абрамов С. |загаловак=Самый знаменитый алгоритм |выданне=Квант |год=1985 |нумар=11 |старонкі=44—46 |спасылка=http://kvant.mccme.ru/1985/11/samyj_znamenityj_algoritm.htm}}
* {{кніга |аўтар=Щетников А. И. |загаловак=Алгоритм Евклида и непрерывные дроби |месца=Новосибирск |выдавецтва=АНТ |год=2003}}
* {{cite book |last=Cohn |first=H. |year=1962 |title=Advanced Number Theory |url=http://books.google.com/?id=yMGeElJ8M0wC |publisher=Dover |location = New York |isbn=0-486-64023-X }}
* {{cite book |last=Knuth |first=Donald |year=1997|title=The Art of Computer Programming, Volume 2: Seminumerical Algorithms|edition=3rd|publisher=Addison–Wesley| isbn=0-201-89684-2 }}
* {{cite book |last=Ore |first=Øystein |year=1948 |title=Number Theory and Its History |url=https://archive.org/details/numbertheoryitsh00ore |publisher=McGraw–Hill |location=New York }}
* {{cite book |last=Stark |first=Harold |year=1978 |title=An Introduction to Number Theory |publisher=MIT Press |isbn=0-262-69060-8 |url-access=registration |url=https://archive.org/details/introductiontonu00star_0 }}

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