# Thread: recursive Strassens Algorithm Problem

1. ## recursive Strassens Algorithm Problem

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);

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);

subtract(C11,p2,C11,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

2. I'm not familiar with the algorithm myself, but what I can tell you that your programming methodologies are about as unsafe and bug prone as imaginable.

(1) Never use the "new" operator unless you're assigning the result directly to the constructor of a "smart pointer" object. Note: conveniently, this will also rid you of the need for the explicit "delete" calls.
(2) Stop using arrays! std::array, std::vector, and the like aren't just safer - they're much easier to use! You won't have to manage memory, and all of the size info and such is readily accessible.
(3) Eventually you should move towards using templates instead of hard-coded data types. Just a suggestion, of course.

Also bear in mind that getting (1) and (2) down is pretty much essential if you expect anyone here to help you - few will want to wade through hundreds of lines of buggy container management code just to inspect a simple algorithm...

3. In practice, the Strasen algorithm provides only a small improvement in the number of operations, its complexity is O(N^2.807), where N is the size of the NXN matrix, instead of the usual O(N^3) operations. In practice, not only there is only a 10 % improvement in execution speed, but this is only after the matrices have size at least 1,000. Three decades ago before my sophomore year I tried to understand Strassen's algorithm, but since then I have never looked at it.

I assume that this is a homework assignment in a course, and so you are forced to complete this project, but overall you will probably never have to use this algorithm in real life, unless you are trying to improve it further as your specialty. There has been some new progress that improves the complexity to O(N^2.3727), and there are hopes that the complexity can one day be reduced to O(N^2), but I suspect that if and when this is done, it will probably require very large matrices to be effective.