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

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

Візуалізація використання двійкового алгоритму Евкліда для обчислення найбільшого спільного дільника (НСД) чисел 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. В будь-якому випадку результат рівний 2kv, де k — кількість спільних дільників 2 знайдених на кроці 2.

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

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

Реалізація

Рекурсивна реалізація на 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 % ефективніший (в термінах кількості бітових операцій) ніж алгоритм Евкліда.[6][7][8] Однак, хоч на практиці цей алгоритм дещо перевершує звичайний алгоритм Евкліда, його асимптотична складність така ж сама, а реалізація непомірно складніша, особливо враховуючи загальнодоступність інструкції цілочисельного ділення на всіх сучасних мікропроцесорах.[9][10]

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

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

Див. також

Посилання
  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. http://gmplib.org/manual/Binary-GCD.html
  4. Knuth, 1998, p. 646, answer to exercise 39 of section 4.5.2
  5. Handbook of Applied Cryptography. Процитовано 9 вересня 2017.
  6. 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. Архів оригіналу за 2 жовтня 2006.
  7. 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. proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.
  8. Notes on Programming by Alexander Stepanov
  9. Jon Stokes (2007). Inside the Machine: An Illustrated Introduction to Microprocessors and Computer Architecture. No Starch Press. с. 117. ISBN 978-1-59327-104-6.
  10. Robert Reese; J. W. Bruce; Bryan A. Jones (2009). Microcontrollers: From Assembly Language to C Using the PIC24 Family. Cengage Learning. с. 217. ISBN 1-58450-633-4.
  11. Stehle, Damien; Zimmermann, Paul (2004). A binary recursive gcd algorithm. Algorithmic number theory. Lecture Notes in Comput. Sci. 3076. Springer, Berlin. с. 411–425. MR 2138011. doi:10.1007/978-3-540-24847-7_31..

Подальше читання
  • 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.

Зовнішні джерела
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.