Дыч2

using System;
using System.Text;

namespace Курсовая_АСД
{
    class Program
    {
        static void Main(string[] args)
        {
            var Matrix1 = GenerateBlock(6);
            var Matrix2 = GenerateBlock(6);
            Console.WriteLine(Matrix1.ToString());
            Console.WriteLine();
            Console.WriteLine(Matrix2.ToString());
            Console.WriteLine();
            Console.WriteLine(ShtrassenMyltiply(Matrix1, Matrix2).ToString());
            Console.ReadLine();
        }

        static long Power(int x, int n)
        {
            if (n == 0)
                return 1;

            if ((n & 1) == 0)
            {
                var p = Power(x, n >> 1);
                return p * p;
            }
            else
            {
                return x * Power(x, n - 1);
            }
        }

        static Block GenerateBlock(int Degree)
        {
            var size = (int)Power(2, Degree);

            Random random = new Random(DateTime.Now.Millisecond);

            var matrix = new Block(size, size);

            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    matrix[i, j] = random.Next(10);
                }
            }
            return matrix;
        }

        static Block ShtrassenMyltiply(Block FirstMatrix, Block SecondMatrix)
        {
            int DefaultSize = FirstMatrix.Length;
            var matrix1 = OnBlocks(FirstMatrix);
            var matrix2 = OnBlocks(SecondMatrix);
            if (DefaultSize > 32)
            {
                int NewSize = FirstMatrix.Length >> 1;
                var x1 = ShtrassenMyltiply(matrix1[0, 0] + matrix1[1, 1], matrix2[0, 0] + matrix2[1, 1]);
                var x2 = ShtrassenMyltiply(matrix1[1, 0] + matrix1[1, 1], matrix2[0, 0]);
                var x3 = ShtrassenMyltiply(matrix1[0, 0], matrix2[0, 1] - matrix2[1, 1]);
                var x4 = ShtrassenMyltiply(matrix1[1, 1], matrix2[1, 0] - matrix2[0, 0]);
                var x5 = ShtrassenMyltiply(matrix1[0, 0] + matrix1[0, 1], matrix2[1, 1]);
                var x6 = ShtrassenMyltiply(matrix1[1, 0] - matrix1[0, 0], matrix2[0, 0] + matrix2[0, 1]);
                var x7 = ShtrassenMyltiply(matrix1[0, 1] - matrix1[1, 1], matrix2[1, 0] + matrix2[1, 1]);

                var X1 = (x1 + x4) + (x7 - x5);
                var X2 = x3 + x5;
                var X3 = x2 + x4;
                var X4 = (x3 + x6) + (x1 - x2);

                var ResultMatrix = new Block(DefaultSize, DefaultSize);

                for (int i = 0; i < NewSize; i++)
                {
                    for (int j = 0; j < NewSize; j++)
                    {
                        ResultMatrix[i, j] = X1[i, j];
                        ResultMatrix[i, j + NewSize] = X2[i, j];
                        ResultMatrix[i + NewSize, j] = X3[i, j];
                        ResultMatrix[i + NewSize, j + NewSize] = X4[i, j];
                    }
                }
                return ResultMatrix;
            }
            else
            {
                var Result = TraditionalMyltiply(FirstMatrix, SecondMatrix);
                return Result;
            }
        }


        static Block TraditionalMyltiply(Block FirstMatrix, Block SecondMatrix)
        {
            var size = FirstMatrix.Length;
            var result = new Block(size, size);
            for (int i = 0; i < size; i++)
                for (int j = 0; j < size; j++)
                {
                    result[i, j] = 0;
                    for (int k = 0; k < size; k++)
                        result[i, j] = result[i, j] + FirstMatrix[i, k] * SecondMatrix[k, j];
                }
            return result;
        }
        static Block[,] OnBlocks(Block Matrix)
        {
            //Верхний левый угол
            int NewSize = Matrix.Length >> 1;
            int DefaultSize = Matrix.Length;
            var ResultMatrix = new Block[2, 2];
            var s1 = new Block(NewSize, NewSize);
            var s2 = new Block(NewSize, NewSize);
            var s3 = new Block(NewSize, NewSize);
            var s4 = new Block(NewSize, NewSize);
            for (int i = 0; i < NewSize; i++)
            {
                for (int j = 0; j < NewSize; j++)
                {
                    s1[i, j] = Matrix[i, j];
                }
            }
            //Верхний правый угол
            for (int i = 0; i < NewSize; i++)
            {
                for (int j = NewSize; j < DefaultSize; j++)
                {
                    s2[i, j - NewSize] = Matrix[i, j];
                }
            }
            //Нижний левый угол
            for (int i = NewSize; i < DefaultSize; i++)
            {
                for (int j = 0; j < NewSize; j++)
                {
                    s3[i - NewSize, j] = Matrix[i, j];
                }
            }
            //Нижнинй правый угол
            for (int i = NewSize; i < DefaultSize; i++)
            {
                for (int j = NewSize; j < DefaultSize; j++)
                {
                    s4[i - NewSize, j - NewSize] = Matrix[i, j];
                }
            }
            ResultMatrix[0, 0] = s1;
            ResultMatrix[0, 1] = s2;
            ResultMatrix[1, 0] = s3;
            ResultMatrix[1, 1] = s4;
            return ResultMatrix;
        }
    }
    class Block
    {
        public int Length { get; private set; }
        private int[,] matrix;
        public Block(int x, int y)
        {
            matrix = new int[x, y];
            Length = x;
        }

        public int this[int x, int y]
        {
            get { return matrix[x, y]; }
            set { matrix[x, y] = value; }
        }
        public bool ArrayToBlock(int[,] arr)
        {
            if (arr.GetLength(0) != arr.GetLength(1)) return false;
            matrix = new int[arr.GetLength(0), arr.GetLength(1)];
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                for (int j = 0; j < arr.GetLength(1); j++)
                {
                    this[i, j] = arr[i, j];
                }
            }
            return true;
        }
        public override string ToString()
        {
            StringBuilder ret = new StringBuilder();
            if (matrix == null) return ret.ToString();

            for (int i = 0; i < Length; i++)
            {
                for (int t = 0; t < Length; t++)
                {
                    ret.Append(matrix[i, t]);
                    ret.Append("\t");
                }
                ret.Append("\n");
            }
            return ret.ToString();
        }
        public static Block operator +(Block matrix1, Block matrix2)
        {
            var ResultMatrix = new Block(matrix1.Length, matrix1.Length);
            for (int i = 0; i < matrix1.Length; i++)
            {
                for (int j = 0; j < matrix1.Length; j++)
                {
                    ResultMatrix[i, j] = matrix1[i, j] + matrix2[i, j];
                }
            }
            return ResultMatrix;
        }
        public static Block operator -(Block matrix1, Block matrix2)
        {
            var ResultMatrix = new Block(matrix1.Length, matrix1.Length);
            for (int i = 0; i < matrix1.Length; i++)
            {
                for (int j = 0; j < matrix1.Length; j++)
                {
                    ResultMatrix[i, j] = matrix1[i, j] - matrix2[i, j];
                }
            }
            return ResultMatrix;
        }
    }
}