Эту реализацию показывал Котов В.М. в Бригантине.
Собственно, время работы данного алгоритма - количество бит в наибольшем числе.
Реализация на С++ (Возможно не самая красивая, ну да не суть)
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