Video 5-6: Fast Multiplication
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-16, 34:27
The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.
0:03 Where we left off last time is the the long multiplication, the uh primary school version of multiplying to integers given as a binary representation. And just from this picture uh I hope you remember that essentially copy this number the first factor put it at the corresponding position below the one um below the second uh factor the the digits of the second factor. If I have a zero I am I might put the zeros but you might also put just nothing. uh for all the ones you have a copy of the first factor shifted so that it aligns with the corresponding digit and then at the end you just sum all these numbers up. That's how we do multiplication right digit by digit or bit by bit. Um again a bit more compactly written as this code but my point is not that you understand this code deeply. Multiplication this way isn't very complicated. The question is we're learning a new divine uh design principle for algorithms divide and conquer. So let's divide and conquer whatever uh moves.
1:15 Maybe we can do divide and conquer multiplication. So let's try that. Um and we'll assume here that n is a power of two which means um n was the number of bits not the size of the number but the number of bits in the numbers. Uh so if the number of bits is not a power of two, you can just fill it up with uh leading zeros, right? Uh why why do we require this? Well, then we can uh cut the number of bits in half without rounding. So um I can write my two numbers x and y are the integers that I'm multiplying. I can write my two numbers as a first part of the uh bits the first n half bits shifted by power of two two to the n half to the to the left and then uh a2. So if you were to write the number down x as its bits it is literally just saying the first half of the bits are a1 and the second half of the bits are a2.
2:21 But as the value of the number I have to shift and add. Right? I can do the same for y. Now um how does multiplication work? Well, I can uh take the product here, plug in what I know about these numbers and uh just multiply out. Then you see how you can rewrite this uh product of two n bit numbers as several products of smaller numbers. So we make progress. Each of these products is on numbers with just half as many bits. So we can solve that recursively with some recursive algorithm. And uh then stitch together the result as given by this formula. Right? I have all these four different smaller products and the remainder is it looks like a fancy calculation but really it's it's addition which is much cheaper than multiplication. It's just linear than length of the numbers and I have to use shifts. The multiplication with powers of two also looks like it's a an expensive operation but of course it isn't. This is just a shift to the left.
3:34 So by um you know arranging um a1 b1 shifted left by uh 2 to the n. Then these two they would be roughly the same length.
4:09 and then this A2 B2. Um I'm basically combining the numbers here. It it looks like they cannot possibly interact, but there's carries. The product of two numbers might slightly be might be slightly bigger.
4:24 In actual fact, I mean it doubles in length. So what I draw here is a bit misleading. It's rather looking like they have an overlap here.
4:45 Okay, picture is a bit messy now. I think the picture should rather be something like this. Okay. Uh the point is outside of these four multiplications, the red ones, I'm only spending a linear number of bit operations. uh whereas previously if you think about what we do here this is clearly a quadratic number of bit operations so the multiplications completely dwarf the effort we have here so I might as well ignore this part or pretend that it's it's way cheaper so if we can somehow um make these multiplications faster then we win so let's analyze this algorithm um it is essentially one of Our master theorem cases we have initially n bits. Now we reduce it to four subpros of half the size and we have a recombination cost conquer cost of linear number of bits. Now sadly um this doesn't seem to help because it's an instance of of the case one. I would compute our our lumber and so we would have to compare the toll function with n^ squ this is of course just two. So we would compare theta n versus n^2. So the um number of leaves wins and that's the case one. So we uh just get n^2 as the overall solution. Duh. This helped nothing, right? We're back to where we started.
6:22 So, it seems um it seems like this was useless. It taught us one thing, though. It taught us that we might as well make this conquer step much more expensive. Uh this this part is kind of very cheap and dominated entirely by the number of small recursive calls at the bottom. We could have spent a lot more time at this uh topmost step and it wouldn't even show up in the asmtoic cost. So maybe we can do a bit more in the conquer step. But what can we do that is is useful that's maybe less clear. Okay, again our product just from before. Let's do some uh creative rewriting. Let's this is the kind of clever magic insight that Karat Zuba had as an undergrad student and um stunned his teachers at the time. How he came up with this is a bit less less clear I think is um is not well known. So suppose you um arbitrarily compute this product a1 plus a2 b1 plus b2. Note that this is this is not x * y.
7:38 This needs to shift. X and Y were this. I'm just forgetting the shift here. I can still define this of course and and uh compute what I get. And now notice that somehow magically what appears here in the middle is this term that we need here. So this middle term two of the products turns out to be the C if I subtract the outer two terms. And it happens that the outer two terms are the other recursive products. So I need those anyways. It all falls conveniently into place that with three recursive multiplications. The third will be this from the C. I seem to get the same job done just by um cleverly stitching the parts together. And um so now I have suddenly three recursive calls with almost no extra effort. A bit more I need I need to subtract here. So well for the algebraically inclined you can only do this if you have a subtraction. You cannot do it in some more abstract uh structures. But let's not worry about that here.
8:54 So you can do a recursive method like this. I'll show you some some animation soon. um you have the two numbers as input. There's a boundary case. If if the numbers are too short, then you just do it via this the primary school method. And otherwise, you compute the left and right halves of the two numbers. Again, this looks like an expensive computation, but it's just taking bit shifts. you compute three recursive products. The the first, the last and then this this weird uh definition C uh where you subtract the first two and that is this middle part and then the result can be stitched together like this.
9:48 So let me first show um this part. So what you see here is the final state when you return from the recursive calls and so you have computed this the input x and y two binary numbers and uh you have already computed these recursive calls. C1 was the product of the highermost bits. That's these blue ones. they're already shifted to the position where they belong. You've computed the green part that were the was the the least significant bits from the two inputs. And then this magenta part is what you get from this weird multiplication and subtracting these first two. That's this purple part. And that is shifted by by half as many bits by n half. And so you have these these three subproducts that you now add together and you get the final product. If you're good at mental maths, maybe you can check that this is indeed correct. Okay. U if you want to see this in action, let me run it here with the same inputs.
10:53 And it it is a bit confusing because it's a recursive algorithm. So you what you see here is the recursion tree. Uh each step has three child recursive calls, right? for the C1, C2, and then this combination, the purple part. As you can see, the purple part is always a tiny bit more expensive because the numbers are a tiny bit longer. Uh, but not to the extent that it makes the overall asmtoic difference. And yeah, here you see which recursive calls we're currently in. As much as I like this visualization, I feel it's uh too many moving parts. But what what's going on is always just this calculation. So the cleverness only resides in somehow rearranging the product that we want to compute and observing that there's a shortcut by computing something different recursively and then subtracting things off. You turn two multiplications into one.
12:06 uh there's there's a few corner cases if you care about precisely what happens when n is not a power of two and so on. Uh so the real implementations need to take care of bits uh of this part. Uh for us we'll we'll just define it away. How good is this algorithm though? Let's analyze this as well. The non-recursive part is kind of the same as before. The constant factors are a bit worse. we do a bit more of of these subtractions but it remains linear number of bit operations. Uh all the numbers that are involved in these operations have roughly n bits. So the conquer cost in the notation remains the same and the analysis is also almost the same except that we have a three here. We have only three recursive calls. Now uh the master theorem case stays the same but now it's log to the uh n to the log base 2 of three and um that's roughly this n to the 1.585 way cheaper than quadratic.
13:16 Now uh this is for large n there is a little bit of an overhead that you get from this recursion because uh you need to have some some recursive stack and so on whereas the previous was just two nested loops. Two nested loops are very quick. Uh this has some overhead but there's a threshold um from a certain number of of length of the certain number of bits in the in the integers. It's worth using carduba in practice. I think at the point where so the sizes of cryptographic operations a few thousand digits is enough so that carduba plays pays off.
14:07 Uh if you don't want to cheat with the powers of two length that's what I mentioned. Um, I don't I don't want you to know this really. It's just uh if if you if you worry about that I lied a bit by saying the numbers have n bits, it's true I lied a bit especially here these uh that last recursive call is slightly bigger. You can fix this in a principled way if your car is on the slides.
14:40 The history of of integer multiplication is somewhat interesting. Um maybe people from probability know Colgorov famous mathematician at the time and uh he thought this is best possible to essentially do this this primary school method and he was proven wrong by Karatuba when he was a student in in his uh university very young and he somehow was courageous enough to stand up to Kogorov. So um be inspired by that if you wish. Now the question is can you push this further? And the answer is yes. Uh by breaking the numbers into more parts and trying more clever recombinations uh you can do a little bit further a little bit better still. But all of this is kind of completely put in the shade by fast for transform methods. So a completely different approach to evaluating numbers. Uh again if you want to read about this um it's it's a bit beyond the scope for the lecture even though it's a very cool and very influential algorithm.
15:49 uh the fast fiery transform essentially says let's reinterpret the multiplication of numbers as a multiplication of polomials and uh in the space of polomials I can do an operation that corresponds to the multiplication I'm not going to really do it as terms instead I'm going to evaluate the resulting polomial at certain points and then just compute the coefficients which is then the number is very clever and many many intricate details So again um you don't need to know about this but I think it's it's important for you to know that this exists and fast fury transform gets you near linear time for multiplication somewhat easily. I mean in a way that is is um efficient in practice.
16:44 It was also long conjectured that essentially what you get from basier transform. So this FFT on its own would be essentially n login bit operations. There's this log login which the actual algorithm needed for a long time. Uh forget about that for the moment. But um long it was conjectured that surely this n login is a lower bound. You cannot do better than that. But that turns out to be probably false. Uh I mean this is one of those uh papers. I'm not sure how thoroughly it has been checked and it's only a month old. Um but it claims that you can do it with a little bit of a smaller exponent on the log. Very unlikely that this is practically an improvement. But of course it means that this conjecture is not true. very exciting times and this is just multiplying numbers. We thought we understand that right?
17:56 time to wake up uh the crowd in the room. So another type of multiplication and if you're clever you can just do this by uh uh eliminating choices.
18:56 Anyone still busy? Probably not. So, uh, all of you figured out that that's the product. I don't know how you approached it. Uh, was there a shortcut you took? You can also just grind through. I was looking at, you know, um, this this entry in the top right, which there was a lot of zeros. Zeros multiplic multiplying with zeros. I can do. So if you put this vector on top of this vector, then there's the three from there and the zeros give you zero. So it has to be D. Uh okay, if you remember how matrix multiplication works, this is easy. And of course that's what I wanted to check. People remember what matrix multiplication is like. Uh I guess in the until a couple of years ago, you would have said ah very foundational problem matrix multiplication. Uh, of course we need this because of course we need this. Now I can say matrix multiplication is behind a lot of machine learning. So of course we need this. Um, mostly sparse there but okay forget about it. Um, it is driving a lot of the computation behind machine learning. So multiplying matrices is another fundamental problem and let's see if we can apply some dividing conquer tricks there as well.
20:20 The setup is uh two matrices square matrices n byn to keep things a bit simpler and we're interested in their product which of course I can write as the element wise um formula for for the the scala product of certain rows and and columns. Um I guess people will remember so let me leave it as that. It's it's evaluating this formula. How much does this cost if you do it in the usual way? The usual way being I have a loop over I and a loop over J because I have to fill all these CI J entries and then I have a third nested loop that evaluates this sum. Right? So I have something like uh for i from one to n for j from 1 to n and then for k from 1 to n and then essentially copy this formula there. That's all it does. So clearly that's a a triple nested sum.
21:24 So it needs uh cubic time and each of these um individual operations in there is is one multiplication and an addition. So let's treat that as constant time. Here we're counting integer multiplications. In the previous part for integer multiplications we zoomed in and said oh let's count individual bit operations. Okay, now we treat all of that as one operation and count number of integer operations to multiply matrices.
21:56 So that's the baseline. Can we do better with divide and conquer? Let's try the very same trick. We uh take our two factor matrices and just chop them up into regular sized pieces. Because these are two-dimensional objects, cutting in half is not so convenient. That leaves them lopsided. So let's cut them into quarters. Each of these quadrants is supposed to be again let's say n is a power of two. So it's an n /2 by n /2 matrix each. And I can um write the product of matrices also in terms of these. Basically you're just pretending that each of these entries is a single integer and you do you apply the usual formula for computing matrix products.
22:42 For example, I can take this upper right submatrix and of course it's going to be what I get if I take the right column and the first row and take their uh dotproduct.
22:58 So I have b12 * well not commutative. So a11 * b12 plus a12 * b22 as it's written here. Of course, the multiplications here are still matrix multiplications, but of half as big, well, in both dimensions, half as big matrices.
23:22 So surely I can do a a recursive divide and conquer approach. Instead of doing one giant matrix multiplication up here, I'm doing well, that's eight in total, small multiplications, but of half the size in two dimensions. So maybe that helps.
23:45 So uh if you set up the recurrence, our total cost is eight sub recursive calls on half as many bits each. The matrices are really squared and and half squared, but the parameter for the cost is just the the side length of the matrix, the n from here. And how much does it cost to recombine these things? That's essentially this uh matrix additions. That's um adding up n half squared matrices essentially n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n squ summations. Okay, so again if you if you're good in your mental math master theorem checking uh of course you compute this critical exponent C log base 2 of 8 otherwise known as three. And so by the very same argument as before, this is uh dominated by the tails by the by the leaves many many small sub instances essentially end to the the third many.
24:47 So this is no improvement whatsoever. Now might the same trick apply? Yes, the same trick applies. It's a bit more nasty, but some clever people found out. If you consider these seven instead of eight matrix products. Now each of the each of these is some weird recombination of matrices from the previous slide. It turns out you can write your results the four submatrices as some differences and products of these seven submatrix matrices.
25:26 Each of these seven just involves a single multiplication. The rest is just addition and and subtraction. Every addition and subtraction only involves or adding and and uh subtracting matrices which you do element wise. So these are by a by a whole factor n cheaper than the multiplications. Right? So in a in a way all of these plus and minus parts are vanishingly cheap compared to the multiplications you do the red parts. So we can all subsume them in some n squ term and um what counts is the recursive calls here. Okay.
26:09 Now checking that this indeed works out is a bit annoying. I'm not going to I'm not very motivated to do it with you. Um there's been some um Okay, first first let's first do the analysis and then a comment on the on the news there as well.
26:30 That's the conquer step. And the recurrence is the same. Just the eight gets replaced by a seven. And as before, it's still case one. It's still dominated by the leaves, but there's a bit fewer leaves. Only n to the log base 2 of seven, which turns out to be slightly less than three. Of course, slightly less than three. So again, um, for large enough matrices, it's a substantial improvement. Also in practical implementations we've seen for both integer multiplication and matrix multiplication that dividing conquer helps a bit um and you for both think that maybe these are well understood for integer multiplication I already hinted at this that's the summary again uh this line I had not on the previous slide there had been a subsequent human improvement that showed this log log login factor from shinhagrassen is not needed uh but is also now maybe um uh further improved and for matrix multiplication I don't know if it's if you can see this table it has years in the first column starting with 1969 and then every couple of years an improvement and here's uh the exponent for multiplying matrices and it's going down down down the last entry here was from 2024 before uh but there also AI has some improvement that should apply at least for our setting again essentially unreadable uh I hope someone has the motivation to really dig through this and represent it in a in a more uh digestible way the jump down. So if you if you zoom in on this table you see the the improvements there. Ah, there's even a okay an improvement not in the Wikipedia table if you care.
28:22 Another paper unrelated to this OpenAI paper drop. Uh the improvements from these were all just in the in the third, fourth, five, fifth digit whereas this went down um a substantial bit.
28:47 yet to be seen if if everything checks out there. Uh I wanted to briefly comment on how these improvements here are made. There um the last one I I don't claim to understand. The ones up to there are tweaks and twists of what I've shown you. Instead of breaking your matrix into uh four pieces that you cleverly recombine in seven instead of eight multiplications, you break them into uh smaller pieces but more of them and cleverly try to recombine these things instead. And there uh there's a lot of wiggle room and you can play with many parameters and that's where often these uh previous uh improvements came from. My understanding is they're all following a roughly similar recipe there. Question.
29:41 >> So I say again computing the omega bound. >> Uh how to get the the the omega as the running time? Um yeah good point. uh it might be that the algorithms uh add extra steps. My feeling is it's similar that it's somehow coming from from a different balance between number of subrecursive calls and their size.
30:39 >> yeah, question is about um in in practice for multiplying matrices what do you do? Uh I think it depends on the hardware and so on and how big the matrices are. I mean number one is if your matrix is very sparse as it is in some applications you want an entirely different approach. Second if it is dense if so sparse just means many entries of zero. Uh if it's essentially dense then uh on some GPU I think they essentially do a simple algorithm because it parallelizes better. Maybe still is is reasonable. Uh CPUs I think is well worth it. also for a different reason. Um the question is more dominated by how is your matrix stored in memory. There's two natural options. You can store row by row or column by column. If you think about matrix multiplication, you kind of want one by row and one by column is a bit of a problem because you're producing an output that's used further. So which one do you choose? What works better in this case is having a recursive algorithm even the one that doesn't improve the asmtoic running time has the feature that it is more local so that you access do all the operations in one submatrix first if you're a bit clever about the memory layout. So uh I think this has a bigger impact maybe for reasonably sized matrices. How do you how do you store them in memory? And how do you get it to be mostly local accesses to memory? And you can do a a recursive memory layout that follows the recursion of the algorithm rather than just rows or columns. And that seems to help. It's a bit of a moving target. I guess these these further refinements here anything with 2.3 in the beginning I don't I'm not sure if they're even implemented and they might might be essentially uh so many so big constant factors that they're not worth it for input sizes in this universe the precise the precise cutff points I don't know yeah fascinating right maybe so Here we don't know of a of a very convincing lower bound for this omega. It could be just two. Two is the lower bound because you have to write the n squ outputs but is not clear. Maybe you can push it all the way down to two.
33:12 Um it looked like not for a long time but nobody had any convincing argument. So maybe it's possible. unclear. So, I think that brings me back to this question I asked you earlier. What do you think how many bits does it take to do a n bit um multiplications and multiplying integers with n bits and let's just have the for entertainment the votes from there again that question turned out to be much more subtle than intended right now there's the the truth is probably between these two options between linear and n login if uh this AI paper is correct and so it's not even among the options for Now, all of these are correct because they're just upper bounds.