www.wikidata.uk-ua.nina.az

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

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

Двійковий алгоритм обчислення НСД, також відомий як алгоритм Стайна або двійковий алгоритм Евкліда — алгоритм, що обчислює найбільший спільний дільник двох невід'ємних цілих чисел. Двійковий алгоритм Евкліда використовує простіші арифметичні операції, ніж звичайний алгоритм Евкліда: він замінює ділення бітовим зсувом, порівняннями та відніманням. Хоча вперше його опублікував ізраїльський фізик і програміст Джозеф Стайн 1967 року, алгоритм міг бути відомим ще в першому столітті в Китаї.

Візуалізація використання двійкового алгоритму Евкліда для обчислення найбільшого спільного дільника (НСД) чисел 36 і 24. Отже, НСД рівний 22 × 3 = 12.

Алгоритм ред.

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

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

У найгіршому випадку алгоритм потребує O(n2) часу, де n — кількість біт у більшому з двох чисел. Хоча кожен крок зменшує хоча б одне число принаймні вдвічі, для дуже великих чисел віднімання та зсув потребують лінійного часу (втім, на практиці вони доволі швидкі).

Розширений двійковий алгоритм обчислення НСД, аналогічний до розширеного алгоритму Евкліда, описав Дональд Кнут у другому томі «Мистецтва програмування».

Реалізація ред.

Рекурсивна реалізація на C ред.

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

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); }

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

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

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; }

Ефективність ред.

Доведено, що в теорії, двійковий алгоритм обчислення НСД в середньому на 60 % ефективніший, ніж алгоритм Евкліда (у термінах кількості бітових операцій). Однак, хоч на практиці цей алгоритм дещо перевершує звичайний алгоритм Евкліда, його асимптотична складність така ж сама, а реалізація непомірно складніша, особливо враховуючи загальнодоступність інструкції цілочисельного ділення на всіх сучасних мікропроцесорах.

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

Для арифметики довільної точності, ні двійковий алгоритм НСД, ні алгоритм Евкліда не є найшвидшими, оскільки обидва вони потребують квадратичного часу від кількості вхідних біт. Натомість, рекурсивні методи, що комбінують ідеї двійкового алгоритму НСД й алгоритму Шьонхаге — Штрассена для швидкого множення цілих чисел, дозволяють досягнути близького до лінійного часу роботи.

Див. також ред.

Посилання ред.

  1. Stein, J. (1967). Computational problems associated with Racah algebra. Journal of Computational Physics 1 (3): 397–405. ISSN 0021-9991. doi:10.1016/0021-9991(67)90047-2. 
  2. Knuth, Donald (1998). Seminumerical Algorithms. The Art of Computer Programming 2 (вид. 3rd). Addison-Wesley. ISBN 0-201-89684-2. 
  3. . Архів оригіналу за 5 листопада 2018. Процитовано 4 листопада 2018. 
  4. (Knuth, 1998, с. 646), answer to exercise 39 of section 4.5.2
  5. . Архів оригіналу за 2 лютого 2019. Процитовано 9 вересня 2017. 
  6. Akhavi, Ali; Vallee, Brigitte (2000). . Proceedings ICALP'00, Lecture Notes Computer Science 1853: 373–387. CiteSeerX: 10.1.1.42.7616. Архів оригіналу за 2 жовтня 2006. 
  7. Brent, Richard P. (2000). . Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in honour of Professor Sir Antony Hoare (Palgrave, NY): 41–53. Архів оригіналу за 15 квітня 2012. Процитовано 4 листопада 2018.  proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.
  8. Notes on Programming [ 25 листопада 2018 у Wayback Machine.] by Alexander Stepanov
  9. Jon Stokes (2007). . No Starch Press. с. 117. ISBN 978-1-59327-104-6. Архів оригіналу за 28 червня 2014. Процитовано 4 листопада 2018. 
  10. Robert Reese; J. W. Bruce; Bryan A. Jones (2009). . Cengage Learning. с. 217. ISBN 1-58450-633-4. Архів оригіналу за 28 червня 2014. Процитовано 4 листопада 2018. 
  11. Stehle, Damien; Zimmermann, Paul (2004). . Algorithmic number theory. Lecture Notes in Comput. Sci. 3076. Springer, Berlin. с. 411–425. MR 2138011. doi:10.1007/978-3-540-24847-7_31. Архів оригіналу за 13 вересня 2014. Процитовано 4 листопада 2018. .

Подальше читання ред.

  • 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.

Зовнішні джерела ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Dvijkovij algoritm obchislennya NSD takozh vidomij yak algoritm Stajna abo dvijkovij algoritm Evklida algoritm sho obchislyuye najbilshij spilnij dilnik dvoh nevid yemnih cilih chisel Dvijkovij algoritm Evklida vikoristovuye prostishi arifmetichni operaciyi nizh zvichajnij algoritm Evklida vin zaminyuye dilennya bitovim zsuvom porivnyannyami ta vidnimannyam Hocha vpershe jogo opublikuvav izrayilskij fizik i programist Dzhozef Stajn 1967 roku 1 algoritm mig buti vidomim she v pershomu stolitti v Kitayi 2 Vizualizaciya vikoristannya dvijkovogo algoritmu Evklida dlya obchislennya najbilshogo spilnogo dilnika NSD chisel 36 i 24 Otzhe NSD rivnij 22 3 12 Zmist 1 Algoritm 2 Realizaciya 2 1 Rekursivna realizaciya na C 2 2 Iterativna realizaciya na C 3 Efektivnist 4 Div takozh 5 Posilannya 6 Podalshe chitannya 7 Zovnishni dzherelaAlgoritm red Algoritm obchislyuye NSD zastosovuyuchi taki totozhnosti NSD 0 v v tomu sho nul dilitsya na vsi chisla a v najbilshij dilnik chisla v Analogichno NSD u 0 u NSD 0 0 zazvichaj neviznacheno ale zruchno vvazhati sho NSD 0 0 0 Yaksho u i v parni to NSD u v 2 NSD u 2 v 2 tomu sho 2 spilnij dilnik Yaksho u parne a v neparne to NSD u v NSD u 2 v tomu sho 2 ne spilnij dilnik Analogichno yaksho u neparne a v parne to NSD u v NSD u v 2 Yaksho u i v neparni ta u gt v to NSD u v NSD u v 2 v yaksho zh u lt v to NSD u v NSD u v u 2 Ce kombinaciya odnogo kroku zvichajnogo algoritmu Evklida de na kozhnomu kroci zastosovuyetsya vidnimannya iz podalshim zastosuvannyam kroku 3 Riznicya dvoh neparnih chisel zavzhdi bude parnoyu tomu dilennya na dva daye cile chislo Kroki 2 4 povtoryuyut poki u ne stane rivnim v abo poki u ne stane 0 na odin krok bilshe U bud yakomu vipadku rezultat dorivnyuvatime 2k v de k kilkist spilnih dilnikiv 2 znajdenih na kroci 2 U najgirshomu vipadku algoritm potrebuye O n2 3 chasu de n kilkist bit u bilshomu z dvoh chisel Hocha kozhen krok zmenshuye hocha b odne chislo prinajmni vdvichi dlya duzhe velikih chisel vidnimannya ta zsuv potrebuyut linijnogo chasu vtim na praktici voni dovoli shvidki Rozshirenij dvijkovij algoritm obchislennya NSD analogichnij do rozshirenogo algoritmu Evklida opisav Donald Knut u drugomu tomi Mistectva programuvannya 4 5 Realizaciya red Rekursivna realizaciya na C red Realizaciya shozha na opis algoritmu zverhu Usi rekursivni vikliki krim odnogo ye hvostovoyu rekursiyeyu unsigned int gcd unsigned int u unsigned int v prosti vipadki zavershennya if u v return u if u 0 return v if v 0 return u obchislennya kilkosti dvijok if u amp 1 u parne if v amp 1 v neparne return gcd u gt gt 1 v else v parne return gcd u gt gt 1 v gt gt 1 lt lt 1 if v amp 1 u neparne v parne return gcd u v gt gt 1 zmenshennya bilshogo argumentu if u gt v return gcd u v gt gt 1 v return gcd v u gt gt 1 u Iterativna realizaciya na C red Iterativna realizaciya spochatku pozbuvayetsya spilnogo dilnika 2 zastosovuyuchi rivnist 2 potim obchislyuye NSD zastosovuyuchi rivnosti 3 i 4 unsigned int gcd unsigned int u unsigned int v int shift NSD 0 v v NSD u 0 u NSD 0 0 0 if u 0 return v if v 0 return u Nehaj shift lg K de K najbilsha stepin dvijki sho dilit u i v for shift 0 u v amp 1 0 shift u gt gt 1 v gt gt 1 while u amp 1 0 u gt gt 1 Pochinayuchi zvidsi u zavzhdi neparne do pozbudemos vsih dilnikiv 2 v v voni ne spilni zauvazhennya v ne 0 tozh cikl zavershitsya while v amp 1 0 Loop X v gt gt 1 Teper u i v neparni Yaksho potribno obminyayemo yih shob u lt v todi vstanovimo v v u parne chislo Dlya dovgih chisel obmin vsogo peremishennya vkazivnikiv i vidnimannya mozhna zrobiti na misci if u gt v unsigned int t v v u u t Obmin u i v v v u Tut v gt u while v 0 Vidnovlyuyemo spilni dilniki 2 return u lt lt shift Efektivnist red Dovedeno sho v teoriyi dvijkovij algoritm obchislennya NSD v serednomu na 60 efektivnishij nizh algoritm Evklida u terminah kilkosti bitovih operacij 6 7 8 Odnak hoch na praktici cej algoritm desho perevershuye zvichajnij algoritm Evklida jogo asimptotichna skladnist taka zh sama a realizaciya nepomirno skladnisha osoblivo vrahovuyuchi zagalnodostupnist instrukciyi cilochiselnogo dilennya na vsih suchasnih mikroprocesorah 9 10 Spravzhni komp yuteri operuyut iz kilkoma bitami odnochasno tomu navit realizaciyi dvijkovogo NSD na asembleri mayut konkuruvati z aparatnimi shemami dlya cilochiselnogo dilennya Na gipotetichnomu komp yuteri MIX rozshirenomu bitovimi zsuvami ta perevirkami na parnist Knut povidomlyav pro 20 perevagu dvijkovogo algoritmu nad zvichajnim algoritmom Evklida Dlya arifmetiki dovilnoyi tochnosti ni dvijkovij algoritm NSD ni algoritm Evklida ne ye najshvidshimi oskilki obidva voni potrebuyut kvadratichnogo chasu vid kilkosti vhidnih bit Natomist rekursivni metodi sho kombinuyut ideyi dvijkovogo algoritmu NSD j algoritmu Shonhage Shtrassena dlya shvidkogo mnozhennya cilih chisel dozvolyayut dosyagnuti blizkogo do linijnogo chasu roboti 11 Div takozh red nbsp Portal Programuvannya Algoritm Evklida Rozshirenij algoritm Evklida Najmenshe spilne kratnePosilannya red Stein J 1967 Computational problems associated with Racah algebra Journal of Computational Physics 1 3 397 405 ISSN 0021 9991 doi 10 1016 0021 9991 67 90047 2 Knuth Donald 1998 Seminumerical Algorithms The Art of Computer Programming 2 vid 3rd Addison Wesley ISBN 0 201 89684 2 Arhivovana kopiya Arhiv originalu za 5 listopada 2018 Procitovano 4 listopada 2018 Knuth 1998 s 646 answer to exercise 39 of section 4 5 2 Handbook of Applied Cryptography Arhiv originalu za 2 lyutogo 2019 Procitovano 9 veresnya 2017 Akhavi Ali Vallee Brigitte 2000 AverageBit Complexity of Euclidean Algorithms Proceedings ICALP 00 Lecture Notes Computer Science 1853 373 387 CiteSeerX 10 1 1 42 7616 Arhiv originalu za 2 zhovtnya 2006 Brent Richard P 2000 Twenty years analysis of the Binary Euclidean Algorithm Millenial Perspectives in Computer Science Proceedings of the 1999 Oxford Microsoft Symposium in honour of Professor Sir Antony Hoare Palgrave NY 41 53 Arhiv originalu za 15 kvitnya 2012 Procitovano 4 listopada 2018 proceedings edited by J Davies A W Roscoe and J Woodcock Notes on Programming Arhivovano 25 listopada 2018 u Wayback Machine by Alexander Stepanov Jon Stokes 2007 Inside the Machine An Illustrated Introduction to Microprocessors and Computer Architecture No Starch Press s 117 ISBN 978 1 59327 104 6 Arhiv originalu za 28 chervnya 2014 Procitovano 4 listopada 2018 Robert Reese J W Bruce Bryan A Jones 2009 Microcontrollers From Assembly Language to C Using the PIC24 Family Cengage Learning s 217 ISBN 1 58450 633 4 Arhiv originalu za 28 chervnya 2014 Procitovano 4 listopada 2018 Stehle Damien Zimmermann Paul 2004 A binary recursive gcd algorithm Algorithmic number theory Lecture Notes in Comput Sci 3076 Springer Berlin s 411 425 MR 2138011 doi 10 1007 978 3 540 24847 7 31 Arhiv originalu za 13 veresnya 2014 Procitovano 4 listopada 2018 Podalshe chitannya red 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 Zovnishni dzherela red NIST Dictionary of Algorithms and Data Structures binary GCD algorithm Arhivovano 13 zhovtnya 2018 u Wayback Machine Cut the Knot Binary Euclid s Algorithm Arhivovano 13 zhovtnya 2018 u Wayback Machine na cut the knot Analysis of the Binary Euclidean Algorithm Arhivovano 21 bereznya 2012 u Wayback Machine 1976 stattya Richard Brent vklyuchaye variant z vikoristannyam zsuviv vlivo Dynamics of the Binary Euclidean Algorithm Functional Analysis and Operators 1998 stattya Brigitte Vallee Otrimano z https uk wikipedia org w index php title Dvijkovij algoritm obchislennya najbilshogo spilnogo dilnika amp oldid 39621682