Is anyone can help for implementing strassen algorithm?

Question

0.00/5 (No votes)

See more:

i need some help me to understand these code

is someone here can to explain important module of these codes to me??

please i really need help

C++

//-------------------------------------------
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
//--------------------------------------
#define BREAK 2
#define a11 a->p[0]
#define a12 a->p[1]
#define a21 a->p[2]
#define a22 a->p[3]
#define b11 b->p[0]
#define b12 b->p[1]
#define b21 b->p[2]
#define b22 b->p[3]
#define c11 c->p[0]
#define c12 c->p[1]
#define c21 c->p[2]
#define c22 c->p[3]
#define d11 d->p[0]
#define d12 d->p[1]
#define d21 d->p[2]
#define d22 d->p[3]
//-------------------------------------------------
typedef double **matrix;
typedef union _strassen_matrix
{
    matrix d;
    union _strassen_matrix **p;
} *strassen_matrix;
//----------------------------------------------
matrix  new_matrix(int);
strassen_matrix new_strassen(int);
void normal_to_strassen(matrix, strassen_matrix, int);
void strassen_to_normal(strassen_matrix, matrix, int);
matrix  strassen_submatrix(strassen_matrix, int, int, int);
void copy_matrix(matrix, matrix, int);
void add_matrix(matrix, matrix, matrix, int);
void sub_matrix(matrix, matrix, matrix, int);
void copy_strassen(strassen_matrix, strassen_matrix, int);
void add_strassen(strassen_matrix, strassen_matrix, strassen_matrix, int);
void sub_strassen(strassen_matrix, strassen_matrix, strassen_matrix, int);
void mul_matrix(matrix, matrix, matrix, int);
void mul_strassen(strassen_matrix, strassen_matrix, strassen_matrix, strassen_matrix, int);
void print_matrix(matrix, int);
int least_power_of_two(int);

//------------------------------------------------
matrix new_matrix(int n)
{
  matrix a = (matrix) malloc(sizeof(double *) * n);
   for (int j = 0; j < n; j++)
		a[j] = (double *) malloc(sizeof(double) * n);
	return(a);
}
//------------------------------------------------
strassen_matrix new_strassen(int n)
{
    strassen_matrix	a;
    a = (strassen_matrix)malloc(sizeof(*a));
    if (n <= BREAK)
      	a->d = (matrix ) new_matrix(n);
   else
	{
		register int 	m = n/2;
      a->p = (strassen_matrix *)malloc(4*sizeof(strassen_matrix));
		a11 = new_strassen(m);
		a12 = new_strassen(m);
		a21 = new_strassen(m);
		a22 = new_strassen(m);
    }
    return a;
}
//----------------------------------------------------
matrix strassen_submatrix(strassen_matrix a,
	int i,
	int j,
	int n
)
{
	if (n <= BREAK)
			return(a->d);
	else
	{
		int cur_bit, bit_num;
		strassen_matrix cur_ptr = a;
      bit_num = least_power_of_two(n)-1;
		cur_bit = n/2;
		while (cur_bit >= BREAK)
		{
			cur_ptr = cur_ptr->p[(((j & cur_bit) | ((i & cur_bit)*2)) >> bit_num)];
			cur_bit >>= 1;
			bit_num--;
		}
		return (cur_ptr->d);
	}
}
//----------------------------------------------------------------
void normal_to_strassen(matrix a,strassen_matrix b,int n)
{
	if (n <= BREAK)
		copy_matrix(a,b->d,n);
	else
	{
		int		i,j,ii,jj;
		matrix 	sub;

		for (i=0; i<n;>		{
			for (j=0; j<n;>			{
				sub = strassen_submatrix(b,i,j,n);
				for (ii=0; ii<break;>					for (jj=0; jj<break;>								sub[ii][jj] = a[i+ii][j+jj];
         }
		}
	}
}
//------------------------------------------------------------
void strassen_to_normal(strassen_matrix a,matrix b,int n)
{
	if (n <= BREAK)
	copy_matrix(a->d,b, n);
	else
	{
	matrix 	sub;
     	for (int i=0; i<n;>		{
			for (int j=0; j<n;>			{
				sub = strassen_submatrix(a,i,j,n);
				for (int ii=0; ii<break;>			  			for (int jj=0; jj<break;>								b[i+ii][j+jj] = sub[ii][jj];
			}
		}
	}
}
//--------------------------------------------------------
void copy_matrix(matrix a,matrix b,int n)
{
  	for(int i=0; i<n;> 		for(int j=0; j<n;>				b[i][j] = a[i][j];
}
void add_matrix(matrix a,matrix b,matrix c,int n)
{
	for (int i=0; i<n;>		for (int j=0; j<n;>			c[i][j] = b[i][j] + a[i][j];
}
//-------------------------------------------------------
void sub_matrix(matrix a,matrix b,matrix c,int n)
{
 for (int i=0; i<n;>  	for (int j=0; j<n;>		c[i][j] = a[i][j] - b[i][j];
}
//-----------------------------------------------------------
void add_strassen(strassen_matrix a,strassen_matrix b,strassen_matrix c,int n)
{
	if (n <= BREAK)
			add_matrix(a->d, b->d, c->d, n);
	else
	{
		int m=n/2;
		add_strassen(a11, b11, c11, m);
		add_strassen(a12, b12, c12, m);
		add_strassen(a21, b21, c21, m);
		add_strassen(a22, b22, c22, m);
	}
}
//-----------------------------------------------------------
void sub_strassen(strassen_matrix a,strassen_matrix b,strassen_matrix c,int n)
{
	if (n <= BREAK)
	{
		sub_matrix(a->d, b->d, c->d, n);
	}
	else
	{
		int m = n/2;
		sub_strassen(a11, b11, c11, m);
		sub_strassen(a12, b12, c12, m);
		sub_strassen(a21, b21, c21, m);
		sub_strassen(a22, b22, c22, m);
	}
}
//----------------------------------------------------------
void mul_matrix(matrix 	a,matrix b,matrix c,int n)
{
	for(int i=0; i<n;>	for(int j=0; j<n;>	{
		c[i][j] = 0.0;
		for(int k=0; k<n;>     	}
}
//--------------------------------------------------------------------
void mul_strassen(strassen_matrix a,strassen_matrix b,strassen_matrix c,strassen_matrix d,int n)
{
	if (n <= BREAK) mul_matrix(a->d,b->d,c->d,n);
	else
	{
		int m = n/2;
		sub_strassen(a12, a22, d11, m);
		add_strassen(b21, b22, d12, m);
		mul_strassen(d11, d12, c11, d21, m);
		sub_strassen(a21, a11, d11, m);
		add_strassen(b11, b12, d12, m);
		mul_strassen(d11, d12, c22, d21, m);
		add_strassen(a11, a12, d11, m);
		mul_strassen(d11, b22, c12, d12, m);
		sub_strassen(c11, c12, c11, m);
		sub_strassen(b21, b11, d11, m);
		mul_strassen(a22, d11, c21, d12, m);
		add_strassen(c21, c11, c11, m);
		sub_strassen(b12, b22, d11, m);
		mul_strassen(a11, d11, d12, d21, m);
		add_strassen(d12, c12, c12, m);
		add_strassen(d12, c22, c22, m);
		add_strassen(a21, a22, d11, m);
		mul_strassen(d11, b11, d12, d21, m);
		add_strassen(d12, c21, c21, m);
		sub_strassen(c22, d12, c22, m);
		add_strassen(a11, a22, d11, m);
		add_strassen(b11, b22, d12, m);
		mul_strassen(d11, d12, d21, d22, m);
		add_strassen(d21, c11, c11, m);
		add_strassen(d21, c22, c22, m);
	}
}
//------------------------------------------------------------------
void print_matrix(matrix a,int n)
{
for(int i=0;i<n;i++)>
	{
		for(int j=0;j<n;j++)>		cout<<endl;
	}
}
//---------------------------------------------------------------------
int least_power_of_two(int n )
{
	int i = 1, k = 1;
	if (n==1) return (0);
	while ((k <<= 1) < n) i++;
	return(i);
}
//---------------------------------------------------
void readMatrix(matrix a,int n)
{
   for(int i=0; i<n;>	for(int j=0; j<n;>		cin>>a[i][j];
}
//---------------------------------------------------
void main()
{
	clrscr();
	int n;
	matrix  a1, a2;
	strassen_matrix b1, b2, b3, b4;
	cout<<"Enter Size Of Matrix(Power Of 2):\n";
	cin>>n;
	a1 = (matrix) new_matrix(n);
	a2 = (matrix) new_matrix(n);
	b1 = (strassen_matrix) new_strassen(n);
	b2 = (strassen_matrix) new_strassen(n);
	b3 = (strassen_matrix) new_strassen(n);
	b4 = (strassen_matrix) new_strassen(n);
	cout<<"Enter Matrix One\n";
	readMatrix(a1,n);
	cout<<"Enter Matrix Two\n";
	readMatrix(a2,n);
	normal_to_strassen(a1,b1,n);
	normal_to_strassen(a2,b2,n);
	mul_strassen(b1,b2,b3,b4,n);
	strassen_to_normal(b3,a2,n);
	cout<<"Result Is: \n";
	print_matrix(a2,n);
	getch();
}
</conio.h></stdlib.h></iostream.h>

Posted 9-Nov-11 22:18pm

Member 8384021

Updated 9-Nov-11 23:22pm

v2

Add a Solution

Comments

LanFanNinja 10-Nov-11 5:59am

I think in a situation like this if you have to ask what it does you are not ready for it. Check this out maybe it will help.
http://en.wikipedia.org/wiki/Strassen_algorithm

5 solutions

Solution 3

thank you very much for answering

i'm not beginner in c++ but this program is my project that i have to deliver to my doubt so i want to know every thing about these code so i can peresent it very well

but i agree with both of you it need a lot of time and effort!! and you don't have much time!

the important procedure that i want to know about are these modules :

mul_strassen ,sub_strassen,add_strassen,strassen_to_normal,normal_to_strassen,
matrix strassen_submatrix ,strassen_matrix new_strassen

just short comment about this procedure is enough for me.
i just want to know why these procedures were defined.

thanks alot

Posted 9-Nov-11 23:08pm

Member 8384021

Comments

Chandrasekharan P 10-Nov-11 5:19am

where did you get this code from? and amazingly there is not a single line of comment in this code.

Smithers-Jones 10-Nov-11 5:53am

Not an answer.
And if it's your project (which means you have developed it), how comes, somebody else has to explain it to you?

Chandrasekharan P 10-Nov-11 6:12am

It doesn't look his project.

Smithers-Jones 10-Nov-11 8:46am

Yeah, obviously it's not his project, but he says so in this (fake) solution. Thus my comment. :)

Chuck O'Toole 10-Nov-11 11:46am

when he says "project" I think we should read "assignment"

Member 8384021 10-Nov-11 9:51am

i never said i write these codes , that if i do why ask you to explain it to me????
it's my project but caz i don't had time so i search in internet and find these codes and caz of that i need someone to help me

JackDingler 10-Nov-11 11:46am

The brackets really hosed the code. It looks like parts of the 'for' loops are missing.

Further, there is an overuse of the 'new' operator and the malloc function. It may well be that this is the best way to do this. But generally an algorithm that is intended to speed up an operation, is intended to be optimized for speed. Heap functions are costly.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2011-11-09T22:24:00

"is someone here can to explain each line of code to me??"
No.

Explaining each line - even of a really trivial program, which that isn't, quite - needs a paragraph or so of text. This takes a lot of time, which we generally don't have for such mentoring.

Instead, either go to your tutor, and ask them to do it, or go back to where you got the code from, and ask them (nicely) if they could try using sensible variable names, and commenting things to a reasonable standard.

Timberbird · Accepted Answer · 2011-11-09T22:39:00

There definitely are people that CAN explain each line as you requested, but I doubt anyone WILL. You see, you paste a 250+ lines program and ask for complete explanation - that would take quite a lot of time and effort, don't you think so? People here have many other things to do, and surely can spend these several hours on something more important for them. So I'm afraid your could only get complete explanation if some bored computer science/math teacher with a lot of spare time will see your message. Which is unlikely.
This doesn't mean noone will help you, of course. Spend some effort on research yourself, read a good book on C and matrices, try to understand this program, and finally you'll come with just a handful of question people here will gladly help with.

Stefan_Lang · Accepted Answer · 2011-11-09T23:19:00

This is the Quick Answers section, and, upon posting a question, you really should read the text explaining what that means. Among other things it says your question should be short and specific. Your question is neither. Unless you considerably shorten your question and restrict yourself to asking one or a few specific questions, no one will give you the answer.

Besides, even if someone did what you ask, the code is not very good, and you would get very little useful information from it.

Consider what it really is that you need to know. We won't give you a full solution to your homework, but if you feel unable to do it by yourself, consider what it is that prevents you from doing so, and ask about that specific thing. In any case, if your question reveals that you didn't bother to put any effort into trying to understand it by yourself, then people here will at the very least be reluctant to put in the effort to answer your question. You need to want to learn, first.

JackDingler · Accepted Answer · 2011-11-10T05:30:00

Solution 5

If you want to understand how the code that implements an algorithm works, then you first need to understand the algorithm. After you've done that, then you should be able to see how the code matches up to the steps outlined in the algorithm.

Here's the Wikipedia entry on the Strassen Algorithm.
http://en.wikipedia.org/wiki/Strassen_algorithm[^]

When does your professor want to you to turn in your homework?

Posted 10-Nov-11 5:30am

JackDingler

Comments

Member 8384021 10-Nov-11 12:18pm

this monday i have to turn in my homework
really thanks for ur help

best of luck

JackDingler 10-Nov-11 12:42pm

Cool, you have time.

Have you tried working through the algorithm with pencil and paper?

Is anyone can help for implementing strassen algorithm?

5 solutions

Solution 1

Solution 2

Solution 4

Solution 5

Solution 3

Add your solution here

Preview 0