I am trying to multiply two matrix whose order is power of 2 using strassens algorithm,The problem I am facing is,when the base case is hit, I always have to keep the base case half of the order, or else i wont work, heres my code

Code:#include <iostream> using namespace std; void Add(int **A,int **B,int **C,int n) { for(int i=0;i<n;++i) { for(int j=0;j<n;++j) C[i][j]=A[i][j]+B[i][j]; } return; } void subtract(int **A,int **B,int **C,int n) { for(int i=0;i<n;++i) { for(int j=0;j<n;++j) C[i][j]=A[i][j]-B[i][j]; } return; } void AB(int **A,int **B,int **C,int n) { for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { C[i][j]=0; for(int k=0;k<n;++k) C[i][j]+=A[i][k]*B[k][j]; } } } void strassen(int **A,int **B,int **C,int n) { /* if(n==1) { C[0][0]=A[0][0]*B[0][0]; return; } */ if(n<=2) { AB(A,B,C,n); return; } int s=n/2; int **A11=new int*[s]; int **A12=new int*[s]; int **A21=new int*[s]; int **A22=new int*[s]; int **B11=new int*[s]; int **B12=new int*[s]; int **B21=new int*[s]; int **B22=new int*[s]; int **C11=new int*[s]; int **C12=new int*[s]; int **C21=new int*[s]; int **C22=new int*[s]; for(int i=0;i<s;++i) { A11[i]=new int[s]; A12[i]=new int[s]; A21[i]=new int[s]; A22[i]=new int[s]; B11[i]=new int[s]; B12[i]=new int[s]; B21[i]=new int[s]; B22[i]=new int[s]; C11[i]=new int[s]; C12[i]=new int[s]; C21[i]=new int[s]; C22[i]=new int[s]; } for(int i=0;i<s;++i) { for(int j=0;j<s;++j) { A11[i][j]=A[i][j]; A12[i][j]=A[i][j+s]; A21[i][j]=A[i+s][j]; A22[i][j]=A[i+s][j+s]; B11[i][j]=A[i][j]; B12[i][j]=A[i][j+s]; B21[i][j]=A[i+s][j]; B22[i][j]=A[i+s][j+s]; } } int **s1=new int*[s]; int **s2=new int*[s]; int **s3=new int*[s]; int **s4=new int*[s]; int **s5=new int*[s]; int **s6=new int*[s]; int **s7=new int*[s]; int **s8=new int*[s]; int **s9=new int*[s]; int **s10=new int*[s]; int **p1=new int*[s]; int **p2=new int*[s]; int **p3=new int*[s]; int **p4=new int*[s]; int **p5=new int*[s]; int **p6=new int*[s]; int **p7=new int*[s]; for(int i=0;i<s;++i) { s1[i]=new int[s]; s2[i]=new int[s]; s3[i]=new int[s]; s4[i]=new int[s]; s5[i]=new int[s]; s6[i]=new int[s]; s7[i]=new int[s]; s8[i]=new int[s]; s9[i]=new int[s]; s10[i]=new int[s]; p1[i]=new int[s]; p2[i]=new int[s]; p3[i]=new int[s]; p4[i]=new int[s]; p5[i]=new int[s]; p6[i]=new int[s]; p7[i]=new int[s]; } subtract(B12,B22,s1,s); subtract(B21,B11,s4,s); subtract(A12,A22,s7,s); subtract(A11,B21,s9,s); Add(A11,A12,s2,s); Add(A21,A22,s3,s); Add(A11,A22,s5,s); Add(B11,B22,s6,s); Add(B21,B22,s8,s); Add(B11,B12,s10,s); strassen(A11,s1,p1,s); strassen(s2,B22,p2,s); strassen(s3,B11,p3,s); strassen(A22,s4,p4,s); strassen(s5,s6,p5,s); strassen(s7,s8,p6,s); strassen(s9,s10,p7,s); Add(p5,p4,C11,s); subtract(C11,p2,C11,s); Add(C11,p6,C11,s); Add(p1,p2,C12,s); Add(p3,p4,C21,s); Add(p5,p1,C22,s); subtract(C22,p3,C22,s); subtract(C22,p3,C22,s); for(int i=0;i<s;++i) { for(int j=0;j<s;++j) { C[i][j]=C11[i][j]; C[i][j+s]=C12[i][j]; C[i+s][j]=C21[i][j]; C[i+s][j+s]=C22[i][j]; } delete C11[i]; delete C12[i]; delete C21[i]; delete C22[i]; delete A11[i]; delete A12[i]; delete A21[i]; delete A22[i]; delete B11[i]; delete B12[i]; delete B21[i]; delete B22[i]; delete s1[i]; delete s2[i]; delete s3[i]; delete s4[i]; delete s5[i]; delete s6[i]; delete s7[i]; delete s8[i]; delete s9[i]; delete s10[i]; delete p1[i]; delete p2[i]; delete p3[i]; delete p4[i]; delete p5[i]; delete p6[i]; delete p7[i]; } delete C11; delete C12; delete C21; delete C22; delete A11; delete A12; delete A21; delete A22; delete B11; delete B12; delete B21; delete B22; delete s1; delete s2; delete s3; delete s4; delete s5; delete s6; delete s7; delete s8; delete s9; delete s10; delete p1; delete p2; delete p3; delete p4; delete p5; delete p6; delete p7; } int main() { int n; cin>>n; int **A=new int*[n],**B=new int*[n],**C=new int*[n]; for(int i=0;i<n;++i) { A[i]=new int[n]; B[i]=new int[n]; C[i]=new int[n]; } for(int i=0;i<n;++i) { for(int j=0;j<n;++j) A[i][j]=B[i][j]=C[i][j]=j+1; } strassen(A,B,C,n); for(int i=0;i<n;++i) { for(int j=0;j<n;++j) cout<<C[i][j]<<" "; cout<<endl; } for(int i=0;i<n;++i) { delete A[i]; delete B[i]; delete C[i]; } }

Now if my input matrix is n, than I must have the base case<=n/2 or else it is giving different result. Can someone help?

for convenience

Multiplication of

1 2 3 4 1 2 3 4 10 20 30 40

1 2 3 4 * 1 2 3 4= 10 20 30 40

1 2 3 4 1 2 3 4 10 20 30 40

1 2 3 4 1 2 3 4 10 20 30 40

I have followed every step of strassens algorithm.. still wrong