fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <chrono>
  4. using namespace std;
  5. using namespace chrono;
  6.  
  7. // Threshold for switching to the naive method (selected experimentally)
  8. const int THRESHOLD = 1;
  9.  
  10. // Function to print the matrix
  11. void printMatrix(const vector<vector<int>>& matrix) {
  12.     int n = (int) matrix.size();
  13.     int m = (int) matrix[0].size();
  14.  
  15.     // Set the limits for rows and columns to be displayed
  16.     int maxRows = min(n, 4); // Display up to 4 rows
  17.     int maxCols = min(m, 4); // Display up to 4 columns
  18.  
  19.     for (int i = 0; i < maxRows; i++) {
  20.         for (int j = 0; j < maxCols; j++) {
  21.             cout << matrix[i][j] << " ";
  22.         }
  23.  
  24.         // If there are more columns, indicate there are more
  25.         if (m > maxCols) {
  26.             cout << "...";
  27.         }
  28.  
  29.         cout << endl;
  30.     }
  31.  
  32.     // If there are more rows, indicate that there are more
  33.     if (n > maxRows) {
  34.         cout << "..." << endl;
  35.     }
  36. }
  37.  
  38. // Naive matrix multiplication for small matrices
  39. vector<vector<int>> naiveMultiply(const vector<vector<int>>& A, const vector<vector<int>>& B) {
  40.     int n = (int) A.size();
  41.     vector<vector<int>> C(n, vector<int>(n, 0));
  42.     for (int i = 0; i < n; i++) {
  43.         for (int j = 0; j < n; j++) {
  44.             for (int k = 0; k < n; k++) {
  45.                 C[i][j] += A[i][k] * B[k][j];
  46.             }
  47.         }
  48.     }
  49.  
  50.     return C;
  51. }
  52.  
  53. // Function to add two matrices
  54. vector<vector<int>> add(const vector<vector<int>>& A, const vector<vector<int>>& B) {
  55.     int n = (int) A.size();
  56.     vector<vector<int>> result(n, vector<int>(n));
  57.     for (int i = 0; i < n; i++) {
  58.         for (int j = 0; j < n; j++) {
  59.             result[i][j] = A[i][j] + B[i][j];
  60.         }
  61.     }
  62.  
  63.     return result;
  64. }
  65.  
  66. // Function to subtract two matrices
  67. vector<vector<int>> subtract(const vector<vector<int>>& A, const vector<vector<int>>& B) {
  68.     int n = (int) A.size();
  69.     vector<vector<int>> result(n, vector<int>(n));
  70.     for (int i = 0; i < n; i++) {
  71.         for (int j = 0; j < n; j++) {
  72.             result[i][j] = A[i][j] - B[i][j];
  73.         }
  74.     }
  75.  
  76.     return result;
  77. }
  78.  
  79. // Function to split a matrix into 4 submatrices
  80. void splitMatrix(const vector<vector<int>>& original, vector<vector<int>>& A11, vector<vector<int>>& A12,
  81.                  vector<vector<int>>& A21, vector<vector<int>>& A22) {
  82.     int newSize = (int) (original.size() / 2);
  83.     for (int i = 0; i < newSize; i++) {
  84.         for (int j = 0; j < newSize; j++) {
  85.             A11[i][j] = original[i][j];
  86.             A12[i][j] = original[i][j + newSize];
  87.             A21[i][j] = original[i + newSize][j];
  88.             A22[i][j] = original[i + newSize][j + newSize];
  89.         }
  90.     }
  91. }
  92.  
  93. // Function to join 4 submatrices into a matrix
  94. void joinMatrices(const vector<vector<int>>& A11, const vector<vector<int>>& A12,
  95.                   const vector<vector<int>>& A21, const vector<vector<int>>& A22,
  96.                   vector<vector<int>>& result) {
  97.     int newSize = (int) A11.size();
  98.     for (int i = 0; i < newSize; i++) {
  99.         for (int j = 0; j < newSize; j++) {
  100.             result[i][j] = A11[i][j];
  101.             result[i][j + newSize] = A12[i][j];
  102.             result[i + newSize][j] = A21[i][j];
  103.             result[i + newSize][j + newSize] = A22[i][j];
  104.         }
  105.     }
  106. }
  107.  
  108. // Hybrid Strassen's matrix multiplication function
  109. vector<vector<int>> strassenMultiply(const vector<vector<int>>& A, const vector<vector<int>>& B) {
  110.     int n = (int) A.size();
  111.  
  112.     // Base case: Use the naive method for small matrices
  113.     if (n <= THRESHOLD) {
  114.         return naiveMultiply(A, B);
  115.     }
  116.  
  117.     // Splitting matrices into submatrices
  118.     int newSize = n / 2;
  119.     vector<vector<int>> A11(newSize, vector<int>(newSize));
  120.     vector<vector<int>> A12(newSize, vector<int>(newSize));
  121.     vector<vector<int>> A21(newSize, vector<int>(newSize));
  122.     vector<vector<int>> A22(newSize, vector<int>(newSize));
  123.     vector<vector<int>> B11(newSize, vector<int>(newSize));
  124.     vector<vector<int>> B12(newSize, vector<int>(newSize));
  125.     vector<vector<int>> B21(newSize, vector<int>(newSize));
  126.     vector<vector<int>> B22(newSize, vector<int>(newSize));
  127.  
  128.     splitMatrix(A, A11, A12, A21, A22);
  129.     splitMatrix(B, B11, B12, B21, B22);
  130.  
  131.     // Computing the 7 products using Strassen's method
  132.     vector<vector<int>> M1 = strassenMultiply(add(A11, A22), add(B11, B22));
  133.     vector<vector<int>> M2 = strassenMultiply(add(A21, A22), B11);
  134.     vector<vector<int>> M3 = strassenMultiply(A11, subtract(B12, B22));
  135.     vector<vector<int>> M4 = strassenMultiply(A22, subtract(B21, B11));
  136.     vector<vector<int>> M5 = strassenMultiply(add(A11, A12), B22);
  137.     vector<vector<int>> M6 = strassenMultiply(subtract(A21, A11), add(B11, B12));
  138.     vector<vector<int>> M7 = strassenMultiply(subtract(A12, A22), add(B21, B22));
  139.  
  140.     // Calculating C submatrices
  141.     vector<vector<int>> C11 = add(subtract(add(M1, M4), M5), M7);
  142.     vector<vector<int>> C12 = add(M3, M5);
  143.     vector<vector<int>> C21 = add(M2, M4);
  144.     vector<vector<int>> C22 = add(subtract(add(M1, M3), M2), M6);
  145.  
  146.     // Joining the 4 submatrices into the result matrix
  147.     vector<vector<int>> C(n, vector<int>(n));
  148.     joinMatrices(C11, C12, C21, C22, C);
  149.  
  150.     return C;
  151. }
  152.  
  153. // Function to measure execution time
  154. void measureExecutionTime(const string& name, vector<vector<int>> (*multiplyFunc)(const vector<vector<int>>&, const vector<vector<int>>&), const vector<vector<int>>& A, const vector<vector<int>>& B) {
  155.     auto start = high_resolution_clock::now();
  156.     vector<vector<int>> C = multiplyFunc(A, B);
  157.     auto end = high_resolution_clock::now();
  158.     auto duration = duration_cast<milliseconds>(end - start).count();
  159.     cout << endl << name << " took " << (duration/1000.0) << " seconds.\n";
  160.  
  161.     cout << "Result Matrix C:" << endl;
  162.     printMatrix(C);
  163.  
  164. }
  165.  
  166. int main() {
  167.     int n = 4; // Example size, should be a power of 2 for simplicity when using Strassen's method
  168.     vector<vector<int>> A(n, vector<int>(n, 1));
  169.     vector<vector<int>> B(n, vector<int>(n, 1));
  170.  
  171.     A[3][0] = 0;
  172.     A[3][1] = 0;
  173.     A[3][2] = 0;
  174.     A[3][3] = 0;
  175.  
  176.     A[0][3] = 0;
  177.     A[1][3] = 0;
  178.     A[2][3] = 0;
  179.     A[3][3] = 0;
  180.  
  181.     B[3][0] = 0;
  182.     B[3][1] = 0;
  183.     B[3][2] = 0;
  184.     B[3][3] = 0;
  185.  
  186.     B[0][3] = 0;
  187.     B[1][3] = 0;
  188.     B[2][3] = 0;
  189.     B[3][3] = 0;
  190.  
  191.     cout << "Matrix A:" << endl;
  192.     printMatrix(A);
  193.  
  194.     cout << endl << "Matrix B:" << endl;
  195.     printMatrix(B);
  196.  
  197.     measureExecutionTime("Naive Multiplication", naiveMultiply, A, B);
  198.     measureExecutionTime("Hybrid Multiplication", strassenMultiply, A, B);
  199.  
  200.     return 0;
  201. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Matrix A:
1 1 1 0 
1 1 1 0 
1 1 1 0 
0 0 0 0 

Matrix B:
1 1 1 0 
1 1 1 0 
1 1 1 0 
0 0 0 0 

Naive Multiplication took 0 seconds.
Result Matrix C:
3 3 3 0 
3 3 3 0 
3 3 3 0 
0 0 0 0 

Hybrid Multiplication took 0 seconds.
Result Matrix C:
3 3 3 0 
3 3 3 0 
3 3 3 0 
0 0 0 0
https://ideone.com/kXE11K
language:
C++ 4.3.2 (gcc-4.3.2)
created:
31 days ago
visibility:
secret

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!