this week will pay attention toe two main problems off multiplication, multiplication, off numbers and multiplication off matrices. And we have already studied multiplication from the point of view off circuit complexity. So we have designed circuits that are able toe multiply numbers in the binary representation for n beats numbers. We had circuits of depth beagle off logarithm often end. The complexity with circuit was quadratic, so the number off gates was big. Go off and squared. Now this week will study the complexity on a software model on RAM Model. Will not talk about gates and circuits and wiring these gates. We'll talk about like, standard organism. You can assume that piece of Britain is written in standard programming language, but we are counting each operation on beats off input numbers. This is called the study of bit complexity. So we start with bit complexity off multiplication for feature numbers. So take two numbers given in their binary form A and B. Both of these representations are in binary. Now, if we use just standard schoolbook method for multiplying these two numbers, we just take the first of them and multiply by the right most beats off the second number. So we get large string off beats like this. Now we multiply the first number by the next piece, off the second number and so on so that we get a letter off numbers that we off course spread from the right with zeros and we then add them up. But actually, the bit complexity is already spoiled by this part. So just to computes and to consider ALS, these pair wise products conjunctions off beats, we spare quadratic complexity. So we have theta off n squared operations here already at this step. Before, we even tried to add these numbers when we talked about circuit complexity of multiplication off numbers. It was not a great deal that we had these end squared operations here, because all these conjunctions can be computed at once in a single layer of the circuit. And so this takes like one unit of time. But now we turned the model when each operation counts on its own. So it either corresponds toe the size of the circuit, were corresponds to just the program running on a single traded processor. So we'll try to do it better than with Titone offense squared operations So let's try divide and conquer approach here one of the standard approaches in computer science and see what it can do for us here. The simplest way that we can try toe to apply, divide and conquer is to divide each of the numbers that we have in two halfs. We say that a really consists off two halfs off this binary representation from a N minus one through a and over to and then a and over two minus one. Through is you. And these two halves correspond to two numbers in binary notation. The one a one, The seconds will be a zero. So each of these numbers is zero and a one is a nun over to beat number. Now the same we do with number be So we divide. It's binary imitation into two halves, and we call the number which corresponds to the first half by be one and the number corresponding to the second half by B zero Everything decree, we can now express a through a zero and a one as a zero plus two to the power off and over to a one, and the same goes for B. We see that we do not place any floor function on silly function on over to. And indeed, we can assume that is just the power of to so that we can divide and by two and recursive Lee proceeds with division on any level. That would like because if our numbers A and B have length, which is between powers of to say to to end and to toe m plus one, then we can always paired our numbers with zeros so considered just numbers like this. And the length of these numbers would be too, to the power of and plus one. So if we don't notice by. Capital n now this capital and will be the power of to and if we get any bound on the time complexity off our over it in the number of beat operations for multiplying these numbers. So if we get, say, the bound like Tee Off N is Big O Capital and to the power of C, where C is some constant, then tee off n is be go off to end to the power of C because we know that's capital and is less than to end. And this, in the end, is just the same as big go off and to the power of C. So it doesn't matter with what numbers toe work with general kind of numbers work with just numbers that our powers of two. And we'll assume what is more convenient for us so that we have already paid it our A and B so that their length is the power of to. So now let's try to employ, divide and conquer and express the product off A and B through these numbers through the parts of A and P. So we see that the product off N B is a zero times B zero plus to to the power and over two times a zero B one plus a one B zero plus two to the power of N a one B one. So we see that we have some number off editions. Also, we have multiplication by some power of two, but there's just playing right with zeros. So this operation is not a decent multiplication, and the number of actual multiplication off numbers that we need to do here is for so we need toe perform. These for multiplication is compute these products. Thus, we can express the bond for our complexity of the algorithm for N as four times the complexity off multiplying and over two bit numbers. Because each of these products is a product off and over two big numbers and plus B go off end because addition, subtraction can be done in linear time. We have already considered circuits for the circuit complexity, but all that can be easily translated in tow. Standard Albritton bit complexity. Unfortunately for this kind off bones, the master theory allows us to unroll it on Lee S t o f m. As we go off end to the power off log to four. So these two comes from here. This is the size of our sub task. And these four comes from here. The number off the sub tasks that we recursive Lee So using our Great. So this is just quadratic complexity again. So, actually, for now, divided conquer was of no use. We've got the same quadratic complexity as we did using just schoolbook method. But at least we see where we can improve. So if we like so fruitfully use divide and conquer approach in here. We cannot improve this guy. But we can try to improve this guy and try to place, say three instead of four. And to do so, we need to improve it here. So we do not need to compute four products off over to get numbers. We have somehow to compute just three such products. Now, the idea off Kurds up and Hoffman was precisely this one. The idea was to compute a zero times B zero to compute a one times be one and then to compute this guy as a whole by means of the falling formula A zero plus a one times zero plus B one and minus what we already have. Computers zero times, B zero and minus a one times be one Soto computer All the ingredients of the formula. We need one to products and three products. All the other things Here are additions, sub directions, which we already know how toe perform in linear time. The only detail here is that this is the product not exactly off over to get numbers, but these numbers is zero plus a one and B zero plus B one are actually an over two plus one bit numbers because we could have carried while adding these numbers into the most significant beat. But if we write down these sums is se see Capital C where this guy is a binary number off over two bits and this is additional bits that can happen here. And if we write down this number as de capital de again where Capital D is a binary number with exactly in order to bits, we can see that we can multiply these two numbers like this. See capital C times de capital de two to the power of N c. D. These air This is just a product of two bits credit properly plus to to the power and over to see times D plus d times, capital C and plus C times t So this is, product off too, and over to get numbers. So we need t off over to operations to compute it. Now this is a product off a single beat by a number. This is also a product of a single bit by a number. This is just reading. This is one did spread it properly. We have addition here, so everything that we have here is doable in big goal off sometime. So in the end, this thing can be computed in tee off over two plus b go off any time. This thing can be computed in tee off over two time as well as a zero times B zero, and we indeed have just three records of calls to our algorithm, plus some time, which is linear on end. And in the end, indeed, Master Theory will tell us that's the time complexity off our algorithm Tee off is big go off and to the power of Look 23 which is South quadratic. Now the question is, can we further improve that? So can we split our numbers into three parts of four parts and then, using some clever formulas, can recombine these parts so that we get all the ingredients to construct the product of the numbers? And indeed, we can do so and we'll learn that while discussing Tom's or Britain. So actually, this exponents that we have here can be made as close toe one as needed off course at the expense off very large, constant in this big O, so these organisms tend to be not very practical, but theoretically it's doable, and we'll learn how to do it a bit later. Now we'll discuss as our next application off this idea and divide and conquer the matrix multiplication. Our first algorithm were working with matrices
