0,0
рейтинг
7 декабря 2013 в 13:27

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

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

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

Итоги

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

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

Алексей Саскевич @asaskevich
карма
9,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (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)?
    • +2
      • +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. Значит и первые две реализации не дают верный ответ.

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