Реализация быстрых алгоритмов (на деле окажется, что они не быстрые) и так же реализованы и комбинированные алгоритмы как отдельная функция
- БПФ
- Карацуба
- Виноград
Ctrl+F и вводим нужный алгоритм
БПФ #define _USE_MATH_DEFINES #include <iostream> #include <vector> #include <complex> #include <cmath> #include <time.h> using namespace std; vector <complex<double>> BPF(vector<double> P) { int n = P.size(); //Степень многочлена +1 на входе if (n == 1) return vector <complex<double>>(1,P[0]); // Если многочлен нулевой степени, то очевидно его ДПФ - сам свободный член //Комплексные корни из 1 vector < complex<double>> Roots_1; for (int i = 0; i < n; i++) { complex<double> Temp(cos(2 * M_PI * i / n), sin(2 * M_PI * i / n)); Roots_1.push_back(Temp); } //Разбиваем на два многочлена vector <double> A, B; for (int i = 0; i < n / 2; i++) { A.push_back(P[2 * i]); B.push_back(P[2 * i + 1]); } //Рекурсивно считаем меньшие многочлены vector <complex<double>> A_cof = BPF(A); vector <complex<double>> B_cof = BPF(B); //Конечный результат vector <complex<double>> res; for (int i = 0; i < n; i++) res.push_back(A_cof[i % (n / 2)] + Roots_1[i] * B_cof[i % (n / 2)]); return res; } vector <complex<double>> DPF(vector<double> P) { int n = P.size(); if (n == 1) return vector <complex<double>>(1, P[0]); vector < complex<double>> Roots_1; for (int i = 0; i < n; i++) { complex<double> Temp(cos(2 * M_PI * i / n), sin(2 * M_PI * i / n)); Roots_1.push_back(Temp); } vector <complex<double>> res; for (int i = 0; i < n; i++) { complex<double> Temp; for (int j = 0; j < n; j++) { Temp += P[j] * pow(Roots_1[i], j); } res.push_back(Temp); } return res; } vector <complex<double>> BPF_Comb(vector<double> P) { int n = P.size(); if (n == 1) return vector <complex<double>>(1, P[0]); vector < complex<double>> Roots_1; for (int i = 0; i < n; i++) { complex<double> Temp(cos(2 * M_PI * i / n), sin(2 * M_PI * i / n)); Roots_1.push_back(Temp); } vector <double> A, B; for (int i = 0; i < n / 2; i++) { A.push_back(P[2 * i]); B.push_back(P[2 * i + 1]); } if (n > 32) { vector <complex<double>> A_cof = BPF(A); vector <complex<double>> B_cof = BPF(B); vector <complex<double>> res; for (int i = 0; i < n; i++) res.push_back(A_cof[i % (n / 2)] + Roots_1[i] * B_cof[i % (n / 2)]); return res; } else { return DPF(P); } } vector<double> Random( int n) { vector<double> res; for (int j = 0; j < n; j++) res.push_back(rand() % 200-100); return res; } int main() { unsigned int Time1=0; unsigned int Time2 = 0; srand(time(0)); //Количество элементов int n = 4; vector<double> P; for (int i = 0; i < 1; i++) { P = Random(n); unsigned int start_time1 = clock(); vector <complex<double>> TestC1 = BPF(P); unsigned int end_time1 = clock(); unsigned int start_time2 = clock(); vector <complex<double>> TestC2 = BPF_Comb(P); unsigned int end_time2 = clock(); //for (int j = 0; j < n; j++) //{ // cout << TestC1[j].real() << " " << TestC1[j].imag() <<" | "<< TestC2[j].real() << " " << TestC2[j].imag()<< endl; //} Time1 += end_time1 - start_time1; Time2 += end_time2 - start_time2; } cout << double(Time1)/10000.0<<" "; cout << double(Time2) / 10000.0 << endl; } Карацуба #define _USE_MATH_DEFINES #include <iostream> #include <vector> #include <complex> #include <cmath> #include <time.h> using namespace std; vector <int> Karatsuba(vector<int> a, vector<int> b) { int n = a.size(); vector <int> res(2 * n,0); if (n == 1) { res = { a[0] * b[0] / 10, a[0] * b[0] % 10 }; return res; } vector <int> l(n/2),r(n/2); for (int i = 0; i < n / 2; i++) { l[i] = a[i] + a[i + n / 2]; r[i] = b[i] + b[i + n / 2]; } vector<int> a1(n / 2), b1(n / 2), a2(n / 2), b2(n / 2); a1.assign(a.begin(), a.begin()+n/2); a2.assign(a.begin() + n / 2, a.end()); b1.assign(b.begin(), b.begin() + n / 2 ); b2.assign(b.begin() + n / 2, b.end()); vector<int> t = Karatsuba(l, r); vector<int> p1 = Karatsuba(a1, b1); vector<int> p2 = Karatsuba(a2, b2); for (int i = 0; i < n; i++) res[i] = p1[i]; int j = 0; for (int i = n; i < 2 * n; i++) { res[i] = p2[j]; j++; } j = 0; for (int i = n / 2; i < 3 * n / 2; i++) { res[i] += t[j] - p1[j] - p2[j]; j++; } return res; } vector <int> Multiply(vector<int> a, vector<int> b) { vector<int> res(2*size(a),0); for(int i=0;i<a.size();i++) for (int j = 0; j < b.size(); j++) { int Multiply_mid = a[i] * b[j]; res[i + j + 1] += Multiply_mid % 10; res[i + j] += Multiply_mid / 10; } for (int i = res.size() - 1; i >= 1; i--) { res[i - 1] += res[i] / 10; res[i] %= 10; } if (res[0] == 0) res.erase(res.begin()); return res; } vector <int> Karatsuba_Comb(vector<int> a, vector<int> b) { int n = a.size(); vector <int> res(2 * n, 0); if (n <= 64) { return Multiply(a,b); } else { vector <int> l(n / 2), r(n / 2); for (int i = 0; i < n / 2; i++) { l[i] = a[i] + a[i + n / 2]; r[i] = b[i] + b[i + n / 2]; } vector<int> a1(n / 2), b1(n / 2), a2(n / 2), b2(n / 2); a1.assign(a.begin(), a.begin() + n / 2); a2.assign(a.begin() + n / 2, a.end()); b1.assign(b.begin(), b.begin() + n / 2); b2.assign(b.begin() + n / 2, b.end()); vector<int> t = Karatsuba(l, r); vector<int> p1 = Karatsuba(a1, b1); vector<int> p2 = Karatsuba(a2, b2); for (int i = 0; i < n; i++) res[i] = p1[i]; int j = 0; for (int i = n; i < 2 * n; i++) { res[i] = p2[j]; j++; } j = 0; for (int i = n / 2; i < 3 * n / 2; i++) { res[i] += t[j] - p1[j] - p2[j]; j++; } return res; } } vector<int> Random(int n) { vector<int> res; res.push_back(rand() % 9 + 1); for (int j = 1; j < n; j++) res.push_back(rand() % 10); return res; } int main() { unsigned int Time1 = 0; unsigned int Time2 = 0; unsigned int Time3 = 0; srand(time(0)); int n = 128; vector<int> a,b; for (int i = 0; i < 10000; i++) { a = Random(n); b = Random(n); /* for (int j = 0; j < n; j++) cout << a[j]; cout << "*"; for (int j = 0; j < n; j++) cout << b[j]; cout << endl; */ unsigned int start_time2 = clock(); vector <int> TestC1 = Multiply(a, b); unsigned int end_time2 = clock(); /* for (int j = 0; j < TestC1.size(); j++) cout << TestC1[j]; cout << endl; */ unsigned int start_time1 = clock(); vector <int> TestC2 = Karatsuba(a,b); for (int i = TestC2.size() - 1; i >= 1; i--) { TestC2[i - 1] += TestC2[i] / 10; TestC2[i] %= 10; } for (int i = 0; i < TestC2.size() - 1; i++) { if (TestC2[i + 1] < 0) { TestC2[i + 1] += 10; TestC2[i] -= 1; } } if (TestC2[0] == 0) TestC2.erase(TestC2.begin()); unsigned int end_time1 = clock(); /* for (int j = 0; j < TestC2.size(); j++) cout << TestC2[j]; cout << endl; */ unsigned int start_time3 = clock(); vector <int> TestC3 = Karatsuba_Comb(a, b); unsigned int end_time3 = clock(); /* for (int j = 0; j < TestC3.size(); j++) cout << TestC3[j]; cout << endl; */ Time1 += end_time1 - start_time1; Time2 += end_time2 - start_time2; Time3 += end_time3 - start_time3; } cout << "Karatsuba:"<<double(Time1) / 10000.0 << endl; cout <<"Usual:"<< double(Time2) / 10000.0 << endl; cout << "Comb:" << double(Time3) / 10000.0 << endl; } Виноград #define _USE_MATH_DEFINES #include <iostream> #include <vector> #include <complex> #include <cmath> #include <time.h> using namespace std; typedef vector <vector<int>> SV; SV Sum_Mat(SV a, SV b, int n) { SV res; for (int i = 0; i < n; i++) { res.push_back(vector<int>(n)); for (int j = 0; j < n; j++) res[i][j] = a[i][j] + b[i][j]; } return res; } SV Dif_Mat(SV a, SV b, int n) { SV res; for (int i = 0; i < n; i++) { res.push_back(vector<int>(n)); for (int j = 0; j < n; j++) res[i][j] = a[i][j] - b[i][j]; } return res; } SV Multiply(SV a, SV b, int n) { SV res; for (int i = 0; i < n; i++) { res.push_back(vector<int>(n)); for (int j = 0; j < n; j++) { int S = 0; for (int k = 0; k < n; k++) S += a[i][k] * b[k][j]; res[i][j] = S; } } return res; } SV StrVin(SV a, SV b,int n) { SV res,a11,a12,a21,a22,b11,b12,b21,b22; if (n == 2) { res = Multiply(a, b, n); } else { for (int i = 0; i < n / 2; i++) { a11.push_back(vector<int>(n / 2)); b11.push_back(vector<int>(n / 2)); for (int j = 0; j < n / 2; j++) { a11[i][j] = a[i][j]; b11[i][j] = b[i][j]; } } for (int i = 0; i < n/2; i++) { a12.push_back(vector<int>(n / 2)); b12.push_back(vector<int>(n / 2)); for (int j = n/2; j < n ; j++) { a12[i][j-n/2] = a[i][j]; b12[i][j-n/2] = b[i][j]; } } for (int i = n / 2; i < n ; i++) { a21.push_back(vector<int>(n / 2)); b21.push_back(vector<int>(n / 2)); for (int j = 0; j < n/2 ; j++) { a21[i- n / 2][j] = a[i][j]; b21[i- n / 2][j] = b[i][j]; } } for (int i = n/2; i < n; i++) { a22.push_back(vector<int>(n / 2)); b22.push_back(vector<int>(n / 2)); for (int j = n/2; j < n; j++) { a22[i- n / 2][j- n / 2] = a[i][j]; b22[i- n / 2][j- n / 2] = b[i][j]; } } SV S1 = Sum_Mat(a21, a22, n / 2); SV S2 = Dif_Mat(S1, a11, n / 2); SV S3 = Dif_Mat(a11, a21, n / 2); SV S4 = Dif_Mat(a12, S2, n / 2); SV S5 = Dif_Mat(b12, b11, n / 2); SV S6 = Dif_Mat(b22, S5, n / 2); SV S7 = Dif_Mat(b22, b12, n / 2); SV S8 = Dif_Mat(S6, b21, n / 2); SV P1 = StrVin(S2, S6,n/2); SV P2 = StrVin(a11, b11, n / 2); SV P3 = StrVin(a12, b21, n / 2); SV P4 = StrVin(S3, S7, n / 2); SV P5 = StrVin(S1, S5, n / 2); SV P6 = StrVin(S4, b22, n / 2); SV P7 = StrVin(a22, S8, n / 2); SV T1 = Sum_Mat(P1, P2, n / 2); SV T2 = Sum_Mat(T1, P4, n / 2); SV c11 = Sum_Mat(P2, P3, n / 2); SV c12 = Sum_Mat(Sum_Mat(T1, P5, n / 2), P6, n / 2); SV c21 = Dif_Mat(T2, P7, n / 2); SV c22 = Sum_Mat(T2, P5, n / 2); for (int i = 0; i < n/2; i++) { res.push_back(vector<int>(n)); for (int j = 0; j < n / 2; j++) res[i][j] = c11[i][j]; for (int j = n/2; j < n; j++) res[i][j] = c12[i][j-n/2]; } for (int i = n/2; i < n; i++) { res.push_back(vector<int>(n)); for (int j = 0; j < n / 2; j++) res[i][j] = c21[i-n/2][j]; for (int j = n / 2; j < n; j++) res[i][j] = c22[i-n/2][j - n / 2]; } } return res; } SV StrVin_Comb(SV a, SV b,int n) { SV res, a11, a12, a21, a22, b11, b12, b21, b22; if (n<=64) { res = Multiply(a, b, n); } else { for (int i = 0; i < n / 2; i++) { a11.push_back(vector<int>(n / 2)); b11.push_back(vector<int>(n / 2)); for (int j = 0; j < n / 2; j++) { a11[i][j] = a[i][j]; b11[i][j] = b[i][j]; } } for (int i = 0; i < n / 2; i++) { a12.push_back(vector<int>(n / 2)); b12.push_back(vector<int>(n / 2)); for (int j = n / 2; j < n; j++) { a12[i][j - n / 2] = a[i][j]; b12[i][j - n / 2] = b[i][j]; } } for (int i = n / 2; i < n; i++) { a21.push_back(vector<int>(n / 2)); b21.push_back(vector<int>(n / 2)); for (int j = 0; j < n / 2; j++) { a21[i - n / 2][j] = a[i][j]; b21[i - n / 2][j] = b[i][j]; } } for (int i = n / 2; i < n; i++) { a22.push_back(vector<int>(n / 2)); b22.push_back(vector<int>(n / 2)); for (int j = n / 2; j < n; j++) { a22[i - n / 2][j - n / 2] = a[i][j]; b22[i - n / 2][j - n / 2] = b[i][j]; } } SV S1 = Sum_Mat(a21, a22, n / 2); SV S2 = Dif_Mat(S1, a11, n / 2); SV S3 = Dif_Mat(a11, a21, n / 2); SV S4 = Dif_Mat(a12, S2, n / 2); SV S5 = Dif_Mat(b12, b11, n / 2); SV S6 = Dif_Mat(b22, S5, n / 2); SV S7 = Dif_Mat(b22, b12, n / 2); SV S8 = Dif_Mat(S6, b21, n / 2); SV P1 = StrVin(S2, S6, n / 2); SV P2 = StrVin(a11, b11, n / 2); SV P3 = StrVin(a12, b21, n / 2); SV P4 = StrVin(S3, S7, n / 2); SV P5 = StrVin(S1, S5, n / 2); SV P6 = StrVin(S4, b22, n / 2); SV P7 = StrVin(a22, S8, n / 2); SV T1 = Sum_Mat(P1, P2, n / 2); SV T2 = Sum_Mat(T1, P4, n / 2); SV c11 = Sum_Mat(P2, P3, n / 2); SV c12 = Sum_Mat(Sum_Mat(T1, P5, n / 2), P6, n / 2); SV c21 = Dif_Mat(T2, P7, n / 2); SV c22 = Sum_Mat(T2, P5, n / 2); for (int i = 0; i < n / 2; i++) { res.push_back(vector<int>(n)); for (int j = 0; j < n / 2; j++) res[i][j] = c11[i][j]; for (int j = n / 2; j < n; j++) res[i][j] = c12[i][j - n / 2]; } for (int i = n / 2; i < n; i++) { res.push_back(vector<int>(n)); for (int j = 0; j < n / 2; j++) res[i][j] = c21[i - n / 2][j]; for (int j = n / 2; j < n; j++) res[i][j] = c22[i - n / 2][j - n / 2]; } } return res; } SV Random(int n) { SV res; for (int i = 0; i < n; i++) { res.push_back(vector<int>()); for (int j = 0; j < n; j++) res[i].push_back ( rand() % 100); } return res; } int main() { unsigned int Time1 = 0; unsigned int Time2 = 0; unsigned int Time3 = 0; srand(time(0)); int n = 128; SV a, b; for (int i1 = 0; i1 < 1; i1++) { a = Random(n); b = Random(n); /* for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << a[i][j] << " "; cout << endl; } cout << "*" << endl;; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << b[i][j] << " "; cout << endl; } cout << endl; */ unsigned int start_time2 = clock(); SV TestC1 = Multiply(a, b,n); unsigned int end_time2 = clock(); /* for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << TestC1[i][j] << " "; cout << endl; } cout << endl; */ unsigned int start_time1 = clock(); SV TestC2 = StrVin(a, b,n); unsigned int end_time1 = clock(); /* for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << TestC2[i][j] << " "; cout << endl; } cout << endl; */ unsigned int start_time3 = clock(); SV TestC3 = StrVin_Comb(a, b,n); unsigned int end_time3 = clock(); /* for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) // cout << TestC3[i][j] << " "; cout << endl; } cout << endl; */ Time1 += end_time1 - start_time1; Time2 += end_time2 - start_time2; Time3 += end_time3 - start_time3; } cout << "StrVin:" << double(Time1) / 100.0 << endl; cout << "Usual:" << double(Time2) / 100.0 << endl; cout << "Comb:" << double(Time3) / 100.0 << endl; }