Лабораторная работа №4-5

Реализация быстрых алгоритмов (на деле окажется, что они не быстрые) и так же реализованы и комбинированные алгоритмы как отдельная функция

• БПФ
• Карацуба
• Виноград

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;
}