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

Введение 2
1. Описание алгоритмов нахождения наибольшего общего делителя 3
2. Выполнение вычислительного эксперимента 10
Заключение 14
Литература 15
Приложение 16

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_1,k_2,k_3;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_1 = k1;cout << "Задайтепараметр k алгоритмаЛемера k поискаНОД" << endl;cout<< "Для k должно выполняться k>=4, взаимно простое с a и b" << endl;cin >> k2;k_2 = k2;cout<< "Задайте параметр k алгоритма Джабелиана-Вебера поиска НОД" << endl;cout<< "Для k должно выполняться k>=4, взаимно простое с a и b" << endl;cin >> k3;k_3 = 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_1.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_2);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_3);stop = clock();cout << "ЗначениеНОД = " << res.toLong() << endl;cout << "Времявыполненияалгоритма,c " << (float)(stop - start) / 1000 << endl;system("pause");return 0;}