public class Strassen 
{
	
	public static double[][] multiply(double[][] A, double[][] B)
	{
		try
		{
			checkInputStrassen(A,B);
		}
		catch (RuntimeException e)
		{
			throw e;
		}
		return strassenRecursive(A,B);
	}
	
	private static double[][] reconstructAnswer(double[][] r, double[][] s,
			double[][] t, double[][] u) 
	{
		int n = r.length*2;
		double[][] C = new double[n][n];
		copyBack(C,r,0,0);
		copyBack(C,s,0,n/2);
		copyBack(C,t,n/2,0);
		copyBack(C,u,n/2,n/2);
		return C;
	}

	private static void copyBack(double[][] C, double[][] r, int x, int y) 
	{
		for (int i=0; i<r.length; i++)
		{
			for (int j=0; j<r.length; j++)
			{
				C[x+i][y+j] = r[i][j];
			}
		}
	}
	
	private static void copy(double[][] a, double[][] A, int x, int y) 
	{
		for (int i=0; i<a.length; i++)
		{
			for (int j=0; j<a.length; j++)
			{
				a[i][j] = A[x+i][y+j]; 
			}
		}
	}

	private static double[][] strassenRecursive(double[][] A, double[][] B) 
	{
		int n = A.length;
		if (n==1)
		{
			double[][] C = new double[1][1];
			C[0][0]=A[0][0]*B[0][0];
			return C;
		}
		
		double[][] r,s,t,u, a,b,c,d,e,f,g,h, P1,P2,P3,P4,P5,P6,P7;
		r = new double[n/2][n/2];		s = new double[n/2][n/2];		t = new double[n/2][n/2];		
		u = new double[n/2][n/2];		a = new double[n/2][n/2];		b = new double[n/2][n/2];		
		c = new double[n/2][n/2];		d = new double[n/2][n/2];		e = new double[n/2][n/2];		
		f = new double[n/2][n/2];		g = new double[n/2][n/2];		h = new double[n/2][n/2];
		P1 = new double[n/2][n/2];		P2 = new double[n/2][n/2];		P3 = new double[n/2][n/2];		
		P4 = new double[n/2][n/2];		P5 = new double[n/2][n/2];		P6 = new double[n/2][n/2];		
		P7 = new double[n/2][n/2];		
		copy(a,A,0,0);
		copy(b,A,0,n/2);
		copy(c,A,n/2,0);
		copy(d,A,n/2,n/2);
		copy(e,B,0,0);
		copy(f,B,0,n/2);
		copy(g,B,n/2,0);
		copy(h,B,n/2,n/2);

		P1= strassenRecursive(a, add(f,h,-1)); // P1 = a(f-h) = af-ah
		P2= strassenRecursive(add(a,b,1), h); // P2 = (a+b)h = ah+bh
		P3= strassenRecursive(add(c,d,1), e); // P3 = (c+d)e = ce+de
		P4= strassenRecursive(d, add(g,e,-1)); // P4 = d(g-e) = dg-de
		P5= strassenRecursive(add(a,d,1), add(e,h,1)); // P5 = (a+d)(e+h)=ae+de+ah+dh
		P6= strassenRecursive(add(b,d,-1), add(g,h,1)); // P6 = (b-d)(g+h)=bg-dg+bh-dh
		P7= strassenRecursive(add(a,c,-1), add(e,f,1)); // P7 = (a-c)(e+f)=ae-ce+af-cf
		
		r = add(add(P5,P4,1),add(P2,P6,-1),-1); // r = P5+P4-P2+P6 = ae+bg
		s = add(P1,P2,1); // s = P1+P2 = af+bh
		t = add(P3,P4,1); // t = P3+P4 = ce+dg
		u = add(add(P5,P1,1),add(P3,P7,1),-1); //u = P5+P1-P3-P7 = cf+dh
		return reconstructAnswer(r,s,t,u);
	}
	
	private static double[][] add(double[][] A, double[][] B, int signofB)
	{
		int n = A.length;
		double[][] C = new double[n][n];
		for (int i=0; i<n; i++)
		{
			for (int j=0; j<n; j++)
			{
				C[i][j] = A[i][j] + signofB*B[i][j];
			}
		}
		return C;
		
	}

	private static void checkInputStrassen(double[][] A, double[][] B) 
	{
		int p = A.length;
		if (p==0)
		{
			throw new IllegalArgumentException("Null matrix");
		}
		int n=p;
		while (n>1)
		{
			if (n%2 != 0)
			{
				throw new IllegalArgumentException("Non power of 2 matrix");
			}
			n/=2;
		}

		int q = A[0].length;
		if (q==0)
		{
			throw new IllegalArgumentException("Null matrix");
		}

		if (q!=p)
		{
			throw new IllegalArgumentException("Nonsquare Matrix");
		}

		for (int i=1; i<p; i++)
		{
			if (A[i].length != q)
			{
				throw new IllegalArgumentException("Inconsistent matrix");
			}
		}
		if (B.length != q)
		{
			throw new IllegalArgumentException("Inconsistent dimensions");
		}
		
		int r = B[0].length;
		if (r!=p)
		{
			throw new IllegalArgumentException("Nonsquare Matrix");
		}
		for (int i=1; i<q; i++)
		{
			if (B[i].length != r)
			{
				throw new IllegalArgumentException("Inconsistent matrix");
			}
		}
	}
}