Перегляд вихідного коду сторінки Двійковий алгоритм обчислення найбільшого спільного дільника

← Двійковий алгоритм обчислення найбільшого спільного дільника

У Вас нема дозволу на редагування цієї сторінки з такої причини:

Ваша IP-адреса знаходиться в діапазоні, який заблоковано у всіх вікі Фонду Вікімедіа.

Блокування зроблено ‪EPIC‬. Причиною вказано Open proxy/Webhost: See the help page if you are affected.

Початок блокування: 08:48, 2 липня 2024
Закінчення блокування: 08:48, 2 липня 2025

Ваша поточна IP-адреса: 206.189.44.186. Заблокований діапазон — 206.189.32.0/20.

Будь ласка, додайте всі вказані подробиці до будь-яких запитів, які Ви будете робити. Якщо ви вважаєте, що вас заблокували помилково, ви можете знайти додаткову інформацію та інструкції в глобальній політиці Без відкритих проксі.

В іншому випадку, щоб обговорити блокування, будь ласка, опублікуйте запит на розгляд на Мета-вікі. Ви також можете надіслати електронний лист до VRT-черги стюардів за адресою stewards@wikimedia.org, вказавши усю вищезазначену інформацію.

Ви можете переглянути та скопіювати вихідний текст цієї сторінки:

[[Файл:binary_GCD_algorithm_visualisation.svg|thumb|upright=1.8|Візуалізація використання двійкового алгоритму Евкліда для обчислення найбільшого спільного дільника (НСД) чисел 36 і 24. Отже, НСД рівний 2<sup>2</sup> &times; 3 = 12.]]

'''Двійковий алгоритм обчислення НСД''', також відомий як '''алгоритм Стайна''' або '''двійковий алгоритм Евкліда'''&nbsp;— алгоритм, що обчислює [[найбільший спільний дільник]] двох невід'ємних цілих чисел. Двійковий алгоритм Евкліда використовує простіші арифметичні операції, ніж звичайний [[алгоритм Евкліда]]: він замінює ділення бітовим зсувом, порівняннями та відніманням. Хоча вперше його опублікував ізраїльський фізик і програміст Джозеф Стайн 1967 року<ref>{{Citation |first=J. |last=Stein |title=Computational problems associated with Racah algebra |journal=Journal of Computational Physics |volume= 1 |issue=3 |pages=397–405 |year=1967 |issn=0021-9991 |doi=10.1016/0021-9991(67)90047-2}}</ref>, алгоритм міг бути відомим ще в першому столітті в Китаї<ref name="Knuth98">{{Citation |first=Donald |last=Knuth |authorlink=Donald Knuth |series=[[The Art of Computer Programming]] |volume=2 |title=Seminumerical Algorithms |edition=3rd |publisher=Addison-Wesley |isbn=0-201-89684-2 |year=1998 }}</ref>.

== Алгоритм ==

Алгоритм обчислює НСД застосовуючи такі тотожності:

# НСД(0, ''v'') = ''v'', тому що нуль ділиться на всі числа, а ''v''&nbsp;— найбільший дільник числа ''v''. Аналогічно НСД(''u'', 0) = ''u''. НСД(0, 0) зазвичай невизначено, але зручно вважати, що НСД(0, 0) = 0.
# Якщо ''u'' і ''v'' парні, то НСД(''u'', ''v'') = 2·НСД(''u''/2, ''v''/2), тому що 2&nbsp;— спільний дільник.
# Якщо ''u'' парне, а ''v'' непарне, то НСД(''u'', ''v'') = НСД(''u''/2, ''v''), тому що 2 не спільний дільник. Аналогічно якщо ''u'' непарне, а ''v'' парне, то НСД(''u'', ''v'') = НСД(''u'', ''v''/2).
# Якщо ''u'' і ''v'' непарні та ''u'' > ''v'', то НСД(''u'', ''v'') = НСД((''u''&nbsp;— ''v'')/2, v), якщо ж ''u'' < ''v'', то НСД(''u'', ''v'') = НСД(''u'', (''v''&nbsp;— ''u'')/2). Це комбінація одного кроку звичайного алгоритму Евкліда, де на кожному кроці застосовується віднімання, із подальшим застосуванням кроку 3. Різниця двох непарних чисел завжди буде парною, тому ділення на два дає ціле число.
# Кроки 2-4 повторюють поки ''u'' не стане рівним ''v'', або поки ''u'' не стане 0 (на один крок більше). У будь-якому випадку результат дорівнюватиме 2<sup>''k''</sup>×''v'', де ''k''&nbsp;— кількість спільних дільників 2, знайдених на кроці 2.

У найгіршому випадку алгоритм потребує O(n<sup>2</sup>)<ref name="gmplib">{{Cite web |url=http://gmplib.org/manual/Binary-GCD.html |title=Архівована копія |accessdate=4 листопада 2018 |archive-date=5 листопада 2018 |archive-url=https://web.archive.org/web/20181105160604/https://gmplib.org/manual/Binary-GCD.html }}</ref> часу, де n&nbsp;— кількість біт у більшому з двох чисел. Хоча кожен крок зменшує хоча б одне число принаймні вдвічі, для дуже великих чисел віднімання та зсув потребують лінійного часу (втім, на практиці вони доволі швидкі).

Розширений двійковий алгоритм обчислення НСД, аналогічний до [[Розширений алгоритм Евкліда|розширеного алгоритму Евкліда]], описав [[Дональд Кнут]] у другому томі «[[Мистецтво програмування|Мистецтва програмування]]».<ref>{{Harvnb|Knuth|1998|p=646}}, answer to exercise 39 of section 4.5.2</ref><ref>{{Cite web|url=http://cacr.uwaterloo.ca/hac/about/chap14.pdf|title=Handbook of Applied Cryptography|last=|first=|date=|website=|archive-url=https://web.archive.org/web/20190202141729/http://cacr.uwaterloo.ca/hac/about/chap14.pdf|archive-date=2 лютого 2019|dead-url=|access-date=2017-09-09}}</ref>

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

=== Рекурсивна реалізація на C ===
Реалізація схожа на опис алгоритму зверху. Усі рекурсивні виклики (крім одного) є [[Хвостова рекурсія|хвостовою рекурсією]].

<syntaxhighlight lang="cpp">
unsigned int gcd(unsigned int u, unsigned int v)
{
    // прості випадки (завершення)
    if (u == v)
        return u;

    if (u == 0)
        return v;

    if (v == 0)
        return u;

    // обчислення кількості двійок
    if (~u & 1) // u - парне
    {
        if (v & 1) // v - непарне
            return gcd(u >> 1, v);
        else // v - парне
            return gcd(u >> 1, v >> 1) << 1;
    }

    if (~v & 1) // u - непарне, v - парне
        return gcd(u, v >> 1);

    // зменшення більшого аргументу
    if (u > v)
        return gcd((u - v) >> 1, v);

    return gcd((v - u) >> 1, u);
}</syntaxhighlight>

=== Ітеративна реалізація на C ===

Ітеративна реалізація спочатку позбувається спільного дільника 2 застосовуючи рівність&nbsp;2, потім обчислює НСД, застосовуючи рівності 3 і&nbsp;4.

<syntaxhighlight lang="cpp">
unsigned int gcd(unsigned int u, unsigned int v)
{
  int shift;

  /* НСД(0,v) == v; НСД(u,0) == u, НСД(0,0) == 0 */
  if (u == 0) return v;
  if (v == 0) return u;
 
  /* Нехай shift := lg K, де K — найбільша степінь двійки, що ділить u і v */
  for (shift = 0; ((u | v) & 1) == 0; ++shift) {
         u >>= 1;
         v >>= 1;
  }
 
  while ((u & 1) == 0)
    u >>= 1;
 
  /* Починаючи звідси, u завжди непарне. */
  do {
       /* позбудемось всіх дільників 2 в v -- вони не спільні */
       /*   зауваження: v не 0, тож цикл завершиться */
       while ((v & 1) == 0)  /* Loop X */
           v >>= 1;
       /* Тепер u і v - непарні. Якщо потрібно обміняємо їх, щоб u <= v,
          тоді встановимо v = v - u (парне число). Для довгих чисел
          обмін - всього переміщення вказівників, і віднімання
          можна зробити на місці */
       if (u > v) {
         unsigned int t = v; v = u; u = t; // Обмін u і v.
       }
       
       v = v - u; // Тут v >= u.
     } while (v != 0);

  /* Відновлюємо спільні дільники 2 */
  return u << shift;
}
</syntaxhighlight>

== Ефективність ==
Доведено, що в теорії, двійковий алгоритм обчислення НСД в середньому на 60&nbsp;% ефективніший, ніж алгоритм Евкліда (у термінах кількості бітових операцій).<ref>{{Citation | first = Ali | last = Akhavi | first2 = Brigitte | last2 = Vallee | title = AverageBit-Complexity of Euclidean Algorithms | year = 2000 | date =  | journal = Proceedings ICALP'00, Lecture Notes Computer Science 1853 | volume =  | issue =  | pages = 373&ndash;387 | url = http://users.info.unicaen.fr/~brigitte/Publications/icalp8-2000.ps | id = [[CiteSeerX]]: [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.7616 10.1.1.42.7616] | deadurl = yes | archiveurl = https://web.archive.org/web/20061002120425/http://users.info.unicaen.fr/~brigitte/Publications/icalp8-2000.ps | archivedate = 2006-10-02 | df =  }}</ref><ref>{{Citation |last=Brent |first=Richard P. |title=Twenty years' analysis of the Binary Euclidean Algorithm |year=2000 |date= |journal=Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in honour of Professor Sir Antony Hoare |location=Palgrave, NY |volume= |issue= |pages=41&ndash;53 |url=http://wwwmaths.anu.edu.au/~brent/pub/pub183.html |doi= |accessdate=4 листопада 2018 |archive-date=15 квітня 2012 |archive-url=https://web.archive.org/web/20120415011438/http://wwwmaths.anu.edu.au/~brent/pub/pub183.html }} proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.</ref><ref name="Stepanov">[http://www.stepanovpapers.com/notes.pdf Notes on Programming] {{Webarchive|url=https://web.archive.org/web/20181125231835/http://stepanovpapers.com/notes.pdf |date=25 листопада 2018 }} by [[Alexander Stepanov]]</ref> Однак, хоч на практиці цей алгоритм дещо перевершує звичайний алгоритм Евкліда, його [[Нотація Ландау|асимптотична складність]] така ж сама, а реалізація непомірно складніша, особливо враховуючи загальнодоступність інструкції цілочисельного ділення на всіх сучасних мікропроцесорах.<ref name="Stokes2007">{{cite book|author=Jon Stokes|title=Inside the Machine: An Illustrated Introduction to Microprocessors and Computer Architecture|url=https://books.google.com/books?id=Q1zSIarI8xoC&pg=PA117|year=2007|publisher=No Starch Press|isbn=978-1-59327-104-6|page=117|accessdate=4 листопада 2018|archive-date=28 червня 2014|archive-url=https://web.archive.org/web/20140628205742/http://books.google.com/books?id=Q1zSIarI8xoC&pg=PA117}}</ref><ref name="Spaulding2009">{{cite book|author1=Robert Reese|author2=J. W. Bruce|author3=Bryan A. Jones|title=Microcontrollers: From Assembly Language to C Using the PIC24 Family|url=https://books.google.com/books?id=ndALAAAAQBAJ&pg=PA217|year=2009|publisher=Cengage Learning|isbn=1-58450-633-4|page=217|accessdate=4 листопада 2018|archive-date=28 червня 2014|archive-url=https://web.archive.org/web/20140628205802/http://books.google.com/books?id=ndALAAAAQBAJ&pg=PA217}}</ref>

Справжні комп'ютери оперують із кількома бітами одночасно, тому навіть реалізації двійкового НСД на асемблері мають конкурувати з апаратними схемами для цілочисельного ділення. На гіпотетичному комп'ютері [[MIX]], розширеному бітовими зсувами та перевірками на парність, [[Дональд Кнут|Кнут]] повідомляв про 20&nbsp;% перевагу двійкового алгоритму над звичайним алгоритмом Евкліда.

Для [[Довга арифметика|арифметики довільної точності]], ні двійковий алгоритм НСД, ні алгоритм Евкліда не є найшвидшими, оскільки обидва вони потребують квадратичного часу від кількості вхідних біт. Натомість, рекурсивні методи, що комбінують ідеї двійкового алгоритму НСД й [[Алгоритм Шьонхаге — Штрассена|алгоритму Шьонхаге — Штрассена]] для швидкого множення цілих чисел, дозволяють досягнути близького до лінійного часу роботи.<ref>{{citation
 | last1 = Stehle
 | first1 = Damien
 | last2 = Zimmermann
 | first2 = Paul
 | contribution = A binary recursive gcd algorithm
 | doi = 10.1007/978-3-540-24847-7_31
 | mr = 2138011
 | pages = 411–425
 | publisher = Springer, Berlin
 | series = Lecture Notes in Comput. Sci.
 | title = Algorithmic number theory
 | url = http://hal.archives-ouvertes.fr/docs/00/07/15/33/PDF/RR-5050.pdf
 | volume = 3076
 | year = 2004
 | accessdate = 4 листопада 2018
 | archive-date = 13 вересня 2014
 | archive-url = https://web.archive.org/web/20140913011216/http://hal.archives-ouvertes.fr/docs/00/07/15/33/PDF/RR-5050.pdf
 }}.</ref>

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

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

== Подальше читання ==
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7}}. Problem 31-1, pg.902.

== Зовнішні джерела ==
* [https://xlinux.nist.gov/dads/HTML/binaryGCD.html NIST Dictionary of Algorithms and Data Structures: binary GCD algorithm] {{Webarchive|url=https://web.archive.org/web/20181013023058/https://xlinux.nist.gov/dads/HTML/binaryGCD.html |date=13 жовтня 2018 }}
* [http://www.cut-the-knot.org/blue/binary.shtml Cut-the-Knot: Binary Euclid's Algorithm] {{Webarchive|url=https://web.archive.org/web/20181013023059/http://www.cut-the-knot.org/blue/binary.shtml |date=13 жовтня 2018 }} на cut-the-knot
* [http://wwwmaths.anu.edu.au/~brent/pub/pub037.html ''Analysis of the Binary Euclidean Algorithm''] {{Webarchive|url=https://web.archive.org/web/20120321101143/http://wwwmaths.anu.edu.au/~brent/pub/pub037.html |date=21 березня 2012 }} (1976), стаття Richard Brent, включає варіант з використанням зсувів вліво
* [https://web.archive.org/web/20110513012901/http://users.info.unicaen.fr/~brigitte/Publications/bin-gcd.ps «Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators»] (1998), стаття Brigitte Vallee.

{{Алгоритми теорії чисел}}
[[Категорія:Алгоритми теорії чисел]]
[[Категорія:Статті з прикладами коду мовою C++]]

Шаблони, використані на цій сторінці:

Шаблон:Citation (переглянути вихідний код) (частково захищено)
Шаблон:Cite book (переглянути вихідний код) (захищено)
Шаблон:Cite web (переглянути вихідний код) (захищено)
Шаблон:Column-width (переглянути вихідний код) (частково захищено)
Шаблон:Harvnb (переглянути вихідний код) (частково захищено)
Шаблон:Hlist/styles.css (переглянути вихідний код) (захищено)
Шаблон:ISBN (переглянути вихідний код) (частково захищено)
Шаблон:Iw (переглянути вихідний код) (захищено)
Шаблон:Main other (переглянути вихідний код) (захищено)
Шаблон:Navbox (переглянути вихідний код) (захищено)
Шаблон:Nobr (переглянути вихідний код) (захищено)
Шаблон:Reflist (переглянути вихідний код) (захищено)
Шаблон:Reflist/styles.css (переглянути вихідний код) (захищено)
Шаблон:Webarchive (переглянути вихідний код) (захищено)
Шаблон:Алгоритми теорії чисел (редагувати)
Шаблон:Не перекладено (переглянути вихідний код) (захищено)
Шаблон:Портал (переглянути вихідний код) (захищено)
Модуль:Arguments (переглянути вихідний код) (захищено)
Модуль:Check for unknown parameters (переглянути вихідний код) (захищено)
Модуль:Citation/CS1 (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/COinS (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Configuration (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Identifiers (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Utilities (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Whitelist (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/styles.css (переглянути вихідний код) (захищено)
Модуль:Footnotes (переглянути вихідний код) (частково захищено)
Модуль:Navbar (переглянути вихідний код) (захищено)
Модуль:Navbar/configuration (переглянути вихідний код) (захищено)
Модуль:Navbar/styles.css (переглянути вихідний код) (захищено)
Модуль:Navbox (переглянути вихідний код) (захищено)
Модуль:Navbox/configuration (переглянути вихідний код) (захищено)
Модуль:Navbox/styles.css (переглянути вихідний код) (захищено)
Модуль:Portal (переглянути вихідний код) (захищено)
Модуль:Portal/images/other (переглянути вихідний код) (захищено)
Модуль:TableTools (переглянути вихідний код) (захищено)
Модуль:Webarchive (переглянути вихідний код) (захищено)
Модуль:Не перекладено (переглянути вихідний код) (захищено)

Повернення до сторінки «Двійковий алгоритм обчислення найбільшого спільного дільника».

Отримано з https://uk.wikipedia.org/wiki/Двійковий_алгоритм_обчислення_найбільшого_спільного_дільника