By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,042 Members | 998 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,042 IT Pros & Developers. It's quick & easy.

Recursive Matrix Multiplication

P: 1
Hi guys. I have a problem with writing the base case for the following matrix multiplication function I have implemented. Please help.
Expand|Select|Wrap|Line Numbers
  1. #define index(i,j,power) (((i)<<(power))+(j))
  2.  
  3. void recMultiply(int i, int j, float a[], int k, int l, float b[], int x, int y, float c[], int s);
  4.  
  5.     int i, j, k, s, matrixsize, blocksize, jj, kk, power, bsize;
  6.     float sum, maxr, total=0.0, startmult, finishmult, multtime;
  7.     float* A = NULL;
  8.     float* B = NULL;
  9.     float* C = NULL;
  10.  
  11. int main(int argc, char *argv[])
  12. {
  13.         //functions for producing random numbers
  14.     srand(99999);
  15.     maxr = (float)RAND_MAX;
  16.  
  17.         //store user parameters into variables
  18.     power = atoi( argv[1] );
  19.     bsize = atoi( argv[2] );
  20.  
  21.     matrixsize = int(pow(2,power)); 
  22.     blocksize = int(pow(2,bsize));
  23.  
  24.     cout<<"Matrix Size = 2^"<<power<<" = "<<"("<<matrixsize<<"*"<<matrixsize<<")"<<" matrix"<<endl<<endl;
  25.  
  26.        A = new float[matrixsize*matrixsize];
  27.        B = new float[matrixsize*matrixsize];
  28.        C = new float[matrixsize*matrixsize];
  29.  
  30.     //fill matrices A and B with pseudo-random float numbers
  31.     for (i = 0; i < matrixsize; i++)
  32.         for (j = 0; j < matrixsize; j++)
  33.         {
  34.             A[index(i,j,power)] = rand()/maxr;
  35.             B[index(i,j,power)] = rand()/maxr;
  36.             C[index(i,j,power)] = 0.0;
  37.         }
  38.  
  39.     //start clock - multiplication
  40.     startmult = clock();
  41.  
  42.        //call matrix multiplication function
  43.       recMultiply(0, 0, A, 0, 0, B, 0, 0, C, matrixsize);
  44.  
  45.     //Stop clock - multiplication    
  46.     finishmult = clock();
  47.  
  48.                 //Calculate time needed to execute multiplication
  49.     multtime = (finishmult-startmult)/CLOCKS_PER_SEC;
  50.  
  51.     cout<<"Sum of the elements of matrix C: "<<total<<endl<<endl;
  52.  
  53.     cout<<"Time for matrix multiplication: "<<multtime<<" seconds"<<endl<<endl;
  54.  
  55. cin>>s;
  56.  
  57.     return 0;
  58. }
  59.  
  60. void recMultiply(int i, int j, float a[], int k, int l, float b[], int x, int y, float c[], int s){
  61.  
  62.      //recursive matrix multiplication algorithm
  63.      if (s == 2) 
  64.      {
  65.  
  66. //What base case code should go here
  67.  
  68.          }
  69.  
  70.      else {
  71.  
  72.           recMultiply(0, 0, a, 0, 0, b, 0, 0, c, s/2);
  73.           recMultiply(0, s/2, a, s/2, 0, b, 0, 0, c, s/2);
  74.  
  75.           recMultiply(0, 0, a, 0, s/2, b, 0, s/2, c, s/2);
  76.           recMultiply(0, s/2, a, s/2, s/2, b, 0, s/2, c, s/2);
  77.  
  78.           recMultiply(s/2, 0, a, 0, 0, b, s/2, 0, c, s/2);
  79.           recMultiply(s/2, s/2, a, s/2, 0, b, s/2, 0, c, s/2);
  80.  
  81.           recMultiply(s/2, 0, a, 0, s/2, b, s/2, s/2, c, s/2);
  82.           recMultiply(s/2, s/2, a, s/2, s/2, b, s/2, s/2, c, s/2);
  83.  
  84.           }
  85. }
Aug 1 '08 #1
Share this Question
Share on Google+
1 Reply


sicarie
Expert Mod 2.5K+
P: 4,677
Wha'ts the problem? Is there an error message with the problem, or is it a logical issue?
Aug 2 '08 #2

Post your reply

Sign in to post your reply or Sign up for a free account.