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

Что такое НОД, все знают еще со школы. Для тех, кто подзабыл, напомню: НОД — наибольший общий делитель, делящий два целых числа без остатка. Например, НОД чисел 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);
}

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

Итоги

Мы рассмотрели пять различных вариантов вычисления наибольшего общего делителя. Для каждого из них мы указали входные данные, на которых ответ существует, но решение «падает», а также способ решения проблемы.

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

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

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

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.