Video 5-5: Long Multiplication
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-10, 5:35
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 In the next section, we'll look at maybe the most fundamental problem of all the problems we look at here, just multiplying numbers. And uh it turns out there's both non-trivial algorithms that maybe you haven't seen plus uh new research results from this month or maybe October. I'm uh yeah. Uh so despite this problem being so fundamental, we still don't know the final answer and it's actively worked on and there's been some some interesting new developments uh repeatedly including from these OpenAI paper drops. So um it's literally about multiplying numbers. There's nothing special about it. I'll come back to this question. And this was uh for getting your gut feeling on how long this should take without having told you uh much about it. And um just for having this uh on the recording, here's what people have voted so far. I'm not going to comment on this further for now. Uh if you want to send something so that it's on the record, you can quickly do it. Now before we go to any fancy algorithm, uh let's see how you learned this in primary school because this everyone did this. What's the cost of multiplying two integers? Well, it clearly depends on how big the numbers are. Right? This is uh we're talking about numbers that are so large that they don't just fit in one word.
1:37 So that we have to use an actual algorithm and not just say this is a built-in multiplication operation in our uh CPU. So um the method that we used in school is called long multiplication. Uh um in binary it's actually uh even nicer to um to execute than the usual decimal version. And let me maybe show this instead of the the simple example here. So here are here are two numbers. Well 181 and 211. And let's multiply those the way you learned it in school. Well, you're going to take um the first is multiply this one multiplies with this yellow number. the 211 I have one times this number and that's what I write down and here it's already added in to the result. Then I have 0 * it's the 2 to the^ 0 * 0 times the yellow number. So I get zeros at this position shifted. I don't need to add much in for the next time. The next digit, it's a one again. So I'm multiplying this number with a one and shift it by two positions to the left. This is this number. Same number as here, just shift it.
3:12 And then you add it to the result bit by bit. I think the way you do it in school is you first fill out this table and then you do one long addition. Of course, both work is the same. You can also keep keep the running count. Whenever we have a zero, we have nothing to do. And whenever we have a one, we just add a shifted version of our other factor to the result. Right? That's what um binary numbers buy you. They make this process a little easier because you never really have to multiply this yellow number with anything. You just either copy it or leave it out. 01 and okay you can do this until the very end then you get the result. You can double check hopefully that this is correct. Uh one last addition. No this is How much time does this take? Round about like the zero columns you could argue don't take much time but you're essentially filling out something that looks a bit like a square here. And the length of side length of this square is the length of the numbers. In the example, I put I made the numbers equally long. If one is shorter, one is longer, you can fill it up with zeros.
4:32 Essentially, you need the product of the lengths of the two numbers. So, n squ if each of the inputs has n bits, right? Uh that is what we've done here. And if you want to spell out the algorithm I've shown on the slides, it's you can spell it out a bit more cleanly for uh the binary case, you can directly write to the right position. If you want to implement that, you can work out how this works. Uh but you're essentially stuck with this quadratic number of bit operations. Uh, if you care about um this little comment, you can speed things up on a word RAM by grouping W bits and doing the multiplication wordwise. If you're clever about it, you can speed things up by this uh w ^2 factor. Uh, but if n is large enough, uh, this will not really save the day. The quadratic term will still dominate.