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

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

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

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

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

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

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

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

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

Итоги

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

Используемая литература, источники, реализации:

• Binary GCD algorithm — Wikipedia
• Euclidean algorithm — Wikipedia
• Алгоритм Евклида — e-maxx
• Binary GCD — Dictionary of Algorithms and Data Structures
• Кормен — Алгоритмы — построение и анализ