Перегляд вихідного коду сторінки Алгоритм Евкліда

[[Файл:Euclidean algorithm 252 105 animation flipped.gif|thumb|alt="Дві вертикальні лінії поділені рисочками на відрізки однакової довжини. На кожному кроці, довжина коротшого сегменту виділяється а потім видаляється з довшого сегменту. На останньому кроці, обидва сегменти однакові, і обидва видаляються."|Анімація алгоритму Евкліда для чисел 252 та 105. Рисочки відповідають числам кратним 21, найбільшому спільному дільникові (НСД). На кожному кроці менше число віднімають від більшого, поки одне з них не дорівнюватиме нулю. Число, що лишилось і є НСД.]]

'''Алгоритм Евкліда''' (також називається '''евклідів алгоритм''')&nbsp;— ефективний метод обчислення [[найбільший спільний дільник|найбільшого спільного дільника]] (НСД). Названий на честь [[Греція|грецького]] [[математика]] [[Евклід|Евкліда]], котрий описав його в книгах VII та X ''[[Начала Евкліда|Начал.]]''<ref>[[Thomas L. Heath]], ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref>

Найбільший спільний дільник двох чисел це найбільше число, що ділить обидва дані числа без остачі. Алгоритм Евкліда заснований на тому, що НСД не змінюється, якщо від більшого числа відняти менше. Наприклад, 21 є НСД чисел 252 та 105 ({{nowrap begin}}252 = 21 × 12;{{nowrap end}} {{nowrap begin}}105 = 21 × 5{{nowrap end}}); оскільки {{nowrap begin}}252 − 105 = 147{{nowrap end}}, НСД 147 та 105 також 21. Оскільки більше з двох чисел постійно зменшується, повторне виконання цього кроку дає все менші числа, поки одне з них не дорівнюватиме нулю. Коли одне з чисел дорівнюватиме нулю, те, що залишилось, і є НСД. Обертаючи кроки алгоритму Евкліда у зворотний порядок, НСД можна виразити як лінійну комбінацію даних чисел помножених на цілі коефіцієнти, наприклад {{nowrap begin}}21 = 5 × 105 + (−2) × 252.{{nowrap end}} Ця важлива властивість відома як [[рівняння Безу]].

Найдавніший опис алгоритму знаходиться в ''[[Начала]]х'' Евкліда (біля [[300 до н. е.]]), що робить його найдавнішим чисельним алгоритмом, яким користуються і нині. Оригінальний варіант алгоритму описував роботу лише з [[натуральні числа|натуральними числами]] та геометричними довжинами ([[дійсні числа|дійсними числами]]), алгоритм було узагальнено в [[19 століття|XIX столітті]] на роботу з іншими типами чисел, такими як [[Гаусові числа]] та [[поліном]]и з однією змінною. Це призвело до появи сучасних алгебраїчних понять, таких як Евклідові класи. Алгоритм Евкліда було узагальнено ще далі для роботи з іншими математичними структурами, такими як [[Вузол (математика)|вузли]] та поліноми від багатьох змінних.

Алгоритм Евкліда має багато застосувань на практиці, та в теорії. З його допомогою можна згенерувати практично всі найважливіші музичні ритми різних культур у всьому світі.<ref>[[Godfried Toussaint]], "The Euclidean algorithm generates traditional musical rhythms, " ''Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science'', Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47—56.</ref> Алгоритм Евкліда відіграє ключову роль в [[RSA|алгоритмі RSA]], поширеному методі криптографії з відкритим ключем. Його також використовують для пошуку розв'язків [[Діофантові рівняння|Діофантових рівнянь]], наприклад, пошук чисел, що задовільняють декільком умовам ([[Китайська теорема про залишки]]) або [[Обернене число|обернені числа]] в [[скінченне поле|скінченному полі]]. Алгоритм Евкліда також застосовують для побудови [[Ланцюгові дроби|ланцюгових дробів]] в [[метод Штурма|методі Штурма]] для пошуку дійсних коренів полінома, та в сучасних методах [[факторизація|факторизації цілих]]. Нарешті, він виступає простим інструментом для доведення теорем в [[теорія чисел|теорії чисел]], таких, як [[Теорема Лагранжа про чотири квадрати]] та [[Основна теорема арифметики|основної теореми арифметики]].

Алгоритм Евкліда ефективно обчислює НСД великих чисел, оскільки виконує операцій не більше, ніж вп'ятеро більше кількості цифр меншого числа (в десятковій системі). Цю властивість було доведено [[Габрієль Ламе|Ґабріелем Ламе]] ({{lang-en|Gabriel Lamé}}) в [[1844]] році, що позначило початок [[Теорія складності обчислень|теорії складності обчислень]]. Методи підвищення ефективності алгоритму були розроблені в [[20 століття|XX столітті]].

== Вступ ==

=== Найбільший спільний дільник ===

Алгоритм Евкліда обчислює найбільший спільний дільник (НСД) двох [[натуральні числа|натуральних чисел]] ''a'' та ''b''. Найбільший спільний дільник ''g''&nbsp;— це найбільше натуральне число яке ділить як ''a'' так і ''b'' без остачі. Найбільший спільний дільник також записують як НСД(''a'',&nbsp;''b'') або, простіше, (''a'',&nbsp;''b'')<ref>Stark, ст. 16.</ref> хоча останнє позначення використовують і для інших математичних понять, таких як координати двовимірних векторів.

Якщо НСД(''a'',&nbsp;''b'')&nbsp;=&nbsp;1, тоді ''a'' та ''b'' називають [[взаємно прості числа|взаємно простими]].<ref>Stark, ст. 21.</ref> Ця властивість не залежить від того, чи [[прості числа]] ''a'' та ''b''.<ref>LeVeque, ст. 32.</ref> Наприклад, ні 6 ні 35 не прості, оскільки їх можна розкласти на добутки 6&nbsp;=&nbsp;2&nbsp;×&nbsp;3 та 35&nbsp;=&nbsp;5&nbsp;×&nbsp;7. Однак, 6 та 35 взаємно прості. Жодне натуральне число окрім 1 не ділить водночас 6 та 35, оскільки у них нема спільних дільників.

[[Файл:Square tiling 24x60.svg|thumb|alt=«Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall.»|Прямокутник з ребрами 24 одиниці на 60 покрито квадратами з ребром 12 одиниць, де 12 це НСД 24 та 60. В загальному випадку, прямокутник з ребрами ''a'' на ''b'' може бути покрито квадратами з ребром ''c'' тоді і лише тоді, коли ''c'' є НСД ''a'' та ''b''.]]

Нехай ''g'' = НСД(''a'',&nbsp;''b''). Оскільки ''a'' та ''b'' є добутками ''g'', їх можна записати, як ''a''&nbsp;=&nbsp;''mg'' та ''b''&nbsp;=&nbsp;''ng'', і не існує більшого числа ''G''&nbsp;>&nbsp;''g'' з такою ж властивістю. Натуральні числа ''m'' та ''n'' мають бути взаємно простими, оскільки інший спільний дільник може бути виділений з ''m'' та ''n'', що збільшить ''g''. Таким чином, будь-яке число ''c'', що ділить ''a'' та ''b'' має ділити і ''g''. Найбільший спільний дільник ''g'' чисел ''a'' та ''b'' може бути визначений, як спільний дільник, який можна поділити іншим спільним дільником ''c''.<ref>Leveque, p. 31.</ref>

Поняття НСД можна проілюструвати наступним чином.<ref>{{cite book | author = Grossman JW | year = 1990 | title = Discrete Mathematics | publisher = Macmillan | location = New York | isbn = 0-02-348331-8 | page = 213}}</ref> Розглянемо прямокутник зі сторонами ''a'' та ''b'', та будь-який спільний дільник ''c'', що ділить і ''a'', і ''b'' без остачі. Ребра прямокутника можна поділити на відрізки довжиною ''c'', які поділять прямокутник на сітку квадратів зі стороною ''c''. Найбільший спільний дільник ''g'' дорівнює найбільшому можливому значенню ''c''. Наприклад, прямокутник 24 на 60 може бути покрита сіткою квадратів зі стороною 1, 2, 3, 6 або 12. Таким чином, 12 є найбільшим спільним дільником 24 та 60. Прямокутник 24 на 60 можна поділити сіткою квадратами з ребром 12, два квадрати вздовж одного ребра (24/12&nbsp;=&nbsp;2), та п'ятеро (60/12&nbsp;=&nbsp;5) вздовж іншого.

Найбільший спільний дільник ''a'' та ''b'' можна визначити як добуток спільних дільників обох чисел.<ref name="Schroeder_21" >Schroeder, ст. 21-22.</ref> Наприклад, оскільки 462 можна розкласти на добуток 2&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;11 а 1071 можна розкласти на добуток 3&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;17, найбільший спільний дільник 462 та 1071 дорівнює 21&nbsp;=&nbsp;3&nbsp;×&nbsp;7, добутку їхніх спільних дільників. Якщо два числа не мають спільних дільників, їх найбільший спільних дільник 1 і вони взаємно прості. Ключовою перевагою алгоритму Евкліда є ефективне знаходження НСД без необхідності обчислення дільників.<ref>Schroeder, ст. 19.</ref><ref>{{cite book | author = Ogilvy CS, Anderson JT | year = 1966 | title = Excursions in number theory | publisher = [[Oxford University Press]] | location = New York | id = {{LCCN|66|0|14484}} | pages = 27-29}}</ref> Розклад великих цілих чисел на дільники є криптографічно складною задачею, яка лежить в основі багатьох сучасних криптографічних систем.<ref name="Schroeder_216" >Schroeder, ст. 216—219.</ref>

НСД трьох або більшої кількості чисел дорівнює добутку дільників спільних для трьох чисел,<ref>Stark, p. 25.</ref> який можна обчислити на основі НСД пар чисел.<ref>Ore, pp. 47-48.</ref> Наприклад,

: НСД(''a'',&nbsp;''b'',&nbsp;''c'') = НСД(''a'',&nbsp;НСД(''b'',&nbsp;''c'')) = НСД(НСД(''a'',&nbsp;''b''),&nbsp;''c'') = НСД(НСД(''a'',&nbsp;''c''),&nbsp;''b'').

Тобто, алгоритм Евкліда обчислення найбільшого спільного дільника двох цілих підходить і для обчислення НСД довільної кількості цілих.

== Характеристики ==
=== Алгоритм ===

<math>{a} = {q_0} {b} + {r_0} \qquad \text{(0)}</math>

<math>{b} = {q_1} {r_0} + {r_1} \qquad \text{(1)}</math>

<math>{r_0} = {q_2} {r_1} + {r_2} \qquad \text{(2)}</math>

<math>{r_1} = {q_3} {r_2} + {r_3} \qquad \text{(3)}</math>

<math>\dots</math>

<math>{r_{n-3}} = {q_{n-1}} {r_{n-2}} + {r_{n-1}} \qquad \text{(n-1)}</math>

<math>{r_{n-2}} = {q_n} {r_{n-1}} + 0 \qquad \text{(n)}</math>

Алгоритм Евкліда ітеративний, тобто, пошук розв'язку відбувається за декілька кроків. Для того щоб знайти НСД(''a'', ''b'') на 0-му кроці знаходять остачу ''r''<sub>0</sub> від ділення ''a'' на ''b''. На 1-му кроці знаходять остачу від ділення ''b'' на ''r''<sub>0</sub>. Оскільки остачі зменшуються на кожному кроці але не можуть бути від'ємними, то цю операцію виконують ''n'' кроків до тих пір поки не отримують остачу 0. Найбільшим спільним дільником є остання не нульова остача ''r''<sub>''n''−1</sub>. Кількість кроків в алгоритмі має бути скінченною, оскільки існує лише скінченна кількість цілих чисел між початковою остачею ''r''<sub>0</sub> та нулем.

=== Доведення алгоритму Евкліда ===

Правильність алгоритму Евкліда можна довести за два кроки.<ref>Stark, ст. 16-20.</ref> Спочатку необхідно довести, що ''r''<sub>''n''−1</sub> дійсно є дільником ''a'' та ''b'', а потім необхідно довести, що це є найбільший спільний дільник.

==== Доведення, що <math>{r_{n-1}}</math> є дільником ''a'' та ''b'' ====
З n-го кроку випливає, що <math>~{r_{n-2}} \;\vdots\; {r_{n-1}}</math> (<math>{r_{n-2}}</math> ділиться на <math>{r_{n-1}}</math>). Підставимо <math>~{r_{n-2}}</math> в ''n-1''-й крок. Маємо:

<math>~{r_{n-3}} = {q_{n-1}} {q_n} {r_{n-1}} + {r_{n-1}}</math>

<math>~{r_{n-3}} = {r_{n-1}} ({q_{n-1}} {q_n}  + 1)</math>

Таким чином <math>~{r_{n-3}} \;\vdots\; {r_{n-1}}</math>. Повторимо цю операцію ''n'' разів і отримаємо, що <math>~{a} \;\vdots\; {r_{n-1}}</math> та <math>~{b} \;\vdots\; {r_{n-1}}</math>. Отже, <math>~{r_{n-1}}</math> є дільником ''a'' та ''b''.

==== Доведення, що <math>{r_{n-1}}</math> є найбільшим дільником ''a'' та ''b'' ====
За означенням число <math>~{d}</math> називається найбільшим спільним дільником ''a'' та ''b'', тоді і тільки тоді, коли для будь-якого числа <math>~ \forall {k}</math> для якого виконується: <math>~ {a} \;\vdots\; {k}</math> та <math>~{b} \;\vdots\; {k}</math> має виконуватись, що <math>~{d} \;\vdots\; {k}</math>.

Нехай ''k'' є дільником ''a'' та ''b'', тоді <math>~{a} \;\vdots\; {k}</math> та <math>~{b} \;\vdots\; {k}</math> або можна сказати, що існують такі числа <math>~{a_1}</math> та <math>~{b_1}</math>, що

<math>~{a} = {a_1} {k}</math>

<math>~{b} = {b_1} {k}</math>

Підставимо в 1-й крок алгоритму:

<math>~{a_1} {k} = {q_0} {b_1} {k} + {r_0} </math> і виконаємо перетворення:

<math>~{r_0} = {a_1} {k} - {q_0} {b_1} {k} </math>

<math>~{r_0} = {k} ({a_1} - {q_0} {b_1}) </math>

Отже, <math>~{r_0} \;\vdots\; {k}</math>. Підставимо <math>~{r_0}</math> в 2-й крок і аналогічно продовжимо до тих пір поки з останнього кроку не отримаємо, що <math>~{r_{n-1}} \;\vdots\; {k}</math>, що доводить те, що <math>~{r_{n-1}}</math> є найбільшим спільним дільником.

=== Реалізації ===

Реалізації алгоритму можна записати у [[псевдокод]]і. Наприклад, версію, основану на операції ділення, можна [[програма|запрограмувати]] наступним чином:<ref>Knuth, ст. 319—320.</ref>

 '''функція''' нсд(a, b)
     '''поки''' b ≠ 0
        t := b
        b := a '''mod''' b
        a := t
     '''поверни''' a

На початку ''k''-ї ітерації, змінна ''b'' має значення останньої остачі ''r''<sub>''k''−1</sub>, а змінна ''a'' має значення попередньої остачі ''r''<sub>''k''−2</sub>. Крок ''b'' := ''a'' mod ''b'' еквівалентний рекурсивній формулі ''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>. Допоміжна змінна ''t'' має значення ''r''<sub>''k''−1</sub> поки відбувається обчислення наступної остачі ''r''<sub>''k''</sub>. В кінці циклу, змінна ''b'' має значення остачі ''r''<sub>''k''</sub>, а змінна ''a'' має значення попередньої ''r''<sub>''k''−1</sub>.

В описаній Евклідом версії алгоритму, обчислення остачі (''b''&nbsp;=&nbsp;''a'' mod ''b'') замінено повторним відніманням.<ref>Knuth, ст. 318—319.</ref>

 '''функція''' нсд(a, b)
     '''якщо''' a = 0
        '''поверни''' b
     '''поки''' b ≠ 0
         '''якщо''' a > b
            a := a − b
         '''інакше'''
            b := b − a
     '''поверни''' a

Змінні ''a'' та ''b'' почергово набувають значення попередніх остач ''r''<sub>''k''−1</sub> та ''r''<sub>''k''−2</sub>. Якщо ''a'' більше за ''b'' на початку ітерації; тоді ''a'' дорівнює ''r''<sub>''k''−2</sub>, оскільки ''r''<sub>''k''−2</sub> > ''r''<sub>''k''−1</sub>. Протягом циклу, ''a'' зменшується на число, кратне попередній остачі ''b'' доки ''a'' не стане меншим за ''b''. Тоді ''a'' стає наступною остачею ''r''<sub>''k''</sub>. Потім ''b'' зменшується на число, кратне ''a'' поки не стане меншим за ''a'', даючи значення наступної остачі ''r''<sub>''k''+1</sub>, і так далі.

Рекурсивна версія <ref>Stillwell, ст. 14.</ref> основана на рівності НСД послідовних остач та умові зупинки НСД(''r''<sub>''N''−1</sub>,&nbsp;0)&nbsp;=&nbsp;''r''<sub>''N''−1</sub>.

 '''функція''' нсд(a, b)
     '''якщо''' b = 0
        '''поверни''' a
     '''інакше'''
        '''поверни''' нсд(b, a '''mod''' b)

Наприклад, НСД(1071,&nbsp;462) обчислюють на основі еквівалентного значення НСД(462,&nbsp;1071&nbsp;mod&nbsp;462)&nbsp;=&nbsp;НСД(462,&nbsp;147). Яке, в свою чергу, обчислюють на основі НСД(147,&nbsp;462&nbsp;mod&nbsp;147)&nbsp;=&nbsp;НСД(147,&nbsp;21), а це, обчислюють від НСД(21,&nbsp;147&nbsp;mod&nbsp;21)&nbsp;=&nbsp;НСД(21,&nbsp;0)&nbsp;=&nbsp;21.

=== Метод найменших абсолютних остач ===

В іншому варіанті реалізації алгоритму Евкліда на кожному кроці частку збільшують на 1 якщо отримане абсолютне значення від'ємної остачі менше за додатну остачу.<ref name="Ore_least_abs_remainders" >Ore, p. 43.</ref><ref name="Stewart_1964">{{cite book | author = Stewart BM | year = 1964 | title = Theory of Numbers | edition = 2nd | publisher = Macmillan | location = New York | id = {{LCCN|64|0|10964}} | pages = 43-44}}</ref> В інших версіях, в рівнянні

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>

припускалось, що ''r''<sub>''k''−1</sub>&nbsp;>&nbsp;''r''<sub>''k''</sub>&nbsp;>&nbsp;0. Однак, іншу від'ємну остачу ''e''<sub>''k''</sub> можна обчислити таким чином:

: ''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> + 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>

де ''r''<sub>''k''−1</sub> вважається додатнім. Якщо |''e''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''</sub>|, тоді ''r''<sub>''k''</sub> замінюють на ''e''<sub>''k''</sub>. Як показано [[Леопольд Кронекер|Леопольдом Кронекером]], цей варіант витрачає найменшу кількість кроків у порівнянні з іншими варіантами алгоритму.<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" />

== Історія ==
[[Файл:Euklid.jpg|thumb|Ймовірно, алгоритм Евкліда було відкрито за століття до народження Евкліда, показаного на картині з [[Циркуль|циркулем]].]]

Алгоритм Евкліда один з найдавніших [[алгоритм]]ів, що досі використовують.<ref name=":0">Knuth, p. 318.</ref> Він описаний в [[Начала Евкліда|Началах Евкліда]] (приблизно [[300 до н. е.]]), а саме, в книгах VII та X. В сьомій книзі алгоритм описано для [[цілі числа|цілих чисел]], а в десятій&nbsp;— для довжин відрізків. Можна сказати, що алгоритм описано для [[дійсні числа|дійсних чисел]]. Однак, довжина, площа та об'єм, що їх вимірюють нині в дійсних числах, вимірюють у різних одиницях та не існує універсальної природної одиниці для вимірювання довжини, площі або об'єму. Також поняття дійсних чисел в ті часи було ще не відоме. Другий алгоритм геометричний. НСД двох довжин ''a'' та ''b'' відповідає довжині найдовшого відрізку ''g'', яким можна виміряти ''a'' та ''b'' без остачі; іншими словами, довжини відрізків ''a'' та ''b'' дорівнюють добуткові довжини ''g'' на ціле число.

Можливо, алгоритм було відкрито не Евклідом, а він лише використав результати, отримані попередниками в ''Началах''.<ref name="Weil_1983">{{cite book | author = [[Андре Вейль|Weil A]] | year = 1983 | title = Number Theory | publisher = Birkhäuser | location = Boston | isbn = 0-8176-3141-0 | pages = 4–6}}</ref><ref name="Jones_1994">{{cite book | author = Jones A | year = 1994 | chapter = Greek mathematics to AD 300 | title = Companion encyclopedia of the history and philosophy of the mathematical sciences | publisher = Routledge | location = New York | isbn = 0-415-09238-8 | pages = 46–48}}</ref> Математик та історик [[Ван дер Варден]] вважає, що книгу VII написано на основі підручника з [[теорія чисел|теорії чисел]] авторства одного з математиків школи [[Піфагор]]а.<ref name="van_der_Waerden_1954">{{cite book | author = [[Bartel Leendert van der Waerden|van der Waerden BL]] | year = 1954 | title = Science Awakening | series = translated by Arnold Dresden | publisher = P. Noordhoff Ltd | location = Groningen | pages = 114–115}}</ref> Ймовірно, алгоритм був відомий ще [[Евдокс Кнідський|Евдоксу Кіндському]] (приблизно [[375 до н. е.]]).<ref name=":0"/><ref>{{cite journal | author = von Fritz K | date = 1945 | title = The Discovery of Incommensurability by Hippasus of Metapontum | url = https://archive.org/details/sim_annals-of-mathematics_1945-04_46_2/page/242 | journal = Ann. Math. | volume = 46 | pages = 242–264 | doi = 10.2307/1969021}}</ref> Можливо, навіть, алгоритм був відомий ще до Евдокса,<ref>{{cite book | author = [[T. L. Heath|Heath TL]] | year = 1949 | title = Mathematics in Aristotle | publisher = Oxford Press | pages = 80–83}}</ref><ref>{{cite book | author = [[David Fowler (mathematician)|Fowler DH]] | year = 1987 | title = The Mathematics of Plato's Academy: A New Reconstruction | url = https://archive.org/details/mathematicsofpla0000fowl_h9l3 | publisher = Oxford University Press | location = Oxford | isbn = 0-19-853912-6 | pages = [https://archive.org/details/mathematicsofpla0000fowl_h9l3/page/31 31]–66}}</ref> судячи з використання поняття {{lang-el|ἀνθυφαίρεσις}} (''антифарезис'') в роботах Евкліда та [[Арістотель|Арістотеля]].<ref>{{cite journal | author = Becker O | year = 1933 | title = Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid | journal = Quellen und Studien zur Geschichte der Mathematik B | volume = 2 | pages = 311–333}}</ref>

Нові можливості застосування алгоритму Евкліда було знайдено в [[19 століття|XIX]] столітті. В [[1829]] році [[Чарльз Штурм]] застосував алгоритм Евкліда в [[метод Штурма|методі Штурма]] для пошуку дійсних коренів поліномів у заданому інтервалі.<ref>{{cite journal | author = Sturm C | year = 1829 | title = Mémoire sur la résolution des équations numériques | journal = Bull. des sciences de Férussac | volume = 11 | pages = 419–422}}</ref>

== Алгоритмічна ефективність ==
[[Файл:Euclidean algorithm running time X Y.png|thumb|alt=«Множина кольорових ліній що виходять з початку декартової системи координат. Кожна лінія відповідає множині пар чисел, для обчислення НСД яких необхідна однакова кількість кроків за алгоритмом Евкліда.»|Кількість кроків необхідних для обчислення НСД(x, y) за алгоритмом Евкліда. Червоним позначено точки, які вимагають порівняно небагато кроків (швидке обчислення), жовтими, зеленими та синіми позначено більшу кількість кроків у порядку зростання (повільне обчислення).]]

Обчислювальну ефективність алгоритму Евкліда ретельно досліджено.<ref>Knuth, pp. 339–364.</ref> Ефективність роботи можна описати як необхідну алгоритму кількість кроків помножену на обчислювальні витрати кожного кроку. Як було показано Ґабріелєм Ламі в 1844 році,<ref>{{cite journal | author = [[Gabriel Lamé|Lamé G]] | year = 1844 | title = Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers | journal = Comptes Rendus Acad. Sci. | volume = 19 | pages = 867–870}}</ref> кількість необхідних кроків ніколи не більша за кількість цифр ''h'' (в [[десяткова система числення|десятковій системі]]) меншого з чисел&nbsp;''b'' помножена на 5.<ref>{{cite journal | author = Grossman H | year = 1924 | title = On the Number of Divisions in Finding a G.C.D. | url = https://archive.org/details/sim_american-mathematical-monthly_1924-11_31_9/page/443 | journal = The American Mathematical Monthly | volume = 31 | page = 443 | doi = 10.2307/2298146}}</ref><ref>{{cite book | author = Honsberger R | year = 1976 | title = Mathematical Gems II | publisher = The [[Mathematical Association of America]] | isbn = 0-88385-302-7 | pages = 54–57}}</ref> Оскільки обчислювальні витрати кожного кроку зазвичай порядку ''h'', загальні витрати зростають на рівні&nbsp;''h''<sup>2</sup>.

=== Кількість кроків ===
Кількість кроків необхідних для обчислення НСД пари натуральних чисел, ''a'' та ''b'', можна позначити як ''T''(''a'',&nbsp;''b'').<ref name=":1">Knuth, p. 344.</ref> Якщо ''g'' є НСД ''a'' та ''b'', тоді ''a''&nbsp;=&nbsp;''mg'' та ''b''&nbsp;=&nbsp;''ng'' де ''m'' та ''n'' взаємно прості числа. Тоді

: ''T''(''a'', ''b'') = ''T''(''m'', ''n'')

що можна отримати поділивши всі кроки алгоритму на ''g''.<ref>Ore, p. 45.</ref> Аналогічно, кількість кроків лишається незмінною якщо ''a'' та ''b'' помножити на спільний дільник ''w'': ''T''(''a'', ''b'') = ''T''(''wa'', ''wb''). Таким чином, кількість кроків ''T'' може сильно відрізнятись для пари сусідніх чисел, наприклад ''T''(''a'', ''b'') та ''T''(''a'',&nbsp;''b''&nbsp;+&nbsp;1), в залежності від розміру обох НСД.

Рекурсивна природа алгоритму Евкліда дає наступне рівняння

: ''T''(''a'', ''b'') = 1 + ''T''(''b'', ''r''<sub>0</sub>) = 2 + ''T''(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = ''N'' + ''T''(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''N'' + 1

де ''T''(''x'', 0)&nbsp;=&nbsp;0 за припущенням.<ref name=":1"/>

==== Кількість кроків у найгіршому випадку ====

Якщо алгоритму Евкліда необхідні ''N'' кроків для обчислення НСД натуральних чисел ''a''&nbsp;>&nbsp;''b''&nbsp;>&nbsp;0, то найменші числа, для яких це дійсне, є [[число Фібоначчі|числа Фібоначчі]] ''F''<sub>''N''+2</sub> та ''F''<sub>''N''+1</sub>.<ref name=":2">Knuth, p. 343.</ref> Цю властивість можна довести методом [[математична індукція|математичної індукції]].<ref>Mollin, p. 21.</ref> Якщо ''N''&nbsp;=&nbsp;1, ''b'' ділить ''a'' без остачі; найменші натуральні числа, для яких це правильно&nbsp;— ''b''&nbsp;=&nbsp;1 та ''a''&nbsp;=&nbsp;2, які дорівнюють ''F''<sub>2</sub> та ''F''<sub>3</sub> відповідно. Припустімо, що це правильно для значень ''N'' не більших за ''M''&nbsp;−&nbsp;1. Першим кроком ''M''-крокового алгоритму є ''a''&nbsp;=&nbsp;''q''<sub>0</sub>''b''&nbsp;+&nbsp;''r''<sub>0</sub>, а другим ''b''&nbsp;=&nbsp;''q''<sub>1</sub>''r''<sub>0</sub>&nbsp;+&nbsp;''r''<sub>1</sub>. Оскільки алгоритм рекурсивний, йому необхідно ''M''&nbsp;−&nbsp;1 кроків для знаходження НСД(''b'',&nbsp;''r''<sub>0</sub>) та найменшими значеннями є ''F''<sub>''M''+1</sub> та ''F''<sub>''M''</sub>. Таким чином, ''a'' має найменше значення коли ''q''<sub>0</sub>&nbsp;=&nbsp;1, що значить ''a''&nbsp;=&nbsp;''b''&nbsp;+&nbsp;''r''<sub>0</sub>&nbsp;=&nbsp;''F''<sub>''M''+1</sub>&nbsp;+&nbsp;''F''<sub>''M''</sub>&nbsp;=&nbsp;''F''<sub>''M''+2</sub>. Це доведення, оприлюднене Ґабріелем Ламі в 1844 заклало основи [[теорія складності обчислень|теорії обчислювальної складності]],<ref>LeVeque, p. 35.</ref> а також є першим застосуванням чисел Фібоначчі на практиці.<ref name=":2"/>

Цього результату достатньо, аби показати, що алгоритм Евкліда виконує кроків не більше, ніж вп'ятеро більше кількості цифр меншого числа (в [[десяткова система числення|десятковій системі]]).<ref>Mollin, pp. 21–22.</ref> Якщо алгоритму потрібно більше ''N'' кроків, тоді ''b'' більше або дорівнює ''F''<sub>''N''+1</sub>, що, в свою чергу. більше або дорівнює ''φ''<sup>''N''−1</sup>, де ''φ'' дорівнює [[золотий перетин|золотому перетину]]. Оскільки ''b''&nbsp;≥&nbsp;''φ''<sup>''N''−1</sup>, тоді ''N''&nbsp;−&nbsp;1&nbsp;≤&nbsp;log<sub>''φ''</sub>''b''. Оскільки log<sub>10</sub>''φ''&nbsp;>&nbsp;1/5, (''N''&nbsp;−&nbsp;1)/5&nbsp;<&nbsp;log<sub>10</sub>''φ''&nbsp;log<sub>''φ''</sub>''b''&nbsp;=&nbsp;log<sub>10</sub>''b''. Таким чином, ''N''&nbsp;≤&nbsp;5&nbsp;log<sub>10</sub>''b''. Звідси випливає, що алгоритм Евкліда потребує менше за [[Нотація Ландау|''O''(''h'')]] ділень, де ''h'' дорівнює кількості цифр в меншому числі ''b''.

==== Середня кількість кроків ====
Середню кількість кроків необхідних алгоритму Евкліда було визначено в три різні способи. Перше визначення, це середній час ''T''(''a'') необхідний для обчислення НСД заданого числа ''a'' та меншого натурального числа ''b'' обраного з рівною ймовірністю з цілих від 0 до ''a''&nbsp;-&nbsp;1<ref name=":1"/>

:<math>
T(a) = \frac{1}{a} \sum_{0 \leq b<a} T(a, b).
</math>

Однак, оскільки ''T''(''a'',&nbsp;''b'') істотно змінюється в залежності від НСД обох чисел, усереднена функція ''T''(''a'') також містить «шум».<ref>Knuth, p. 353.</ref>

Аби зменшити цей шум, використовують друге середнє τ(''a'') для взаємно простих до ''a'' чисел.

:<math>
\tau(a) = \frac{1}{\varphi(a)} \sum_{0 \leq b<a, \mathrm{GCD}(a, b) = 1} T(a, b).
</math>

Всього існує ''φ''(''a'') взаємно простих чисел менших за ''a'', де ''φ'' це [[функція Ейлера]]. Значення τ поступово зростає разом з ''a''<ref>Knuth, p. 357.</ref><ref>{{cite journal | author = Tonkov T | year = 1974 | title = On the average length of finite continued fractions | journal = Acta arithmetica | volume = 26 | pages = 47–57}}</ref>

:τ(''a'') = (12/π<sup>2</sup>) ln 2 ln a + ''C'' + [[Нотація Ландау|''O''(''a''<sup>−(1/6) + ε</sup>)]]

з похибкою порядку ''a''<sup>−(1/6) + ε</sup>, де ε [[нескінченно мала величина|нескінченно мала]]. Стала ''C'' в цій формулі дорівнює

:''C'' = −(1/2) + 6 (ln 2/π<sup>2</sup>)( 4γ − 24π<sup>2</sup>ζ&nbsp;'(2) + 3 ln 2 − 2) ≈ 1.467

де γ це [[Стала Ейлера — Маскероні]], а ζ'&nbsp;— [[похідна]] [[Дзета-функція Рімана|дзета-функції Рімана]].<ref>{{cite journal | author = Porter JW | year = 1975 | title = On a Theorem of Heilbronn | journal = Mathematika | volume = 22 | pages = 20–28}}</ref><ref>{{cite journal | author = Knuth DE | year = 1976 | title = Evaluation of Porter's Constant | url = https://archive.org/details/sim_computers-mathematics-with-applications_1976_2/page/137 | journal = Computers and Mathematics with Applications | volume = 2 | pages = 137–139 | doi = 10.1016/0898-1221(76)90025-0}}</ref> Значення основного коефіцієнту {{nowrap begin}}(12/π<sup>2</sup>) ln 2{{nowrap end}} було визначено двома незалежними методами.<ref>{{cite journal | author = Dixon JD | year = 1970 | title = The Number of Steps in the Euclidean Algorithm | journal = J. Number Theory | volume = 2 | pages = 414–422 | doi = 10.1016/0022-314X(70)90044-2}}</ref><ref>{{cite book | author = Heilbronn HA | year = 1969 | chapter = On the Average Length of a Class of Finite Continued Fractions | title = Number Theory and Analysis | editor = Paul Turán | publisher = Plenum | location = New York | id = {{LCCN|68|00|8991}} | pages = 87–96}}</ref>

Оскільки перше середнє може бути обчислене на основі тау середнього додаванням дільників ''d'' числа ''a''<ref>Knuth, p. 354.</ref>

:<math>
T(a) = \frac{1}{a} \sum_{d | a} \varphi(d) \tau(d)
</math>

воно може бути наближене формулою<ref name="Norton_1990">{{cite journal | author = Norton GH | year = 1990 | title = On the Asymptotic Analysis of the Euclidean Algorithm | journal = Journal of Symbolic Computation | volume = 10 | pages = 53–58 | doi = 10.1016/S0747-7171(08)80036-3}}</ref>

:''T''(''a'') ≈ ''C'' + (12/π<sup>2</sup>) ln 2 ( ln ''a'' − Σ<sub>''d''|''a''</sub> Λ(''d'')/''d'' )

де Λ(''d'')&nbsp;— [[функція фон Мангольда]].<ref>Knuth, p. 355.</ref>

Третє середнє ''Y''(''n'') визначають як середню кількість кроків необхідних для обчислення НСД коли ''a'' та ''b'' випадкові числа (рівномірно розподілені) від 1 до ''n''<ref name="Norton_1990" />

:<math>
Y(n) = \frac{1}{n^{2}} \sum_{a=1}^{n} \sum_{b=1}^{n} T(a, b) = \frac{1}{n} \sum_{a=1}^{n} T(a).
</math>

Заміна наближеною формулою для ''T''(''a'') в це рівняння дає оцінку ''Y''(''n'')<ref>Knuth, p. 356.</ref>

:''Y''(''n'') ≈ (12/π<sup>2</sup>) ln 2 ln ''n'' + 0.06.

=== Обчислювальні витрати за крок ===

На кожному кроці ''k'' алгоритму Евкліда, обчислюють [[частка|частку]] ''q''<sub>''k''</sub> та [[Остача|остачу]] ''r''<sub>''k''</sub> для пари цілих ''r''<sub>''k''−2</sub> та ''r''<sub>''k''−1</sub>

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>.

Основні витрати за крок полягають в обчисленні ''q''<sub>''k''</sub>, оскільки остача ''r''<sub>''k''</sub> можна швидко обчислити на основі ''r''<sub>''k''−2</sub>, ''r''<sub>''k''−1</sub> та ''q''<sub>''k''</sub>

: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>.

Обчислювальна складність ділення ''h''-бітних чисел змінюються як ''O''(''h''(''ℓ''+1)), де ''ℓ''&nbsp;— довжина частки.<ref>Knuth, pp. 257–261.</ref>

Для порівняння, оригінальний варіант алгоритму на основі віднімання може бути набагато повільнішим. Ділення цілого еквівалентне ''q'' віднімань, де ''q''&nbsp;— частка. Якщо відношення ''a'' до ''b'' велике, частка буде також великою і знадобиться велика кількість віднімань. З іншого боку, було показано, що частки найімовірніше матимуть невеликі значення. Ймовірність отримати частку ''q'' приблизно ln|''u''/(''u''&nbsp;−&nbsp;1)| де ''u''&nbsp;=&nbsp;(''q''&nbsp;+&nbsp;1)<sup>2</sup>.<ref>Knuth, p. 352.</ref> Наприклад, ймовірність отримати частку 1, 2, 3, або 4 дорівнює приблизно 41.5%, 17.0%, 9.3%, та 5.9%, відповідно. Оскільки операція віднімання швидша за ділення, особливо для великих чисел,<ref>{{cite book | author = Wagon S | year = 1999 | title = Mathematica in Action | publisher = Springer-Verlag | location = New York | isbn = 0-387-98252-3 | pages = 335–336}}</ref> оснований на відніманні алгоритм Евкліда може бути на рівні з основаним на діленні.<ref>Cohen, p. 14.</ref> Цю властивість використано в [[бінарний алгоритм Евкліда|бінарному алгоритмі Евкліда]].<ref>Cohen, pp. 14–15, 17–18.</ref>

Поєднання оцінки кількості кроків з оцінкою обчислювальних витрат на крок показує, що витрати алгоритму Евкліда зростають квадратично (''h''<sup>2</sup>) в залежності від середньої кількості цифр ''h'' в заданих числах. Нехай ''h''<sub>0</sub>, ''h''<sub>1</sub>, …, ''h''<sub>''N''−1</sub> дорівнює кількості цифр в послідовних остачах ''r''<sub>0</sub>,&nbsp;''r''<sub>1</sub>,&nbsp;…,&nbsp;''r''<sub>''N''−1</sub>. Оскільки кількість кроків ''N'' зростає пропорційно ''h'', час роботи алгоритму обмежено

:<math>
O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2)\Big)\subseteq O(h(h_0+2N))\subseteq O(h^2).</math>

== Приклад ==

Обчислимо НСД чисел 1071 та 1029.

{| border="1" cellpadding="5"
| || || a || b || Пояснення
|-
| || НСД(|| 1071, || 1029) || Початкові аргументи
|-
| = || НСД(|| 1029, || 42) || 1071 mod 1029 = 42
|-
| = || НСД(|| 42, || 21) || 1029 mod 42 = 21
|-
| = || НСД(|| 21, || 0) || 42 mod 21 = 0
|-
| = || || 21 || || Оскільки b=0, то повертаємо a=21
|}
----
У випадку невеликих чисел, можна використати послідовне ділення у стовпчик. Наприклад, нам потрібно знайти НСД (2700, 1520):

<div style='text-align: center;'>
[[Файл:Найбільший спільний дільник чисел 2700 та 1520.svg]]
</div>

Отже, НСД (2700, 1520) = 20.

== Див. також ==
{{Портал|Математика}}
* [[Найбільший спільний дільник]]
* [[Розкладання на прості множники]]
* [[Розширений алгоритм Евкліда]]

== Посилання ==
{{reflist|2}}

== Джерела ==
* {{TAOCP.v2}}

{{Алгоритми теорії чисел}}
[[Категорія:Елементарна математика]]
[[Категорія:Теорія чисел]]
[[Категорія:Евклід]]