RecursiveMatrixMultiplier implements MatrixMultiplier { @Override public <E extends Number> Matrix<E> multiply(Matrix<E> first, Matrix<E> second) { if (first.getColumns() != first.getRows()) { throw new IllegalArgumentException("First matrix isn't square: " + first.getRows() + "x" + first.getColumns()); } if (second.getColumns() != second.getRows()) { throw new IllegalArgumentException("Second matrix isn't square: " + second.getRows() + "x" + second.getColumns()); } if ((first.getColumns() & (first.getColumns() - 1)) != 0) { throw new IllegalArgumentException("The first matrix's dimension is not a power of two"); } if ((second.getColumns() & (second.getColumns() - 1)) != 0) { throw new IllegalArgumentException("The second matrix's dimension is not a power of two"); } if (first.getRows() != second.getColumns()) { throw new IllegalArgumentException("Incompatible matrix dimensions"); } final int size = first.getColumns(); final Matrix<E> result = factory.getMatrix(size, size); if (size == 1) { result.set(0, 0, NumberUtils.multiply(first.get(0, 0), second.get(0, 0))); } else { final int newSize = size / 2; final DelegatingMatrix<E> firstTopLeft = new DelegatingMatrix<>(first, 0, 0, newSize, newSize); final DelegatingMatrix<E> firstTopRight = new DelegatingMatrix<>(first, 0, newSize, newSize, size - newSize); final DelegatingMatrix<E> firstBottomLeft = new DelegatingMatrix<>(first, newSize, 0, size - newSize, newSize); final DelegatingMatrix<E> firstBottomRight = new DelegatingMatrix<>(first, newSize, newSize, size - newSize, size - newSize); final DelegatingMatrix<E> secondTopLeft = new DelegatingMatrix<>(second, 0, 0, newSize, newSize); final DelegatingMatrix<E> secondTopRight = new DelegatingMatrix<>(second, 0, newSize, newSize, size - newSize); final DelegatingMatrix<E> secondBottomLeft = new DelegatingMatrix<>(second, newSize, 0, size - newSize, newSize); final DelegatingMatrix<E> secondBottomRight = new DelegatingMatrix<>(second, newSize, newSize, size - newSize, size - newSize); final Matrix<E> resultTopLeft = new DelegatingMatrix<>(result, 0, 0, newSize, newSize); final Matrix<E> resultTopRight = new DelegatingMatrix<>(result, 0, newSize, newSize, size - newSize); final Matrix<E> resultBottomLeft = new DelegatingMatrix<>(result, newSize, 0, size - newSize, newSize); final Matrix<E> resultBottomRight = new DelegatingMatrix<>(result, newSize, newSize, size - newSize, size - newSize); copy(sum(multiply(firstTopLeft, secondTopLeft), multiply(firstTopRight, secondBottomLeft)), resultTopLeft); copy(sum(multiply(firstTopLeft, secondTopRight), multiply(firstTopRight, secondBottomRight)), resultTopRight); copy(sum(multiply(firstBottomLeft, secondTopLeft), multiply(firstBottomRight, secondBottomLeft)), resultBottomLeft); copy(sum(multiply(firstBottomLeft, secondTopRight), multiply(firstBottomRight, secondBottomRight)), resultBottomRight); } return result; } RecursiveMatrixMultiplier();  RecursiveMatrixMultiplier(MatrixFactory factory); @Override Matrix<E> multiply(Matrix<E> first, Matrix<E> second);  }
@Test public void testSquareMultiplication() throws Exception { final MatrixMultiplier multiplier = new RecursiveMatrixMultiplier(); final Matrix<Integer> first = new ArrayMatrix<>(4, 4); first.set(0, 0, 0); first.set(0, 1, 1); first.set(0, 2, 2); first.set(0, 3, 3); first.set(1, 0, 1); first.set(1, 1, 2); first.set(1, 2, 3); first.set(1, 3, 0); first.set(2, 0, 2); first.set(2, 1, 3); first.set(2, 2, 0); first.set(2, 3, 1); first.set(3, 0, 3); first.set(3, 1, 0); first.set(3, 2, 1); first.set(3, 3, 2); final Matrix<Integer> second = new ArrayMatrix<>(4, 4); second.set(0, 0, 0); second.set(0, 1, 1); second.set(0, 2, -2); second.set(0, 3, -4); second.set(1, 0, 1); second.set(1, 1, -1); second.set(1, 2, -3); second.set(1, 3, 0); second.set(2, 0, 3); second.set(2, 1, -3); second.set(2, 2, 0); second.set(2, 3, 1); second.set(3, 0, -7); second.set(3, 1, -1); second.set(3, 2, 1); second.set(3, 3, -1); final Matrix<Integer> result = multiplier.multiply(first, second); assertThat(result.getRows(), is(4)); assertThat(result.getColumns(), is(4)); assertThat(result.get(0, 0), is(-14)); assertThat(result.get(0, 1), is(-10)); assertThat(result.get(0, 2), is(0)); assertThat(result.get(0, 3), is(-1)); assertThat(result.get(1, 0), is(11)); assertThat(result.get(1, 1), is(-10)); assertThat(result.get(1, 2), is(-8)); assertThat(result.get(1, 3), is(-1)); assertThat(result.get(2, 0), is(-4)); assertThat(result.get(2, 1), is(-2)); assertThat(result.get(2, 2), is(-12)); assertThat(result.get(2, 3), is(-9)); assertThat(result.get(3, 0), is(-11)); assertThat(result.get(3, 1), is(-2)); assertThat(result.get(3, 2), is(-4)); assertThat(result.get(3, 3), is(-13)); }