Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями

→‎Реализации: Усовершенствование реализации на C
(→‎Реализации: Усовершенствование реализации на C)
 
==[[w:C (язык программирования)|С]]==
typedef unsigned int IntTypeInteger; /* Вместо unsigned int можно подставить любой другой целочисленный тип */
Без рекурсии:
<source lang="c">
typedef unsigned int IntType; /* Вместо unsigned int можно подставить любой другой целочисленный тип */
 
IntTypeInteger gcdGCD (IntTypeInteger a, IntTypeInteger b) {
int Integer shift;
 
/* НОД(0, x) = x */
if (!a == 0 || b == 0)
return a | b;
/* НОД(x, 0) = x */
if (!b)
return a;
 
/* Вычисление shift = lg K, где K — наибольшая степень 2, на которую делятся без остатка a и b. */
for (shift = 0; !((a | b) & 1) == 0; ++shift) {
a >>= 1;
b >>= 1;
}
}
 
while (!(a & 1) == 0)
a >>= 1;
 
/* Начиная отсюда a всегда нечётно. */
do {
while (!(b & 1) == 0) /* Цикл по X */
b >>= 1;
 
/* Теперь a и b нечётны, поэтому их разность (diff) чётна.
Вычисление a = min(a, b), b = (a - b) / 2. */
if (a < b) {
b -= a;
} else {
a -= IntType diff(b = a - b);
b >>= 1;
a = b;
} while (b != 0);
b = diff;
}
b >>= 1;
} while (b != 0);
 
return a << shift;
}
</source>
 
74

правки