L
L
lycyfer2021-06-07 20:29:58
C++ / C#
lycyfer, 2021-06-07 20:29:58

Matrix multiplication by Strassen's algorithm?

class Strassen
    {

        static void Main(string[] args)
        {
            Strassen s = new Strassen();
            Console.WriteLine("Введите количество строк");
            int size =Convert.ToInt32(Console.ReadLine());
           
            //while (size % 4 != 0)//создание матрицы подходящего размера
            //{
            //    size++;
            //}
            Random rnd = new Random();

            int[,] a = new int[size, size];
            int[,] b = new int[size, size];
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {

                    a[i, j] = rnd.Next(0, 32);
                }
            }
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {

                    b[i, j] = rnd.Next(0, 32);
                }
            }
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (a[i, j] < 10 && a[i, j] > -10) Console.Write(" " + a[i, j] + "  ");
                    else Console.Write(" " + a[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (b[i, j] < 10 && b[i, j] > -10) Console.Write(" " + b[i, j] + "  ");
                    else Console.Write(" " + b[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
            
            int[,]C= s.Multiplay(a, b, size);
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (C[i, j] < 10 && C[i, j] > -10) Console.Write(" " + C[i, j] + "  ");
                    else Console.Write(" " + C[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.ReadKey();

        }
        //Метод Сложения 
        public int[,] add(int[,] A, int[,] B, int size)
        {
            int[,] C = new int[size/2, size/2];
            for (int i = 0; i < size/2 ; i++)
            {
                for (int j = 0; j < size/2; j++)
                {
                    C[i, j] = A[i, j] + B[i, j];
                }
            }
            return C;
        }
        //Метод разложения
        public void split(int[,] P, int[,] C, int iB, int jB, int size)
        {

            for (iB = 0; iB < size / 2; iB ++)
            {
                for (jB = 0; jB < size / 2; jB ++)
                {
                    for (int i = iB; i < size/2 ; i++)
                    {
                        for (int j = jB; j < size/2; j++)
                        {
                            
                                C[i, j] = P[iB, jB];
                            
                        }
                    }
                }

            }
        }
        
        public void join(int[,] C, int[,] P, int iB, int jB, int size)
        {

            for (int i1 = 0, i2 = iB; i1 < size; i1++, i2++)
            {
                for (int j1 = 0, j2 = jB; j1 < size ; j1++, j2++)
                {

                    P[i2, j2] = C[i1, j1];
                }
            }
        }
        //Метод вычитания 
        public int[,] sub(int[,] A, int[,] B, int size)
        {

            int[,] C = new int[size, size]; ;
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    C[i, j] = A[i, j] - B[i, j];
                }
            }
            return C;
        }
        //Алгоритм Штрассена
        public int[,] Multiplay(int[,] A, int[,] B, int size)
        {
            int n = size;
            int[,] C = new int[size,size];
            if (n == 2)
            {
                C[0, 0] = A[0, 0] * B[0, 0];
            }
            else
            {
                int[,] A11 = new int[n / 2, n / 2];
                int[,] A12 = new int[n / 2, n / 2];
                int[,] A21 = new int[n / 2, n / 2];
                int[,] A22 = new int[n / 2, n / 2];
                int[,] B11 = new int[n / 2, n / 2];
                int[,] B12 = new int[n / 2, n / 2];
                int[,] B21 = new int[n / 2, n / 2];
                int[,] B22 = new int[n / 2, n / 2];


                split(A, A11, 0, 0, size);
                split(A, A12, 0, 2, size);
                split(A, A21, n / 2, 0, size);
                split(A, A22, n / 2, n / 2, size);


                split(B, B11, 0, 0, size);
                split(B, B12, 0, n / 2, size);
                split(B, B21, n / 2, 0, size);
                split(B, B22, n / 2, n / 2, size);


                int[,] M1 = Multiplay(add(A11, A22, size), add(B11, B22, size), size);
                int[,] M2 = Multiplay(add(A11, A22, size), B11, size);
                int[,] M3 = Multiplay(A11, sub(B12, B22, size), size);
                int[,] M4 = Multiplay(A22, sub(B21, B11, size), size);
                int[,] M5 = Multiplay(add(A11, A12, size), B22, size);
                int[,] M6 = Multiplay(sub(A21, A11, size), add(B11, B12, size), size);
                int[,] M7 = Multiplay(sub(A12, A22, size), add(B21, B22, size), size);


                int[,] C11 = add(sub(add(M1, M4, size), M5, size), M7, size);
                int[,] C12 = add(M3, M5, size);
                int[,] C21 = add(M2, M4, size);
                int[,] C22 = add(sub(add(M1, M3, size), M2, size), M6, size);


                join(C11, C, 0, 0, size);
                join(C12, C, 0, n / 2, size);
                join(C21, C, n / 2, 0, size);
                join(C22, C, n / 2, n / 2, size);
            }
            return C;
        }
    }
}

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question