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

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

Кожны крок пачынаецца з двума неадмоўнымі астаткамі 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 павінен аказацца роўным нулю, на гэтым кроку алгарытм спыняецца^[3]. Апошні ненулявы астатак r_N−1 і ёсць найбольшы агульны дзельнік a і b. Нумар кроку N абавязкова канечны, бо існуе толькі канечная колькасць неадмоўных цэлых лікаў паміж пачатковым астаткам r₀ і нулём.

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

function gcd(a, b)
    r₀ := a
    r₁ := b
    i := 1
    while r_i ≠ 0
       r_i+1 := r_i-1 mod r_i
       i := i + 1
    if i ≤ 2 then return |r_i-1|
    return r_i-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. Такіх адніманняў будзе два (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) праз разкладанне лікаў на простыя множнікі. Пройдзеныя крокі можна прадставіць табліцай

Крок k	Роўнасць	Дзель і астатак
0	1071 = q₀ 462 + r₀	q₀ = 2 and r₀ = 147
1	462 = q₁ 147 + r₁	q₁ = 3 and r₁ = 21
2	147 = q₂ 21 + r₂	q₂ = 7 and r₂ = 0; алгарытм завяршаецца

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

Алгарытм Эўкліда можна візуалізаваць з дапамогай пакрыцця прамавугольнікаў квадратнымі пліткамі^[5]. Дапусцім, што трэба роўна пакрыць 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 іначай)^[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, колькасць крокаў будзе найменшая, калі і толькі калі q_k выбіраецца так, што $\left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\approx 0.618,$ дзе $\varphi$ — залатое сячэнне^[8].

Зноскі

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

Літаратура

Виноградов И. М. Основы теории чисел.
Курант Р., Роббинс Г. Дополнение к главе I, § 4. // Что такое математика? — 3-e изд., испр. и доп. — М., 2001. — 568 с.
Абрамов С. Самый знаменитый алгоритм // Квант. — 1985. — № 11. — С. 44—46.
Щетников А. И. Алгоритм Евклида и непрерывные дроби. — Новосибирск: АНТ, 2003.
Cohn, H. (1962). Advanced Number Theory. New York: Dover. ISBN 0-486-64023-X.
Knuth, Donald (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison–Wesley. ISBN 0-201-89684-2.
Ore, Øystein (1948). Number Theory and Its History. New York: McGraw–Hill.
Stark, Harold (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8.

[1] Heath, Thomas L. (1956) [1925]. The Thirteen Books of Euclid's Elements (2nd ed.). Dover Publications.

[Cohn_1962-2] Cohn 1962, pp. 104–110

[3] Stark 1978, p. 18

[4] Knuth 1997, pp. 319–320

[Kimberling_1983-5] Kimberling C (1983). "A Visual Euclidean Algorithm". Mathematics Teacher. 76: 108–109.

[Ore_least_abs_remainders-6] а ^б Ore 1948, p. 43

[Stewart_1964-7] а ^б Stewart, B. M. (1964). Theory of Numbers (2nd ed.). New York: Macmillan. pp. 43–44. LCCN 64010964.

[8] Lazard, D. (1977). "Le meilleur algorithme d'Euclide pour K[X] et Z" [Best Euclidean algorithm for K[X] and Z]. Comptes Rendus Acad. Sci.(фр.). 284. Paris: 1–4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]