fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ROW_1 4
  5. #define COL_1 4
  6.  
  7. #define ROW_2 4
  8. #define COL_2 4
  9.  
  10. void print(string display, vector<vector<int> > matrix,
  11.            int start_row, int start_column, int end_row,
  12.            int end_column)
  13. {
  14.     cout << endl << display << " =>" << endl;
  15.     for (int i = start_row; i <= end_row; i++) {
  16.         for (int j = start_column; j <= end_column; j++) {
  17.             cout << setw(10);
  18.             cout << matrix[i][j];
  19.         }
  20.         cout << endl;
  21.     }
  22.     cout << endl;
  23.     return;
  24. }
  25.  
  26. vector<vector<int> >
  27. add_matrix(vector<vector<int> > matrix_A,
  28.            vector<vector<int> > matrix_B, int split_index,
  29.            int multiplier = 1)
  30. {
  31.     for (auto i = 0; i < split_index; i++)
  32.         for (auto j = 0; j < split_index; j++)
  33.             matrix_A[i][j]
  34.                 = matrix_A[i][j]
  35.                   + (multiplier * matrix_B[i][j]);
  36.     return matrix_A;
  37. }
  38.  
  39. vector<vector<int> >
  40. multiply_matrix(vector<vector<int> > matrix_A,
  41.                 vector<vector<int> > matrix_B)
  42. {
  43.     int col_1 = matrix_A[0].size();
  44.     int row_1 = matrix_A.size();
  45.     int col_2 = matrix_B[0].size();
  46.     int row_2 = matrix_B.size();
  47.  
  48.     if (col_1 != row_2) {
  49.         cout << "\nError: The number of columns in Matrix "
  50.                 "A  must be equal to the number of rows in "
  51.                 "Matrix B\n";
  52.         return {};
  53.     }
  54.  
  55.     vector<int> result_matrix_row(col_2, 0);
  56.     vector<vector<int> > result_matrix(row_1,
  57.                                        result_matrix_row);
  58.  
  59.     if (col_1 == 1)
  60.         result_matrix[0][0]
  61.             = matrix_A[0][0] * matrix_B[0][0];
  62.     else {
  63.         int split_index = col_1 / 2;
  64.  
  65.         vector<int> row_vector(split_index, 0);
  66.  
  67.         vector<vector<int> > a00(split_index, row_vector);
  68.         vector<vector<int> > a01(split_index, row_vector);
  69.         vector<vector<int> > a10(split_index, row_vector);
  70.         vector<vector<int> > a11(split_index, row_vector);
  71.         vector<vector<int> > b00(split_index, row_vector);
  72.         vector<vector<int> > b01(split_index, row_vector);
  73.         vector<vector<int> > b10(split_index, row_vector);
  74.         vector<vector<int> > b11(split_index, row_vector);
  75.  
  76.         for (auto i = 0; i < split_index; i++)
  77.             for (auto j = 0; j < split_index; j++) {
  78.                 a00[i][j] = matrix_A[i][j];
  79.                 a01[i][j] = matrix_A[i][j + split_index];
  80.                 a10[i][j] = matrix_A[split_index + i][j];
  81.                 a11[i][j] = matrix_A[i + split_index]
  82.                                     [j + split_index];
  83.                 b00[i][j] = matrix_B[i][j];
  84.                 b01[i][j] = matrix_B[i][j + split_index];
  85.                 b10[i][j] = matrix_B[split_index + i][j];
  86.                 b11[i][j] = matrix_B[i + split_index]
  87.                                     [j + split_index];
  88.             }
  89.  
  90.         vector<vector<int> > p(multiply_matrix(
  91.             a00, add_matrix(b01, b11, split_index, -1)));
  92.         vector<vector<int> > q(multiply_matrix(
  93.             add_matrix(a00, a01, split_index), b11));
  94.         vector<vector<int> > r(multiply_matrix(
  95.             add_matrix(a10, a11, split_index), b00));
  96.         vector<vector<int> > s(multiply_matrix(
  97.             a11, add_matrix(b10, b00, split_index, -1)));
  98.         vector<vector<int> > t(multiply_matrix(
  99.             add_matrix(a00, a11, split_index),
  100.             add_matrix(b00, b11, split_index)));
  101.         vector<vector<int> > u(multiply_matrix(
  102.             add_matrix(a01, a11, split_index, -1),
  103.             add_matrix(b10, b11, split_index)));
  104.         vector<vector<int> > v(multiply_matrix(
  105.             add_matrix(a00, a10, split_index, -1),
  106.             add_matrix(b00, b01, split_index)));
  107.  
  108.         vector<vector<int> > result_matrix_00(add_matrix(
  109.             add_matrix(add_matrix(t, s, split_index), u,
  110.                        split_index),
  111.             q, split_index, -1));
  112.         vector<vector<int> > result_matrix_01(
  113.             add_matrix(p, q, split_index));
  114.         vector<vector<int> > result_matrix_10(
  115.             add_matrix(r, s, split_index));
  116.         vector<vector<int> > result_matrix_11(add_matrix(
  117.             add_matrix(add_matrix(t, p, split_index), r,
  118.                        split_index, -1),
  119.             v, split_index, -1));
  120.  
  121.         for (auto i = 0; i < split_index; i++)
  122.             for (auto j = 0; j < split_index; j++) {
  123.                 result_matrix[i][j]
  124.                     = result_matrix_00[i][j];
  125.                 result_matrix[i][j + split_index]
  126.                     = result_matrix_01[i][j];
  127.                 result_matrix[split_index + i][j]
  128.                     = result_matrix_10[i][j];
  129.                 result_matrix[i + split_index]
  130.                              [j + split_index]
  131.                     = result_matrix_11[i][j];
  132.             }
  133.  
  134.         a00.clear();
  135.         a01.clear();
  136.         a10.clear();
  137.         a11.clear();
  138.         b00.clear();
  139.         b01.clear();
  140.         b10.clear();
  141.         b11.clear();
  142.         p.clear();
  143.         q.clear();
  144.         r.clear();
  145.         s.clear();
  146.         t.clear();
  147.         u.clear();
  148.         v.clear();
  149.         result_matrix_00.clear();
  150.         result_matrix_01.clear();
  151.         result_matrix_10.clear();
  152.         result_matrix_11.clear();
  153.     }
  154.     return result_matrix;
  155. }
  156.  
  157. int main()
  158. {
  159.     vector<vector<int> > matrix_A = { { 1, 1, 1, 1 },
  160.                                       { 2, 2, 2, 2 },
  161.                                       { 3, 3, 3, 3 },
  162.                                       { 2, 2, 2, 2 } };
  163.  
  164.     print("Array A", matrix_A, 0, 0, ROW_1 - 1, COL_1 - 1);
  165.  
  166.     vector<vector<int> > matrix_B = { { 1, 1, 1, 1 },
  167.                                       { 2, 2, 2, 2 },
  168.                                       { 3, 3, 3, 3 },
  169.                                       { 2, 2, 2, 2 } };
  170.  
  171.     print("Array B", matrix_B, 0, 0, ROW_2 - 1, COL_2 - 1);
  172.  
  173.     vector<vector<int> > result_matrix(
  174.         multiply_matrix(matrix_A, matrix_B));
  175.  
  176.     print("Result Array", result_matrix, 0, 0, ROW_1 - 1,
  177.           COL_2 - 1);
  178. }
  179.  
  180. // Time Complexity: T(N) = 7T(N/2) +  O(N^2) => O(N^Log7)
  181. // which is approximately O(N^2.8074) Code Contributed By:
  182. // lucasletum
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Array A =>
         1         1         1         1
         2         2         2         2
         3         3         3         3
         2         2         2         2


Array B =>
         1         1         1         1
         2         2         2         2
         3         3         3         3
         2         2         2         2


Result Array =>
         8         8         8         8
        16        16        16        16
        24        24        24        24
        16        16        16        16
https://ideone.com/Kwl5Zo
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!