document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=869778>Question 869778</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Lets assume that you have a CPU which takes y microseconds to add 2 floating point numbers and z microseconds to multiply 2 floating point numbers. You have an nxm matrix and an mxp matrix. What is the time taken (in microseconds) to multiply the matrices?<BR>\n" );
document.write( "a) It is not possible to multiply them.<BR>\n" );
document.write( "b) 100<BR>\n" );
document.write( "c) (m*n*p*(y-z))<BR>\n" );
document.write( "d) n*p*e^(y+z)<BR>\n" );
document.write( "e) (mz+(m-1)*y)*n*p </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #524398 by </B><A HREF=/tutors/aboutme.mpl?userid=jim_thompson5910><B>jim_thompson5910(35256)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=jim_thompson5910><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=524398\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Call the first matrix A. Matrix A is n x m. <BR>\n" );
document.write( "Call the second matrix B. Matrix B is m x p.<BR>\n" );
document.write( "Let C = A*B. Matrix C is n x p\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Matrix C is defined since you have n x m by m x p. The two 'm's match and the final size of matrix C will be n x p. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "There will be n*p elements in matrix C.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "For each element, you have to have a combination of multiplication and addition.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "To find the element in row1, column1 of matrix C, you are going to multiply m pairs of numbers (the corresponding numbers in row 1 of matrix A with column 1 of matrix B). <BR>\n" );
document.write( "So far, the CPU has taken up m*z microseconds. <BR>\n" );
document.write( "After you multiply all of those pairs of numbers, you're going to add them. You will have m-1 additions to perform (eg: if you have 10 numbers to add up, you really have 10-1 = 9 addition operations). <BR>\n" );
document.write( "Doing these m-1 operations costs you another (m-1)*y microseconds. In total, it takes m*z + (m-1)*y microseconds to calculate the result for the element in row1, column1. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "For the element in row1, column2 of matrix C, you do the same number of multiplications and additions. So you take another m*z + (m-1)*y microseconds. \r<BR>\n" );
document.write( "\n" );
document.write( "Etc etc\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "You keep doing this for each of the n*p elements in matrix C. That means you do this n*p times.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "So you'll take up a total of <font color=\"red\">(mz+(m-1)*y)*n*p</font> microseconds to multiply matrix A and matrix B to get matrix C.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This is <font color=\"red\">choice E)</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );