# Recursive matrix multiplication

Page 1 of 1

## 14 Replies - 10683 Views - Last Post: 23 January 2011 - 12:25 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=211405&amp;s=584b5448ceeca9774732631fd30d40da&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 alcantarex

Reputation: 0
• Posts: 7
• Joined: 21-January 11

# Recursive matrix multiplication

Posted 22 January 2011 - 11:35 AM

I hope that you help me please.I would need about the c++ code of the algorithm square multiply matrix recursive and not Strassen's algorithm.Can I help me ,please?

```#define index(i,j,power) (((i)<<(power))+(j))

void recMultiply(int i, int j, float a[], int k, int l, float b[], int x, int y, float c[], int s);

int i, j, k, s, matrixsize, blocksize, jj, kk, power, bsize;
float sum, maxr, total=0.0, startmult, finishmult, multtime;
float* A = NULL;
float* B = NULL;
float* C = NULL;

int main(int argc, char *argv[])
{
//functions for producing random numbers
srand(99999);
maxr = (float)RAND_MAX;

//store user parameters into variables
power = atoi( argv[1] );
bsize = atoi( argv[2] );

matrixsize = int(pow(2,power));
blocksize = int(pow(2,bsize));

cout<<"Matrix Size = 2^"<<power<<" = "<<"("<<matrixsize<<"*"<<matrixsize<<")"<<" matrix"<<endl<<endl;

A = new float[matrixsize*matrixsize];
B = new float[matrixsize*matrixsize];
C = new float[matrixsize*matrixsize];

//fill matrices A and B with pseudo-random float numbers
for (i = 0; i < matrixsize; i++)
for (j = 0; j < matrixsize; j++)
{
A[index(i,j,power)] = rand()/maxr;
B[index(i,j,power)] = rand()/maxr;
C[index(i,j,power)] = 0.0;
}

//start clock - multiplication
startmult = clock();

//call matrix multiplication function
recMultiply(0, 0, A, 0, 0, B, 0, 0, C, matrixsize);

//Stop clock - multiplication
finishmult = clock();

//Calculate time needed to execute multiplication
multtime = (finishmult-startmult)/CLOCKS_PER_SEC;

cout<<"Sum of the elements of matrix C: "<<total<<endl<<endl;

cout<<"Time for matrix multiplication: "<<multtime<<" seconds"<<endl<<endl;

cin>>s;

return 0;
}

void recMultiply(int i, int j, float a[], int k, int l, float b[], int x, int y, float c[], int s){

//recursive matrix multiplication algorithm
if (s == 2)
{

c[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0];
c[0][1]=a[0][0]*b[0][1]+a[0][1]*b[1][1];
c[1][0]=a[1][0]*b[0][0]+a[1][1]*b[1][0];
c[1][1]=a[1][0]*b[1][0]+a[1][1]*b[1][1];

}

else {

recMultiply(0, 0, a, 0, 0, b, 0, 0, c, s/2);
recMultiply(0, s/2, a, s/2, 0, b, 0, 0, c, s/2);

recMultiply(0, 0, a, 0, s/2, b, 0, s/2, c, s/2);
recMultiply(0, s/2, a, s/2, s/2, b, 0, s/2, c, s/2);

recMultiply(s/2, 0, a, 0, 0, b, s/2, 0, c, s/2);
recMultiply(s/2, s/2, a, s/2, 0, b, s/2, 0, c, s/2);

recMultiply(s/2, 0, a, 0, s/2, b, s/2, s/2, c, s/2);
recMultiply(s/2, s/2, a, s/2, s/2, b, s/2, s/2, c, s/2);

}
}

```

This code doesn't work good because for the case where the size of the matrix is two,it gives me the product between matrix correctly but when the size of the matrix is power of two doesn't work good .This code is designed only for the matrix where the size is a power of two.Can you help me?Thank you for attention
Bye Alcantarex

Is This A Good Question/Topic? 0

## Replies To: Recursive matrix multiplication

### #2 Salem_c

• void main'ers are DOOMED

Reputation: 2031
• Posts: 3,996
• Joined: 30-May 10

## Re: Recursive matrix multiplication

Posted 22 January 2011 - 12:02 PM

c[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0];
c[0][1]=a[0][0]*b[0][1]+a[0][1]*b[1][1];
c[1][0]=a[1][0]*b[0][0]+a[1][1]*b[1][0];
c[1][1]=a[1][0]*b[1][0]+a[1][1]*b[1][1];
None of your arrays are 2D arrays.

Didn't you get a whole bunch of
foo.cpp:71: error: invalid types ‘float[int]’ for array subscript
errors?

Also, you're passing a whole load of parameters (i,j,k,l,x,y) which seem to be unused.

• Saucy!

Reputation: 6219
• Posts: 23,965
• Joined: 23-August 08

## Re: Recursive matrix multiplication

Posted 22 January 2011 - 12:14 PM

Another copy/paste coder

### #4 Salem_c

• void main'ers are DOOMED

Reputation: 2031
• Posts: 3,996
• Joined: 30-May 10

## Re: Recursive matrix multiplication

Posted 22 January 2011 - 12:22 PM

Crap.
It'll soon be time for a plugin to analyse new posts and provide an automatic cross-post detection feature.

I'm sure it will free up time in the long run if we all know to avoid such selfish posters well in advance.

### #5 anonymous26

• D.I.C Lover

Reputation: 1
• Posts: 3,638
• Joined: 26-November 10

## Re: Recursive matrix multiplication

Posted 22 January 2011 - 12:26 PM

JackOfAllTrades, on 22 January 2011 - 07:14 PM, said:

How do you find this stuff?!

### #6 r.stiltskin

• D.I.C Lover

Reputation: 1833
• Posts: 4,927
• Joined: 27-December 05

## Re: Recursive matrix multiplication

Posted 22 January 2011 - 02:16 PM

ButchDean, on 22 January 2011 - 03:26 PM, said:

How do you find this stuff?!

Easy -- google. Just select a "distinctive" line of code.

### #7 anonymous26

• D.I.C Lover

Reputation: 1
• Posts: 3,638
• Joined: 26-November 10

## Re: Recursive matrix multiplication

Posted 22 January 2011 - 06:53 PM

r.stiltskin, on 22 January 2011 - 09:16 PM, said:

ButchDean, on 22 January 2011 - 03:26 PM, said:

How do you find this stuff?!

Easy -- google. Just select a "distinctive" line of code.

Makes sense!

• Saucy!

Reputation: 6219
• Posts: 23,965
• Joined: 23-August 08

## Re: Recursive matrix multiplication

Posted 23 January 2011 - 06:53 AM

It's really very simple to find these people. When someone comes and dumps a lot of fairly complicated code with an "it doesn't work", "fix this for me", or some simple error that they can't figure out, it's pretty damn obvious they got the code from somewhere and have absolutely no idea how it works.

These are the people that NEED to be weeded out of their program, not given help so they can cheat their way through school and end up at my desk during an interview unable to code a FizzBuzz program.

Here's another one that was obvious.

This post has been edited by JackOfAllTrades: 23 January 2011 - 07:27 AM

### #9 alcantarex

Reputation: 0
• Posts: 7
• Joined: 21-January 11

## Re: Recursive matrix multiplication

Posted 23 January 2011 - 10:41 AM

Hi I must implement a product between matrix with a recursive function.

of matrices, it is easier to assume that the order of the matrix is
a power of two. This restriction is relaxed later with negligible
overhead; the timing curves are smooth.
A complete matrix has index 0. A matrix at
index i is either scalar, or it is composed of four submatrices—
northwest, southwest, southeast, and northeast—each of half the
order and with indices 4i+1, 4i+2, 4i+3, and 4i+4, respectively.
The constant offset specifies the number
of interior nodes for example 5 if the size of matrix is 4. It can also be computed
directly from order:
offset=4^log order-1/3
Subtracting it from each element’s actual index yields a zero-based
indexing of just the elements in the matrix. Ignoring the offset,
this definition provides a zero-based, level-order indexing1 across
a matrix’s tree . It
prompts several observations.
Every block/subtree is indexed consecutively at each of its
levels. The scalars in any subblock, as terminal nodes at the
same level in some subtree, are therefore indexed consecutively.
A good, block-oriented algorithm, one that descends
the tree to a subtree small enough to fit in cache (for instance),
experiences excellent caching behavior without any programmers’
worries over striding. Moreover, a multilayered memory
experiences good locality simulatneously at each level of
the memory/tree, independently of the page sizes.
Where a matrix’s order is not a power of two, it is padded (as
if with zeroes) on its south and east margins to the next larger
power, but these extra elements would never be touched by a
introduces gaps into the level-order indexing, but the data in
these gaps are never touched and never migrate to cache.
a block purely of zeroes (padding) might be announced by a
flag in its parent node , from which all memory
accesses into that quadrant become unnecessary. That flag directs
the algebra around zeroes (as additive identities and multiplicative
annihilators), to yield accelerated computations on
sparse matrices. A good use for a second flag is to announce,
in contrast, that the subtree is practically dense—that it contains
no zero blocks large enough to justify the routine zero
tests that might avoid them. Instead, all matrix operations
would descend blindly to the leaves, saving the few stalls that
would result from branch instructions.
```#include <cstdlib>
#include <iostream>

using namespace std;
typedef float Scalar;
typedef struct {
int order; /* Size of the matrix */
int offset; /* Census of nonterminal nodes */
Scalar *matrix;
} Matrix;
#define nw(i) ((i << 2) + 1) /* index to Northwest quadrant of Matrix i */
#define sw(i) ((i << 2) + 2) /* index to Southwest quadrant of Matrix i */
#define se(i) ((i << 2) + 3) /* index to Southeast quadrant of Matrix i */
#define ne(i) ((i << 2) + 4) /* index to Northeast quadrant of Matrix i */

static void mult (register int i_C,Scalar* C_matrix,register int i_A,Scalar* A_matrix, register int i_B,Scalar* B_matrix) {
int offset=3;
if (i_A >= offset)
C_matrix[i_C] += A_matrix[i_A] * B_matrix[i_B];
else {
mult (nw (i_C), C_matrix, nw (i_A) , A_matrix, nw (i_B)/>, B_matrix);
mult (se (i_C), C_matrix, sw (i_A) , A_matrix, ne (i_B)/>, B_matrix);
mult (nw (i_C), C_matrix, ne (i_A) , A_matrix, sw (i_B)/>, B_matrix);
mult (ne (i_C), C_matrix, nw (i_A) , A_matrix, ne (i_B)/>, B_matrix);
mult (se (i_C), C_matrix, se (i_A) , A_matrix, se (i_B)/>, B_matrix);
mult (sw (i_C), C_matrix, sw (i_A) , A_matrix, nw (i_B)/>, B_matrix);
mult (ne (i_C), C_matrix, ne (i_A) , A_matrix, se (i_B)/>, B_matrix);
mult (sw (i_C), C_matrix, se (i_A) , A_matrix, sw (i_B)/>, B_matrix);
}
}

int main(int argc, char *argv[]){
int i,j,n;
Matrix a,b,c;

cout << "Inserire la dimensione della matrice:" <<" " ;
cin >> n;
cout << endl;
float a1[n],b1[n];

a.order=n;
b.order=n;
c.order=n;
a.offset=3;
b.offset=3;
c.offset=3;

cout << "Inserire la matrice A" << endl;
for( i=0;i<n*n;i++){

cout <<"\n a[" << i << "]=";
cin >> a1[i];
cout << endl;

}
a.matrix=a1;

for( i=0;i<n*n;i++){

cout <<"\n a[" << i <<"]=";
cout << a.matrix[i];
cout << endl;

}
cout << "Inserire la matrice B" << endl;
for( i=0;i<n*n;i++){

cout <<"\n a[" << i << "]=";
cin >> b1[i];
cout << endl;

}
b.matrix=b1;
cout << "Questo é la stampa" << endl;
for( i=0;i<n*n;i++){

cout <<"\n a[" << i <<"]=";
cout << b.matrix[i];
cout << endl;

}
for( i=0;i<n*n;i++){

c.matrix[i]=0;

}
mult (1,c.matrix, 1,a.matrix, 1,b.matrix)  ;

system("PAUSE");
return EXIT_SUCCESS;
}

```

• Saucy!

Reputation: 6219
• Posts: 23,965
• Joined: 23-August 08

## Re: Recursive matrix multiplication

Posted 23 January 2011 - 10:52 AM

So, now you're just going to copy and paste this paper (PDF)?

### #11 sk1v3r

Reputation: 231
• Posts: 668
• Joined: 06-December 10

## Re: Recursive matrix multiplication

Posted 23 January 2011 - 10:57 AM

JackOfAllTrades, you have good eyes for spotting copypastas

This post has been edited by sk1v3r: 23 January 2011 - 10:57 AM

### #12 anonymous26

• D.I.C Lover

Reputation: 1
• Posts: 3,638
• Joined: 26-November 10

## Re: Recursive matrix multiplication

Posted 23 January 2011 - 10:59 AM

And it gets him some nice kudos!

### #13 r.stiltskin

• D.I.C Lover

Reputation: 1833
• Posts: 4,927
• Joined: 27-December 05

## Re: Recursive matrix multiplication

Posted 23 January 2011 - 11:02 AM

Hilarious.

alcantarex, on 23 January 2011 - 01:41 PM, said:

Hi I must implement ...

where does it say "I must copy"?

Why don't you try writing some code of your own? Afraid you might learn something?

### #14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11447
• Posts: 43,144
• Joined: 27-December 08

## Re: Recursive matrix multiplication

Posted 23 January 2011 - 12:14 PM

### #15 anonymous26

• D.I.C Lover

Reputation: 1
• Posts: 3,638
• Joined: 26-November 10

## Re: Recursive matrix multiplication

Posted 23 January 2011 - 12:25 PM

JackOfAllTrades, on 23 January 2011 - 01:53 PM, said:

It's really very simple to find these people. When someone comes and dumps a lot of fairly complicated code with an "it doesn't work", "fix this for me", or some simple error that they can't figure out, it's pretty damn obvious they got the code from somewhere and have absolutely no idea how it works.

These are the people that NEED to be weeded out of their program, not given help so they can cheat their way through school and end up at my desk during an interview unable to code a FizzBuzz program.

Here's another one that was obvious.

FizzBuzz is a great test! The only reason why it took me just under 3 mins is because I was limited by how fast I type - the solution was immediate. There are many tests out there to test proficiency and as you can guess, copycats will not even get to sit at the desk of their new job as a software engineer. They will be weeded out long before that happens.