Алгоритмы нахождения наибольшего общего делителя (НОД) и их сравнительная характеристика

toInt ();int x = (-1) * inverseAModK * b;x = modK (x, k);if (G[x] == 1 && abs (a) + abs (b) < minLengthOfSumAB[x]){A[x] = a;minLengthOfSumAB[x] = abs (a) + abs (b);}}}// Eratosthenes’s sievefor (inti = 0; i <= k; i++){P[i] = true;}P[0] = P[1] = false;for (inti = 2; i * i <= k; i++){if (P[i]){for (int j = i * i; j <= k; j += i) P[j] = false;}}for (int d = boundary + 1; d <= k; d++){if (P[d] && k % d ≠ 0) P[d] = false;}//Second phase — trial divisionnumber g = 1;for (inti = 2; i <= k; i++){while (P[i] && u % i == 0 && v % i == 0){u /= i;v /= i;g *= i;}}// Third phase — Main loopwhile (u ≠ 0 && v ≠ 0){number u1 = u % k, v1 = v % k;int indexU1 = u1. toInt (), indexV1 = v1. toInt ();if (G[indexU1] > 1){u /= G[indexU1]; }else{if (G[indexV1] > 1){v /= G[indexV1]; }else{number x = (u1 * I[indexV1]) % k;number a = A[x.toInt ()]; number b = modK ((-a * x), k);maxNumber (u, v) = abs (a * u + b * v) / k;}}}number t = u + v;// Fourth phase — Trial divisionfor (int d = 2; d <= k; d++){while (P[d] && t % d == 0) t /= d;}g *= t;return g;}//Алгоритм Лемера поиска НОДnumbergcd_algorithms:lemehr_gcd (constnumber& a, constnumber& b, number& p){//Промежуточные переменныеlong h;number a0, a1;number u0, v0;number u1, v1;number q0, q1;number r, R;number T;number q;numberpow_base = 2;number W = 1;number W1 = 1;number temp;numberA, B;//ИсходныезначенияA = a;B = b;if (A > B){temp = A;A = B;B = temp;}//Вычислениестепениоснованияfor (inti = 0; i < p. toInt (); i++)W = W*pow_base;//Пока выполняется условиеwhile (B >= W){//Вычисляем битовую длину числа Bh = (int)(log ((double)B.toLong ()) /log (2.))+1;//Рассчитываем порядок hh = h — p. toUnsignedLong () + 1;//Считаемстепень 2^hfor (inti = 0; i < h; i++)W1 = W1*pow_base;//Вычисляем начальные значенияa0 = A / W1;a1 = B / W1;u0 = 1;u1 = 0;v0 = 0;v1 = 1;while (((a1 + u1) ≠ 0) && ((a1 + v1) ≠ 0)){q0 = (a0 + u0) / (a1 + u1);q1 = (a0 + v0) / (a1 + v1);if (q0 ≠ q1) break;r = a0 — q0*a1; a0 = a1; a1 = r;r = u0 — q0*u1; u0 = u1; u1 = r;r = v0 — q0*v1; v0 = v1; v1 = r;}if (v0 == 0){q = A / B;R = A — q*B;A = B;B = R;}else{R = u0*A + v0*B;T = u1*A + v1*B;A = R;B = T;}if (B == 0) return A;}A = classicEuclidByDiv (A, B);return A;}numbergcd_algorithms:jw_gcd (constnumber& A, constnumber& B, number& k){number r;number n1, n2;number d1, d2;numbersqrt_k = (int)sqrt ((double)k.toLong ());number div_;number res1, res2, res;number pow=1;for (inti = 0; i < k. toLong (); i++)pow *= 2;k = pow;r = (A / B) % k;n1 = k;d1 = 0;n2 = r;d2 = 1;res1 = A;res2 = B;while (n2 >= sqrt_k){div_ = n1 / n2;//f1=f1-[n1/n2]*f2n1 = n1 — div_*n2;d1 = d1 — div_*d2;//swap (f1,f2)number temp = n1;n1 = n2;n2 = temp;temp = d1;d1 = d2;d2 = temp;res1 = abs (n1*B — d1*A) / k;res2 = abs (n2*B — d2*A) / k;res = classicEuclidByDiv (max (res1, res2), min (res1, res2));} res = classicEuclidByDiv (max (res1, res2), min (res1,res2));return res;}Main.cpp#include" GCDAlgorithms. h" #include<iostream>#include<time.h>#include<string>#include" windows. h" #include" BigInteger/BigIntegerUtils.hh" #defineBILLION 1E9usingnamespacestd;intmain (){long start, stop;numbera, b;number k₁, k₂, k₃;long k1, k2,k3;string a1, b1;SetConsoleCP (1251);SetConsoleOutputCP (1251);cout << «Введитепервоечислоa» << endl;cin >> a1;cout<< «Введите второе число b» << endl;cin >> b1;a = stringToBigInteger (a1);b = stringToBigInteger (b1);cout << «Задайтепараметр k>=2 алгоритма k-арногоалгоритмапоиска.

НОД" << endl;cin >> k1;k₁ = k1;cout << «Задайтепараметр k алгоритма.

Лемера k поиска.

НОД" << endl;cout<< «Для k должно выполняться k>=4, взаимно простое с a и b» << endl;cin >> k2;k₂ = k2;cout<< «Задайте параметр k алгоритма Джабелиана-Вебера поиска НОД» << endl;cout<< «Для k должно выполняться k>=4, взаимно простое с a и b» << endl;cin >> k3;k₃ = k3;//Задаем настройки подсчета времениsrand (time (0));//Рекурсивный алгоритм Евклида с использованием разностейnumberres;start = clock ();cout<< «Рекурсивный алгоритм Евклида с использованием разностей» << endl;res= gcd_algorithms:classicEuclidBySubtrRecursive (a, b);cout<<" Значение.

НОД = «<< res. toLong () << endl;stop = clock ();cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;//Рекурсивный алгоритм Евклида с использованием деленияstart = clock ();cout<< «Рекурсивный алгоритм Евклида с использованием деления» << endl;res = gcd_algorithms:classicEuclidByDivRecursive (a, b);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;//Алгоритм Евклида с использованием разностейstart = clock ();cout<< «Алгоритм Евклида с использованием разностей» << endl;res= gcd_algorithms:classicEuclidBySubtr (a, b);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;//Алгоритм Евклида с использованием деленияstart = clock ();cout<< «Алгоритм Евклида с использованием деления» << endl;res = gcd_algorithms:classicEuclidByDiv (a, b);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;//Рекурсивный бинарный алгоритм Евклидаstart = clock ();cout<< «Рекурсивный бинарный алгоритм Евклида» << endl;res = gcd_algorithms:binaryEuclidRecursive (a, b);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;//Бинарный алгоритм Евклидаstart = clock ();cout<< «Бинарный алгоритм Евклида» << endl;res = gcd_algorithms:binaryEuclid (a, b);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;//Рекурсивный расширенный алгоритм Евклидаstart = clock ();cout<< «Рекурсивный расширенный алгоритм Евклида» << endl;number x, y;res = gcd_algorithms:extendedEuclidRecursive (a, b, x, y);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;cout << «Коэффициентыx, yприкоторых a*x+b*y=НОД (a, b)» << endl;cout << «x=» << x. toLong () << «, y=» << y. toLong () << endl;//Расширенный алгоритм Евклидаstart = clock ();cout<< «Расширенный алгоритм Евклида» << endl;res = gcd_algorithms:extendedEuclid (a, b, x, y);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;cout << «Коэффициентыx, yприкоторых a*x+b*y=НОД (a, b)» << endl;cout << «x=» << x. toLong () << «, y=» << y. toLong () << endl;//k-арный алгоритм поиска НОДstart = clock ();cout<< «k-арный алгоритм поиска НОД» << endl;res = gcd_algorithms:kAryEuclid (a, b, k₁.toInt ());stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;//Алгоритм Лемера поиска НОДstart = clock ();cout<< «Алгоритм Лемера поиска НОД» << endl;res = gcd_algorithms:lemehr_gcd (a, b, k₂);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;//Алгоритм.

Джабелиана-Вебераstart = clock ();cout << «Алгоритм.

Джабелиана-Вебера" << endl;res = gcd_algorithms:jw_gcd (a, b, k₃);stop = clock ();cout << «Значение.

НОД = «<< res. toLong () << endl;cout << «Времявыполненияалгоритма, c «<< (float)(stop — start) / 1000 << endl;system («pause»);return 0;}.