14 Replies - 7264 Views - Last Post: 23 January 2011 - 12:25 PM Rate Topic: -----

#1 alcantarex  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1678
  • View blog
  • Posts: 3,180
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6063
  • View blog
  • Posts: 23,517
  • Joined: 23-August 08

Re: Recursive matrix multiplication

Posted 22 January 2011 - 12:14 PM

Another copy/paste coder
Was This Post Helpful? 0
  • +
  • -

#4 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1678
  • View blog
  • Posts: 3,180
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Recursive matrix multiplication

Posted 22 January 2011 - 12:26 PM

View PostJackOfAllTrades, on 22 January 2011 - 07:14 PM, said:


How do you find this stuff?! :D
Was This Post Helpful? 0
  • +
  • -

#6 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

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

Re: Recursive matrix multiplication

Posted 22 January 2011 - 02:16 PM

View PostButchDean, on 22 January 2011 - 03:26 PM, said:

How do you find this stuff?! :D

Easy -- google. Just select a "distinctive" line of code.
Was This Post Helpful? 2
  • +
  • -

#7 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Recursive matrix multiplication

Posted 22 January 2011 - 06:53 PM

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

View PostButchDean, on 22 January 2011 - 03:26 PM, said:

How do you find this stuff?! :D

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

Makes sense! :D
Was This Post Helpful? 0
  • +
  • -

#8 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6063
  • View blog
  • Posts: 23,517
  • 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

Was This Post Helpful? 1
  • +
  • -

#9 alcantarex  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.

On first reading of the definitions for the quadtree decomposition
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
good algorithm. (Interior padding is also possible.) Padding
introduces gaps into the level-order indexing, but the data in
these gaps are never touched and never migrate to cache.
Padding can be detected from the size of each quadrant, or
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;
}



I need about for your help because It is for exam.Please Bye
Was This Post Helpful? 0
  • +
  • -

#10 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6063
  • View blog
  • Posts: 23,517
  • 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)?
Was This Post Helpful? 2
  • +
  • -

#11 sk1v3r  Icon User is offline

  • D.I.C Addict

Reputation: 231
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#12 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • 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! :D
Was This Post Helpful? 0
  • +
  • -

#13 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

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

Re: Recursive matrix multiplication

Posted 23 January 2011 - 11:02 AM

Hilarious.

Quoting your own statement

View Postalcantarex, 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?
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,121
  • Joined: 27-December 08

Re: Recursive matrix multiplication

Posted 23 January 2011 - 12:14 PM

Duplicate threads merged. Please avoid duplicate posting.
Was This Post Helpful? 0
  • +
  • -

#15 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Recursive matrix multiplication

Posted 23 January 2011 - 12:25 PM

View PostJackOfAllTrades, 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1