|
Двійковий алгоритм обчислення найбільшого спільного дільника Двійковий алгоритм обчислення НСД, також відомий як алгоритм Стайна або двійковий алгоритм Евкліда — алгоритм, що обчислює найбільший спільний дільник двох невід'ємних цілих чисел. Двійковий алгоритм Евкліда використовує простіші арифметичні операції, ніж звичайний алгоритм Евкліда: він замінює ділення бітовим зсувом, порівняннями та відніманням. Хоча вперше його опублікував ізраїльський фізик і програміст Джозеф Стайн 1967 року[1], алгоритм міг бути відомим ще в першому столітті в Китаї[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] Справжні комп'ютери оперують із кількома бітами одночасно, тому навіть реалізації двійкового НСД на асемблері мають конкурувати з апаратними схемами для цілочисельного ділення. На гіпотетичному комп'ютері MIX, розширеному бітовими зсувами та перевірками на парність, Кнут повідомляв про 20 % перевагу двійкового алгоритму над звичайним алгоритмом Евкліда. Для арифметики довільної точності, ні двійковий алгоритм НСД, ні алгоритм Евкліда не є найшвидшими, оскільки обидва вони потребують квадратичного часу від кількості вхідних біт. Натомість, рекурсивні методи, що комбінують ідеї двійкового алгоритму НСД й алгоритму Шьонхаге — Штрассена для швидкого множення цілих чисел, дозволяють досягнути близького до лінійного часу роботи.[11] Див. такожПосилання
Подальше читання
Зовнішні джерела
|
