Перейти к содержимому


Публикации АлексейДовгаль

1 публикаций создано АлексейДовгаль (учитываются публикации только с 29-марта 23)


#304 НОД и НОК

Отправлено от АлексейДовгаль в 07 августа 2013 - 12:44 in Рекурсия

Хочу добавить более быструю реализацию функции НОД.
Эту реализацию показывал Котов В.М. в Бригантине.

Собственно, время работы данного алгоритма - количество бит в наибольшем числе.

Реализация на С++ (Возможно не самая красивая, ну да не суть)
long NOD(long a, long B)/>
{
	if (a == B)/>
   	return a;
	if (a*b == 0)
   	return a+b;
	// Если мы уже нашли НОД, то выдаём его значение
	if ((a % 2 == 0) && (b % 2 == 0))
   	return 2*NOD(a/2,b/2); // Если оба числа кратны двум, то сокращаем их пополам и выдаём их НОД, домноженный на 2
	if (a % 2 == 0)
   	return NOD(a/2,B)/>;
	if (b % 2 == 0)
   	return NOD(a,b/2);
	// Если какое-то из двух чисел кратно двум, а другое - нет, то сокращаем его вдвое (ибо эта двойка роли не играет)
	long a1 = a;
	long b1 = b;
	if (a1 < b1)
   	swap(a1,b1);
	return NOD((a1-b1)/2,b1); // И самое интересное. Если оба числа нечётные, то мы уменьшаем одно из них (по Евклиду НОД этих чисел от этого не изменится) и сокращаем вдвое.
}


Таким вот образом на каждой итерации отсекается 1 бит.

Результаты вычислений на АСМР (обе реализации на C++):
Евклид:
  • 0,037
  • 0,016
  • 0,01
  • 0,009
  • 0,009
  • 0,012
  • 0,01
  • 0,009
  • 0,01
  • 0,01
Котов:
  • 0,027
  • 0,008
  • 0,008
  • 0,008
  • 0,008
  • 0,008
  • 0,008
  • 0,008
  • 0,01
  • 0,011