Strassen Multiplication

import java.util.*;
import java.io.*;
class strassen
{
    public static void read(int x[][],int n)throws IOException
    {
        BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter matrix");
        for(int i=0;i
        {
            for(int j=0;j
            {
                x[i][j]=Integer.parseInt(b.readLine());
            }
           
        }
    }
    public static void display(int x[][],int n)
    {
        for(int i=0;i
        {
            for(int j=0;j
            {
                System.out.print(x[i][j]+" ");
                    System.out.println(" ");
               
           
            }
        }
    }
    public static int[][] add(int x[][],int y[][],int n)
    {
        int z[][]=new int[n][n];
        for(int i=0;i
        {
            for(int j=0;j
            {
                z[i][j]=x[i][j]+y[i][j];
            }
        }
        return z;
    }
    public static int[][] prod(int x[][],int y[][])
    {
        int z[][]=new int[2][2];
        int p,q,r,s,t,u,v;
        p=(x[0][0]+x[1][1])*(y[0][0]+y[1][1]);
        q=(x[1][0]+x[1][1])*y[0][0];
        r=x[0][0]*(y[0][1]-y[1][1]);
        s=x[1][1]*(y[1][0]-y[0][0]);
        t=(x[0][0]+x[0][1])*y[1][1];
        u=(x[1][0]-x[0][0])*(y[0][0]+y[0][1]);
        v=(x[0][1]-x[1][1])*(y[1][0]+y[1][1]);
        z[0][0]=p+s-t+v;
        z[0][1]=r+t;
        z[1][0]=q+s;
        z[1][1]=p+r-q+u;
        return z;
    }
    public static void store(int p[][],int res[][],int is,int ie,int js,int je)
    {
        for(int i=is,i1=0;i
        {
            for(int j=is,j1=0;j
            {
                res[i][j]=p[i1][j1];
            }
        }
    }
    public static int[][] mult(int x[][],int y[][],int n)
    {
        if(n==2)
            return(prod(x,y));
        int x1[][]=new int[n/2][n/2];
        int x2[][]=new int[n/2][n/2];
        int x3[][]=new int[n/2][n/2];
        int x4[][]=new int[n/2][n/2];
        int y1[][]=new int[n/2][n/2];
        int y2[][]=new int[n/2][n/2];
        int y3[][]=new int[n/2][n/2];
        int y4[][]=new int[n/2][n/2];
        for(int i=0;i
        {
            for(int j=0;j
            {
               
                x1[i][j]=x[i][j];
                y1[i][j]=y[i][j];
               
            }
        }
        for(int i=0,i1=0;i
        {
            for(int j=n/2,j1=0;j
            {
                x2[i1][j1]=x[i][j];
                y2[i1][j1]=y[i][j];
       
            }
        }
        for(int i=n/2,i1=0;i
        {
            for(int j=0,j1=0;j
            {
                x3[i1][j1]=x[i][j];
                y3[i1][j1]=y[i][j];
            }
        }
        for(int i=n/2,i1=0;i
        {
            for(int j=n/2,j1=0;j
            {
                x4[i1][j1]=x[i][j];
                y4[i1][j1]=y[i][j];
            }
        }
        int k[][][]=new int[8][][];
        k[0]=mult(x1,y1,n/2);
        k[1]=mult(x2,y3,n/2);
        k[2]=mult(x1,y2,n/2);
        k[3]=mult(x2,y4,n/2);
        k[4]=mult(x3,y1,n/2);
        k[5]=mult(x4,y2,n/2);
        k[6]=mult(x3,y2,n/2);
        k[7]=mult(x4,y4,n/2);
        int partial[][][]=new int[4][][],j=0;
        for(int i=0;i
        {
            partial[j]=add(k[i],k[i+1],n/2);
            j++;
        }
        int result[][]=new int[n][n];
        store(partial[0],result,0,n/2,0,n/2);
        store(partial[1],result,0,n/2,n/2,0);
        store(partial[0],result,n/2,n,0,n/2);
        store(partial[0],result,n/2,n,n/2,n);
        return result;
        }
}
class StrassenDemo
{
    public static void main(String args[])throws IOException
    {
            BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
            System.out.println("Enter the order of the matrix");
            int n=Integer.parseInt(b.readLine());
            int a[][]=new int[n][n];
            int d[][]=new int[n][n];
            strassen s=new strassen();
            s.read(a,n);
            s.read(d,n);
            int c[][]=s.mult(a,d,n);
            System.out.println("Strassen Matrix Multiplication\nResult Matrix");
            s.display(c,n);
        }
}
/*Output
Enter the order of the matrix
2
Enter matrix
5
6
7
4
Enter matrix
4
2
1
5
Strassen Matrix Multiplication
Result Matrix
26 
40 
32 
34 
*/