Главная

Вычисление НОД — ошибка, которой не замечают

2013-12-07 в 9:27, admin, рубрики: GCD, Алгоритмы, Совершенный код, метки: GCD, nod

Что такое НОД, все знают еще со школы. Для тех, кто подзабыл, напомню: НОД — наибольший общий делитель, делящий два целых числа без остатка. Например, НОД чисел 100 и 45 равен 5, а НОД чисел 17 и 7 равен 1. Существует несколько различных алгоритмов поиска этого числа. Однако, несмотря на то, что это достаточно простые алгоритмы, часто совершают одну маленькую, но очень существенную ошибку.

Алгоритмы вычисления НОД

Я рассмотрю 5 алгоритмов вычисления НОД:

1. Рекурсия и остатки

public static int gcd_1(int a, int b) {
	if (b == 0)
		return a;
	return gcd_1(b, a % b);
}

2. Те же остатки, но без рекурсии

public static int gcd_2(int a, int b) {
	int t;
	while (b != 0) {
		t = b;
		b = a % b;
		a = t;
	}
	return a;
}

3. Классический алгоритм Евклида

public static int gcd_3(int a, int b) {
	while (a != b) {
		if (a > b) {
			a = a - b;
		} else {
			b = b - a;
		}
	}
	return a;
}

4. Бинарный алгоритм поиска НОД

public static int gcd_4(int a, int b) {
	if (a == b)
		return a;
	if (a == 0)
		return b;
	if (b == 0)
			return a;
	if ((~a & 1) != 0) {
		if ((b & 1) != 0)
			return gcd_4(a >> 1, b);
		else
			return gcd_4(a >> 1, b >> 1) << 1;
	}
	if ((~b & 1) != 0)
		return gcd_4(a, b >> 1);
	if (a > b)
		return gcd_4((a - b) >> 1, b);
	return gcd_4((b - a) >> 1, a);
}

5. Бинарный алгоритм на основе битовой арифметики

public static int gcd_5(int a, int b) {
	int shift;
	if (a == 0)
		return b;
	if (b == 0)
		return a;
	for (shift = 0; ((a | b) & 1) == 0; ++shift) {
		a >>= 1;
		b >>= 1;
	}
	while ((a & 1) == 0)
		a >>= 1;
		do {
		while ((b & 1) == 0)
			b >>= 1;
		if (a > b) {
			int t = b;
			b = a;
			a = t;
		}
		b = b - a;
	} while (b != 0);
	return a << shift;
}

Естественно, чаще всего пишут первый вариант — он легко запоминается, быстро пишется и достаточно быстро работает.

Претесты

Реализации корректно работают на таких тестах:

gcd(1, 10) = 1
gcd(5, 10) = 5
gcd(24, 24) = 24
gcd(0, 0) = 0
gcd(5,10) = 5

Естественно, они будут работать и на подобных тестах, где в качестве аргументов выступают целые неотрицательные числа. Но что, если…

Первые тесты с подвохом

… если заменить одно из чисел нулем? Например так:

gcd(5, 0) = 5
gcd(0, 15) = 15

Классический алгоритм Евклида (№3) уже попадает в бесконечный цикл.

Копаем глубже

Согласно определению, НОД может быть определен для любых двух целых чисел. Так почему бы не попробовать тесты, где одно из чисел — отрицательное:

gcd(-5,10) = ?

Все становится еще интереснее. Первые две реализации выдают в качестве ответа -5. Третий алгоритм снова попадает в бесконечный цикл. Вместе с ним в бесконечном цикле оказывается пятый алгоритм. Четвертый падает по StackOverFlow — скорее всего тоже попадает в бесконечный цикл.
Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель. А таковым является число 5. Ведь и первое, и второе число делятся без остатка на 5. Значит и первые две реализации не дают верный ответ.

Почему решения №№3-5 попадают в бесконечный цикл?

Алгоритм Евклида попадает в цикл из-за бесконечного увеличения аргументов, если один из них отрицательный. Действительно, если посмотреть на эти строки, то можно заметить, что при отрицательном a (или b) операция вычитания заменяется сложением.

if (a > b) {
	a = a - b;
} else {
	b = b - a;
}

Аналогичное происходит в четвертом и пятом алгоритме:

if (a > b)
	return gcd_4((a - b) >> 1, b);
return gcd_4((b - a) >> 1, a);

if (a > b) {
	int t = b;
	b = a;
	a = t;
}
b = b - a;

В ситуации, когда a или b равны 0, то происходит бесконечное вычитание нуля, которое никаким образом не меняет значения аргументов.

Так что же не так?

Все эти алгоритмы корректны для входных данных, когда оба числа a и b — целые неотрицательные числа. Но вспомним еще раз — НОД существует для любых двух целых чисел.

Что же делать?

В качестве аргументов в функцию можно передавать абсолютное значение чисел, тогда ответ будет корректен:

int ans = gcd(Math.abs(a), Math.abs(b));

Второй способ решения задачи — возвращать абсолютное значение ответа:

public static int gcd(int a, int b) {
	if (b == 0)
		return Math.abs(a);
	return gcd(b, a % b);
}

Второй вариант гораздо предпочтительнее: будет производиться меньше лишних вычислений, чем в первом варианте.

Итоги

Мы рассмотрели пять различных вариантов вычисления наибольшего общего делителя. Для каждого из них мы указали входные данные, на которых ответ существует, но решение «падает», а также способ решения проблемы.
Такие небольшие ошибки чаще всего допускаются по причине того, что не замечают «скользкие» места решения какой-то задачи. Часть из них отлавливается в процессе тестирования, а часть остается незамеченной.
В ситуации с вычислением НОД почти все реализации приведены с ошибкой. В Сети я нашел лишь парочку корректно работающих решений, остальные идентичны тем, что приведены в начале поста.