Krdytkyu

I have written an implementation of the Strassen Vinograde Algorithm, but it's running slowly because of recursive creation of static arrays. I know that dynamic arrays would solve this problem, but I'm not allow to use them. So the main idea of this version of Strassen: We use corner elements of each square instead of copying every sub-square. I think something like this we should apply for the arrays that I create recursively.
In general, the main problem is that the algorithm is several times slower than usual even at larger values ​​of n.

    #include "pch.h"

    #include<iostream>

    #include<cstdio>

    #include<conio.h>

    #include<cstdlib>

    #include<cmath>

    #include<ctime>

    #pragma comment(linker, "/STACK:5813242100")

    using namespace std;

    const int sizs = 256;



    void vivod(int matrix[256], int n);

    void Matrix_Add(int a[256], int b[256], int c[256], int n, int x1, int y1, int x2, int y2); 

    void Matrix_Sub(int a[256], int b[256], int c[256], int n, int x1, int y1, int x2, int y2);

    void Matrix_Multiply(int a[256], int b[256], int c[256], int x1, int y1, int x2, int y2, int n);

    void strassen(int a[256], int b[256], int c[256], int m, int n, int x1, int y1, int x2, int y2);

    void Naive_Multiply(int a[256], int b[256], int c[256], int n);



    int main()

    {

        setlocale(LC_ALL, "Russian");

        int n;

        cout << "Enter the N:";

        cin >> n;

        const int m = 256;

        int A[m][m];

        int B[m][m];

        int C[m][m];

        int k[m][m];

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                A[i][j] = 0;

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                B[i][j] = 0;

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                A[i][j] = rand() % 10;

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                B[i][j] = rand() % 10;

        cout << "First Matrix:" << endl;

        //vivod(A, n);

        cout << "Second Matrix:" << endl;

        //vivod(B, n);

        int begin = clock();

        //for (int i =0; i < 100; i++)

        Naive_Multiply(A, B, k, n);

        int end = clock();

        cout << "Naive Multiply tacts: " << end - begin << endl;

        //vivod(k, n);

        int begin2 = clock();

        //for (int i = 0; i < 100; i++)

        strassen(A, B, C, n, n, 0, 0, 0, 0);

        int end2 = clock();

        cout << "Shtrassen tacts: " << end2 - begin2 << endl;

        //vivod(C, n);

        system("pause");

        return 0;

    }



    void strassen(int a[256], int b[256], int c[256], int m, int n, int x1, int y1, int x2, int y2) {

        m = n / 2;

        if (m != 1)

        {

            int s1[sizs][sizs];

            int s2[sizs][sizs];

            int s3[sizs][sizs];

            int s4[sizs][sizs];

            int s5[sizs][sizs];

            int s6[sizs][sizs];

            int s7[sizs][sizs];

            int s8[sizs][sizs];

            int m1[sizs][sizs];

            int m2[sizs][sizs];

            int m3[sizs][sizs];

            int m4[sizs][sizs];

            int m5[sizs][sizs];

            int m6[sizs][sizs];

            int m7[sizs][sizs];

            int t1[sizs][sizs];

            int t2[sizs][sizs];

            int c11[sizs][sizs];

            int c12[sizs][sizs];

            int c21[sizs][sizs];

            int c22[sizs][sizs];

            Matrix_Add(a, a, s1, m, x1 + m, y1, x1 + m, y1 + m);

            Matrix_Sub(s1, a, s2, m, 0, 0, x1, y1);

            Matrix_Sub(a, a, s3, m, x1, y1, x1 + m, y1);

            Matrix_Sub(a, s2, s4, m, x1, y1 + m, 0, 0);

            Matrix_Sub(b, b, s5, m, x2, y2 + m, x2, y2);

            Matrix_Sub(b, s5, s6, m, x2 + m, y2 + m, 0, 0);

            Matrix_Sub(b, b, s7, m, x2 + m, y2 + m, x2, y2 + m);

            Matrix_Sub(s6, b, s8, m, 0, 0, x2 + m, y2);

            strassen(s2, s6, m1, m, m, 0, 0, 0, 0);

            strassen(a, b, m2, m, m, x1, y1, x2, y2);

            strassen(a, b, m3, m, m, x1, y1 + m, x2 + m, y2);

            strassen(s3, s7, m4, m, m, 0, 0, 0, 0);

            strassen(s1, s5, m5, m, m, 0, 0, 0, 0);

            strassen(s4, b, m6, m, m, 0, 0, x2 + m, y2 + m);

            strassen(a, s8, m7, m, m, x1 + m, y1 + m, 0, 0);



            Matrix_Add(m1, m2, t1, m, 0, 0, 0, 0);

            Matrix_Add(t1, m4, t2, m, 0, 0, 0, 0);

            Matrix_Add(m2, m3, c11, m, 0, 0, 0, 0);

            Matrix_Sub(t2, m7, c21, m, 0, 0, 0, 0);

            Matrix_Add(t1, m5, c12, m, 0, 0, 0, 0);

            Matrix_Add(c12, m6, c12, m, 0, 0, 0, 0);

            Matrix_Add(t2, m5, c22, m, 0, 0, 0, 0);

            for (int i = 0; i < n / 2; i++)

            {

                for (int j = 0; j < n / 2; j++)

                {

                    c[i + n - 2 * m][j + n - 2 * m] = c11[i][j];

                    c[i + n - 2 * m][j + n - m] = c12[i][j];

                    c[i + n - m][j + n - 2 * m] = c21[i][j];

                    c[i + n - m][j + n - m] = c22[i][j];

                }

            }

        }

        else

        {

            Matrix_Multiply(a, b, c, x1, y1, x2, y2, n);

        }

    }

    void vivod(int matrix[256], int n)

    {

        for (int i = 0; i < n; i++)

        {

            for (int j = 0; j < n; j++)

            {

                cout << matrix[i][j] << " ";

            }

            cout << endl;

        }

        cout << endl;

    }

    void Matrix_Add(int a[256], int b[256], int c[256], int n, int x1, int y1, int x2, int y2)

    {

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                c[i][j] = a[i + x1][j + y1] + b[i + x2][j + y2];

            }

        }

    }



    void Matrix_Sub(int a[256], int b[256], int c[256], int n, int x1, int y1, int x2, int y2)

    {

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                c[i][j] = a[i + x1][j + y1] - b[i + x2][j + y2];

            }

        }

    }

    void Matrix_Multiply(int a[256], int b[256], int c[256], int x1, int y1, int x2, int y2, int n)

    {

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                c[i][j] = 0;

                for (int t = 0; t < n; t++) {

                    c[i][j] = c[i][j] + a[x1 + i][y1 + t] * b[x2 + t][y2 + j];

                }

            }

        }

    }

    void Naive_Multiply(int a[256], int b[256], int c[256], int n)

    {

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                c[i][j] = 0;

                for (int t = 0; t < n; t++) {

                    c[i][j] = c[i][j] + a[i][t] * b[t][j];

                }

            }

        }

    }

It probably may not even start, because of large amount of arrays, but i have launched it and here is the tests:

With N = 128 and 256 naive multiplication takes nearly 10 seconds, when at the same time I'm waiting for Strassen for ~1-5 minutes.