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

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

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

    Итоги

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

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

    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 39
    • –2
      Много букв, вся статья сводится к одному, проверка входных данных:
      public static int gcd(int a, int b) {
          if (a <= 0 || b <= 0) {
              throw new IllegalArgumentException();
          }
          ...
      }
      
      • +16
        Зачем кидать исключение при нормальных данных?
        • +11
          Они не нормальные. Я не знаю, почему в Википедии написано «целых чисел». В «Математическом энциклопедическом словаре (1988)» у меня значится «Наибольший общий делитель двух или нескольких натуральных чисел».
          • +2
            Но в википедии как минимум написано
            Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

            так что часть нападок ТС являются ошибочными.
            • +4
              Но вы же исправили в Википедии, да?
              • +2
                В Википедии всё верно написано. И преведён источник.

                Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

                Вероятно, для НОД(0, 0) разумно принять значение ∞ или бросать исключение, для остальных пар целых чисел он прекрасно находится.
                • 0
                  Ещё можно INT_MAX :) Всё равно пока аргумент int ничего больше просто быть не может. Но я бы бросил исключение либо вернул −1: ±∞ существует только для чисел с плавающей запятой, выпендрёж с INT_MAX вряд ли кому‐то нужен, а −1 gcd возвращать не должен ни при каких условиях. Т.е. специальное значение (здесь — −1, т.к. я последнее время много пишу на C, но это может быть и nan (привет языкам без целых чисел) или Nothing) для языков без исключений (или где их не принято использовать для математических функций) либо исключение.
                  • 0
                    Лучше кинуть исключение, т.к. результат будет использоваться потом. В случае NaN исключение наверняка вылезет в другом месте, а с -1 вообще может ничего и не быть.
                    • 0
                      Исключений может просто не быть: тогда и кинуть их не получится. NaN взят из lua, там исключения ловятся весьма заморочным способом с pcall, а math.log(-1) возвращает NaN.
                      • 0
                        Но когда они есть, лучше их и кидать, благо они для этого и созданы.
                        А log(-1) = NaN, так это в соответствии с IEEE 754 возвращает сопроцессор, lua здесь абсолютно не причем.
                        • 0
                          Не сказал бы: Python и Perl кидают исключение, lua тоже не обязан выдавать то, что выдаёт сопроцессор. Высокоуровневые языки на то и высокоуровневые, что абстрагируются от железа.
                          • 0
                            * То есть, он не был обязан выдавать это при создании. Теперь, если math.log начнёт выдавать исключение, комплексное число или что‐нибудь ещё, будет много недовольных, которые рассчитывают на старое поведение.
          • 0
            Лучше тогда вернуть gcd(Math.Abs(a), Math.Abs(b));
            • 0
              а нулевые входные значения?
              • 0
                Точно, тогда gcd(Math.Max(Math.Abs(a), Math.Abs(b)), Math.Min(Math.Abs(a), Math.Abs(b)))) — с таким изменением будут работать все реализации, кроме третьей, но я ни разу не видел человека, который писал третью
            • –2
              Если уж и кидать исключение, то только если a < 0 || b < 0, в случае с нулем все нормально отработает
            • +15
              Чувак, не парься. Garbage in, garbage out. :)
              • НЛО прилетело и опубликовало эту надпись здесь
              • +7
                Обычно задача начинается с «Дано два натуральных числа...»
                • 0
                  На западе часто 0 считается натуральным. Лучше использовать словосочетание positive integer
                  • +1
                    Я на западе. Где это тут 0 считается натуральным?
                    • +3
                      Peano axioms — 0 is a natural number.
                      Аскиомы Пеано — 1 является натуральным числом

                      В Agda, Coq и Idris натуральные тоже начинаются с 0.
                      • –8
                        Хех, а в геометрии Лобачевского параллельные линии пересекаются.

                        Но за Пеано спасибо! Отличное чтиво на ночь :)
                        • +1
                          Regrettably, there seems to be no general agreement about whether to include 0 in the set of natural numbers.

                          (с) Wolfram MathWorld
                          • +2
                            Ну это и не противоречит, ведь где как. Я просто уточнил, что в Agda, Coq, а также в Homotopy type theory таки с нуля, а это вроде как наиболее современное в программировании и математике.
                            • +1
                              А я уточнил, что «на западе» есть разные мнения по этому вопросу.
                        • +1
                          There is no universal agreement about whether to include zero in the set of natural numbers: some define the natural numbers to be the positive integers {1, 2, 3, ...}, while for others the term designates the non-negative integers {0, 1, 2, 3, ...}. The former definition is the traditional one, with the latter definition having first appeared in the 19th century.

                          Natural Numbers
                    • +4
                      > НОД существует для любых двух целых чисел.
                      НОД(0;0)?
                        • +6
                          0 делится на 42. И 0 делится на 42. Следовательно, 42 — общий делитель 0 и 0. Но 42 > 0, так что 0 не может быть наибольшим общим делителем 0 и 0.
                          • –3
                            Значит, НОД(0;0) = -42? :)
                            • НЛО прилетело и опубликовало эту надпись здесь
                          • 0
                            Вы ведь понимаете, что 0 не может быть каким-либо делителем, правда?
                        • 0
                          Хм. Что в таком случае тогда можно сказать про НОК?
                          • 0
                            Например, НОК(0,b)=НОК(a,0)=0, НОК(a,b)=НОК(abs(a),abs(b))*sign(a*b) — чтобы сохранить формулу НОК(a,b)*НОД(a,b)=a*b.
                            Число 0 в операции умножения играет роль бесконечности, так что не удивительно, что оно оказывается «наибольшим».
                          • +2
                            Есть очень хорошая лекция А. Степанова (автора C++ STL) про алгоритм Эвклида: video.yandex.ru/users/ya-events/view/129#

                            Так там он описывает, как к нему на одну из предыдущих лекций пришел Дональд Кнут и сказал в стиле «Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель.» На что Степанов ответил: «Зависит от определения». В лекции по ссылке подробно описано и объяснено.
                            • 0
                              int ans = gcd(Math.abs(a), Math.abs(b));

                              У этого решения могут быть проблемы, когда одно из чисел a или b равно int.MinValue (для него Abs не работает). Справится ли второе решение
                              (if(b==0) return Math.Abs(a)) для всех случаев, кроме (int.MinValue,0) и (int.MinValue, int.MinValue), я не проверял (подозрение вызывает (int.MinValue,-1) — будет ли там считаться без ошибки и исключений остаток от деления?)
                              Думаю, что безопаснее было бы сразу перевести аргументы в uint (или в ulong, если мы пишем gcd(long,long)), а в конце преобразовать ответ обратно. Как-нибудь так:
                              long gcd(long x,long y){
                                ulong a=x,b=y;
                                if(x<0) a=-a;
                                if(y<0) b=-b;
                                while(b!=0){
                                    ulong t=a%b;
                                    a=b;
                                    b=t;
                                }
                                return (long)a;
                              }
                              
                              • –1
                                А почему -5 не может быть делителем? ведь указанные числа на него делятся, и без остатка.
                                Может быть, такой ответ и неудобен в некоторых применениях, но чему собственно он противоречит?

                                Хм… разделить яблоко на -5 частей… а что, звучит!
                                • 0
                                  Читайте статью внимательно. Ответ на ваш вопрос дан в следующем же абзаце:
                                  Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель. А таковым является число 5. Ведь и первое, и второе число делятся без остатка на 5. Значит и первые две реализации не дают верный ответ.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.