[go: up one dir, main page]
Scribd
Upload
20 views4 pages

Experiment 4 Daa Lab

multiplication of two matrices

Uploaded by

Shakala Vengalreddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
20 views4 pages

Experiment 4 Daa Lab

multiplication of two matrices

Uploaded by

Shakala Vengalreddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Experiment 4

Aim-: Write a program for multiplication of two matrices using strassen's matrix multiplication
algorithm
Code-:
#include <stdio.h>
#include <stdlib.h>
// Function to add two matrices
void add(int n, int A[n][n], int B[n][n], int C[n][n]) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] + B[i][j];
}
// Function to subtract two matrices
void subtract(int n, int A[n][n], int B[n][n], int C[n][n]) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] - B[i][j];
}
// Function to implement Strassen's algorithm
void strassen(int n, int A[n][n], int B[n][n], int C[n][n]) {
if (n == 1) {
C[0][0] = A[0][0] * B[0][0];
return;

int mid = n / 2;
int A11[mid][mid], A12[mid][mid], A21[mid][mid], A22[mid][mid];
int B11[mid][mid], B12[mid][mid], B21[mid][mid], B22[mid][mid];
int C11[mid][mid], C12[mid][mid], C21[mid][mid], C22[mid][mid];
int P1[mid][mid], P2[mid][mid], P3[mid][mid], P4[mid][mid], P5[mid][mid], P6[mid][mid],
P7[mid][mid];
int temp1[mid][mid], temp2[mid][mid];
// Dividing matrices into sub-matrices
for (int i = 0; i < mid; i++) {
for (int j = 0; j < mid; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + mid];
A21[i][j] = A[i + mid][j];
A22[i][j] = A[i + mid][j + mid];

B11[i][j] = B[i][j];
B12[i][j] = B[i][j + mid];
B21[i][j] = B[i + mid][j];
B22[i][j] = B[i + mid][j + mid];
}
}

// Calculating P1 to P7
add(mid, A11, A22, temp1);
add(mid, B11, B22, temp2);
strassen(mid, temp1, temp2, P1);

add(mid, A21, A22, temp1);


strassen(mid, temp1, B11, P2);

subtract(mid, B12, B22, temp1);


strassen(mid, A11, temp1, P3);

subtract(mid, B21, B11, temp1);


strassen(mid, A22, temp1, P4);

add(mid, A11, A12, temp1);


strassen(mid, temp1, B22, P5);
subtract(mid, A21, A11, temp1);
add(mid, B11, B12, temp2);
strassen(mid, temp1, temp2, P6);

subtract(mid, A12, A22, temp1);


add(mid, B21, B22, temp2);
strassen(mid, temp1, temp2, P7);

// Calculating C11, C12, C21, C22


add(mid, P1, P4, temp1);
subtract(mid, temp1, P5, temp2);
add(mid, temp2, P7, C11);

add(mid, P3, P5, C12);

add(mid, P2, P4, C21);

add(mid, P1, P3, temp1);


subtract(mid, temp1, P2, temp2);
add(mid, temp2, P6, C22);

// Combining sub-matrices into result matrix C


for (int i = 0; i < mid; i++) {
for (int j = 0; j < mid; j++) {
C[i][j] = C11[i][j];
C[i][j + mid] = C12[i][j];
C[i + mid][j] = C21[i][j];
C[i + mid][j + mid] = C22[i][j];
}
}
}
// Function to print a matrix
void printMatrix(int n, int matrix[n][n]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int n = 2; // Size of the matrix (must be a power of 2)
int A[2][2] = {{1, 2}, {3, 4}};
int B[2][2] = {{5, 6}, {7, 8}};
int C[2][2];
strassen(n, A, B, C);

printf("Result matrix:\n");
printMatrix(n, C);

return 0;
}

You might also like