Fast Multiplication: From Grade-School Multiplication To Karatsuba's Algorithm

Key Takeaways

Selam NDT nachos are a Silla fad and multiplication Norman tomorrow is she all right I am just kidding what we're gonna learn about today is fast multiplication so if you're watching this channel you're probably watching for software engineering prep and we do a lot of algorithm stuff but I'm going to be honest this video and this topic is not going to be useful for you at all this video if you're watching for that purpose is probably just going to be for entertainment slash intrigue purposes otherwise this is completely useless for you and I'm just doing it because it's pretty famous and it matters in algorithms so what we're going to look at is how do we multiply numbers okay so give me two numbers give me Y and X so I have those numbers how do we multiply them so we're going all the way back to what we learned when we were kids and the way we learned to multiply when we were kids was not the fastest way and so how would we do this so let's do this together so we would grab one digit from the bottom number and then we'd multiply it by all the digits in the top number we grab the next one all of the ones in the top they grab the next one all the ones in the top grab the next one all of the ones in the top and I forgot to say N and remember we always define N and is supposed to be the length of each of the numbers so the numbers don't have to be the same length but we just it will consider the special case where they are the same length and we're going to have each number be length n and here n is 4 I want you to remember that we're gonna need that later so how many multiplications just happened and is four we just did one multiplication against for another multiplication is for another against four and another against four so we just did 16 multiplications how many multiplications is that well that's N squared if that's four squared multiplications so why is this algorithm bad well we're bounded to N squared or Big O bound on this is and squared can we do better that is the question we always ask in the stereotypically asked us in our interviews and okay let's think let's think like computer scientists how do we think about doing better so let's think about our asymptotic bounds I talked about asymptotic stuff all the time let's put them right there so okay that is our palette to choose from and I need to choose let me think about what I want to do so I'm sitting at N squared right now and what is the best that I can do well I can do another bound that's something like n to the 1.8 or something like that or I can go down to n log N or we can be really aggressive let's say we could do linear time well the thing is linear time seems a little too aggressive so I think the most optimal approach might be between n log N and N squared but we'll see we'll see how we do that so this brings me to my next point or the next topic how do we speed this up how do we increase the speed of our multiplication because this is fast multiplication after all it's faster than our standard algorithm so we saw that we did N squared multiplications with the grade school algorithm so why don't we try to do something different and now let's present our example again and look at it a different way okay so let's bring back our example and and it equals four I'm gonna put that up there this is very very important remember that N equals four so the the approach that we could take is we could do a divide and conquer approach so again this is this is like a famous algorithm and this is not something this is not like an interview question just just stay with me and we'll we'll see how this improves of the time so we have two numbers call this guy X call the top guy Y and what we need to do is we need to chop each in half we need to chop each into an a a b a c and a d and okay i said that let's put those off to the side and let's keep note of them and we have a a b c and d a and b is a part of x c and d is a part of y so okay we have split those sections so what i can declare is i need to reshape what i declare X why ass and what we can say is why is 10 to the N over 2 times C plus D and here's why so I want you to look at why let me put it right there for you and let me do a little splitting let me split it apart if I take the sum of these two numbers what do I get I get my original Y right I get my original Y so what we need to think about is where did that original equation come from well all I did was I took into account how much I how much my C term is shifted over from the side it's shifted by two places two is a familiar number to me remember n is four so what the ten means all the 10 means if you do 10 to the power of something times something we are shifting in a number over by that much if I do 1 times 10 I'm shifting the 1 over if I do 1 times 100 I'm shifting the 1 over 2 places so does that make sense all we're doing is decomposing the numbers we're not changing them at all so let's go back to our example and let's look at why and we said it's 10 times n over 2 we need a shifty and over 2 places over and now we multiply that by the second number see because we need to do that so we stay you know the same as our example plus the first part which is d so that's why when x follows the same pattern we do 10 to the N over 2 times a plus B so I really want you to understand what just happened because this is something we're gonna build off of later so we have these numbers sitting right here and what we need to do is we need to multiply them together so why don't we just do a simple multiplication so let's take our x + y and let's move them into one line let's do that right now and let's do foil we know how to multiply Paul polynomial quantities together or binomial quantities so let's do a multiplication let's multiply the first term in the first term we get that multiply the first term by that second term we get that multiplied the second term by the first term we get that and we multiply the last term by the last term we get that and then once we do a little simplification we finally get that equation so now we have what that equation says it says 10 to the N times AC plus 10 to the N over 2 times ad plus BC plus BD equals our original x times y so what we have here is an equation to decompose our original subproblem our original subproblem was x times y and now what we've done is we've decomposed the original sub-problem into another sub problem with four multiplications we have a times C we have a times D we have B times C we have B times D and now what we need to do is we need to look at these multiplications and analyze how much time we saved ourselves and again this is going to be recursively going downwards with our base case being what is called an atomic multiplication an atomic multiplication is signified by the mu mu sign and what it is is it is the time it takes for a fundamental multiplication operation to happen and that instead of just saying 1 we use that special sign to mean that because it would depend on the system you're on and stuff like that the hardware okay so if you're still following me we have this new formula that is our new formula for calculating the value of 2 and digit numbers multiplied together so what is the length of a the length of a is and over 2 the length of C is n over 2 the length of D is n over 2 the length of B is an over 2 and remember n is our original quantity n was 4 and this is the first level of our recursion where we split downwards and so now something we need to establish is if I am multiplying an N over 2 number by an N over 2 number what is the length of the result well the length of the result is going to be a length end number so if I have a length and over to a number and I have a length and over to C number if I multiply those together I'm going to get a length and number okay so remember we have our four multiplications right there a times C a times D B times C and B times D so these each are multiplications and that's our original equation so what we need to do is we need to realize the length of each of these multiplications because now we need to analyze how many additions happened so what we need to do is we need to look at how much time it takes to do a d-plus BC how many additions happen so a times D it's going to give us a length and number B times C is going to give us a length and number y remember a is n over 2 B is n over 2 C is n over 2 D is n over 2 those are the numbers we extracted by chopping our original n lengths number in half so the result of 8 times D is going to be length n which will be 4 at the top level and the result of B times C will be length 4 which will be at the top level as well if we're adding two lengths and numbers how many additions are we doing we're going to be doing and additions but we use a special sign we use a alpha sign to represent atomic additions the smallest additions we can do and remember this we have our atomic multiplications which is represented by the mu at MU I'm saying that wrong and the atomic additions which are represented by the Alpha so remember we're just trying to track our multiplications and additions we're doing and we're gonna see why so okay back to analyzing this for multiplication remember 1 2 3 4 recursive multiplications are going to happen to express the original x times y that guy in the middle is going to give us alpha n additions okay alpha n additions that makes sense because remember if we're adding a length n and a length n number the amount of additions we're gonna do is n times the time takes for an addition or the cost of an atomic addition so what we need to see is okay middle part alpha and thank you and now do we add the guys on the tail end and we do not and here's the reason why if we're multiplying something by 10 to the N and it is length n we are shifting a length and number over by n places so that's going to leave n zeroes so here's a here's an animation so if I had one two three four and I multiply it by ten to the four I'm always have one two three four times four zeros if I add that number to a number of length four do you see what I did right there why would I do alpha additions why would I do any additions there when I see a pattern what I can do is I can just concatenate these guys concatenate the results together and that leaves me with another quantity okay so now we're playing with two added numbers we're playing with our results from ad plus BC which took alpha end time and we're playing with our result 10 to the N AC plus BD which was the result of a concatenation so okay we have two numbers one of them is length what one of them is length 2n and one of them is linked n so how many additions are we going to do we're going to be doing another alpha n additions to combine these quantities so think about this the results from a times C is length n we push it over by four numbers so now it's length 2n it went from length for to like eight and the results from BD is length n and remember we concatenated them and now we need to think well the results from a DBC is going to be a length of n right and then if we're adding a number length to n to a number of length n the only places that will require addition will be n places so that's alpha and additions so total this algorithm is going to be performing to alpha and additions at each level of our recursion at each level so this brings me to my I now have an ability to draw a recurrence I can draw a recurrence relation to express how this function how this recursion is going to do work recursively so let's look at that recurrence right now so all the recurrences is an expression of the amount of work done in a recursive relationship and in something that you know R occurs and does work over and over so what we need to see is how many times are we going to split so what we're going to do is we're going to get two numbers of length N and what we're going to do is we're going to split them in half we're going to split each number in half yielding four and over two numbers so what we're going to be doing is we're going to be doing four multiplications remember back to our equation there are one two three four multiplications so to solve my current multiplication I'm going to have to do four more multiplications and then four more until I reach a base case when I have two single-digit numbers and then that's just an atomic multiplication so what we need to do is we need to see how do I call this function so I'm going to call this function four times I'm going to call it four times and what is the size of the input to each of those functions well bring bring my numbers back I had two lengths and numbers I chopped them in half I have four lengths and over two numbers and if I'm doing a multiplication or if I'm doing a call what I'm going to do is I'm going to be passing in two lengths and over two numbers I'm going to be passing numbers the less size of n over two so if I make another call what I'm going to be passing in is numbers the size of n over two so the size of the inputs to the recursive call is n over two because remember both of the numbers being passed to a multiplication function will be length n that's our original one but when we make a recursive call is from the chopped' numbers and the Chop two numbers are lengths and over two and if I pass to chop two numbers they'll both be lengths and over two so that's that right there and how much work is done during like inside our call when we're actually calculating the quantities in doing our additions once we get multiplication values back once we bought them out to our base case the amount of additions we just established is 2 alpha N so this is it this is the recurrence so we see that we have for the size of the next call for a multiplication going downward will be n over 2 the length of the two numbers x and y we pass in our next call will be length at over two and then what do we add that to we add that to two alpha n that is the work that we're going to be doing to combine all our results once all our callers come back to us and that is going to be the work done on this call and so this is going to be a recursive expression of the total work we're going to do and what we need to look at is a tree to make this really obvious so why don't we do that right now ok so we start with N and what did I say if I'm multiplying 2 and length the numbers I'm going to make for multiplication calls each of the calls will get n over to size X and wise so okay that's fair so I want four Forks each size of n over 2 okay so we just forked and now each of those subproblems have a size of n over 2 and they're going to fork again and what is the size of the sub problem they fork up to what is that going to be well it's going to be half of n over 2 which is n over 4 so each of these guys will have four forks and the subproblem we come at over four in size ok so now you see our recursive tree slowly going downwards and what I want you to now see is how many subproblems are each at each level so we see there's one sub problem at the top level there are four sub problems at the next level and then there's 16 sub problems at the next level and now how much work is done in each level remember in the first level we said it's going to be 2 alpha n the size of the supper we get at this level is N and then what we see is we are going to do how much work in the next level four times what and not to alpha n the size of the sub problem is now n over 2 so we're gonna have to alpha and over to okay so what is the size for the next level well we're gonna do two alpha what size of the sub problem is n over four two alpha and over four because that's the size of the input the the amount of additions are contingent on the size of the input so we're gonna do two alpha and over four okay so how do I generalize this so the way that I generalize this is don't you see how 4 to the 0 is 1 4 to the 1 is 4 4 to the 2 is 16 so let's say 4 to the I four to the I times what we're trying to generalize the work it done at every level and what we can see is the two alphas gonna stay the same because all that changes is the N and what do we see so at the first level we have n over 1 at the second level we have n over 2 at the third level we have n over four so we see a pattern well actually level 0 1 and 2 so 2 to the 0 is 1 2 to the 1 is 2 2 to the 2 is 4 so we see that we can express it as 2 to the power of something to the I to the level we're on so it becomes n over 2 to the I okay and then this should not be surprising we've already done recurrence relations in recursion trees in my merge sort video this should this shouldn't be new to us we know how to analyze a recursive tree and extract a generalization of the work done at every level and that's a generalization of the work we do at every level but there's one more thing we need to take into account we need to take into account atomic multiplications done at our base cases so how many levels are going to be in this tree so the amount of levels in this tree are going to be log n levels and again if you're not sound with logarithms I have videos on logarithms that I have other videos that talk about it the reason we have log base 2 levels in this tree is because we're cutting our input size in half every level and we can only cut our input size in half to get to a base case of one's a certain amount of times and a logarithm expresses that a logarithm tells us how many times we can chop in half and we're chopping our input size in half every level so a logarithm will give us the height of this tree and we need that value because we need to find how many atomic multiplications happen at the bottom level the amount of atomic multiplications is signified or the time for atomic multiplication the cost is signified by the MU or mu sign and what we're gonna do is it's gonna look like this so what we see here is the MU times four to the log n 4 to the what the amount of levels gives us the amount of ones in this final level why does it do that remember our generalization was 4 to the level number to give us the amount of notes level 0 4 to the 0 is 1 how many nodes do you see you see one node level 1 which is this level 4 to the 1 is 4 how many nodes do you see four notes four to the to four to the 2 you see 16 notes four to the log n the amount of levels will give us the amount of nodes in the last level and that's how logarithms help us so 4 to the log n gives us the amount of base cases and each base case will take mu its cost you'll have a time or a cost of MU or mu I keep I can't see it I don't know how it's pronounced yeah that is multiplications atomic multiplications and those are going to be how we sum our atomic additions and here's what we can do we can take this tree and we can derive a summation it's going to look like this so finally we get a summation we go from this first level level 0 all the way to the second to last level we sum up the work we did sum up the additions we're not doing anything new nothing new is happening we're just using that generalization we had before and we're using it right there and then what we add that to is what we deduced at the flea Flevoland our atomic multiplications because we don't keep going if we have two single-digit numbers we just have an answer because that's a that is the finite the smallest the smallest multiplication that can happen it's an atomic multiplication so we have mu times four to the log n 4 to the log n is the number of base cases the number of leaf nodes times the cost of the atomic multiplication so this is the work that we do and we can do some plication I probably do it wrong so I'm just gonna pull from my notes so if you actually solve this and throw the summation in some calculator what you're going to find is we're going to be doing and squared multiplications and the surprising thing is although we did this divide and conquer approach we would think that this would do better but it actually doesn't and on this asymptotic end it does not do any better than our multiplication with the grade school algorithm and that's how many additions we do but we're more concerned about the multiplications because they weigh us down a lot so what we see here is we did not improve we did not do better asymptotic Li and this does not help us so we need to go back to the drawing board literally and we need to reassess our original equation that we came up with and see how we can fix things all right so we're back through the drawing board and let's pull back up our equation we had so that is our equation to express x times y we're doing four additions right there there there and there and that is not good that did not help us improve on our asymptotic bound for multiplications so we need to see the culprit and the culprit sits right there that those two terms in the middle are multiplications that we do not need to do and here's the reason why what we can actually do is we can let's put BC plus AD right there BC plus ad is the same thing as a plus B times C plus D minus a c-minus B D and remember we already have a see we already have B D so what we're doing is we're reducing our multiplications and increasing our additions instead of doing four multiplications now we're going to be doing three multiplications but we're going to be doing more additions if we do it this way if we take a plus B and n over two plus and n over two term how many additions is that that is one-half alpha and additions if we add C plus D that is going to be one-half alpha n additions okay and now we need to do a subtraction which is basically the same thing as addition except against a negative number a times C is a length and number remember and n over two number times an N over two number is a length and number so we have the multiplication between two lengths and over two numbers which yields a length and number now we have a length and number added to a length and number how many additions is that that is going to be one alpha n additions and now after that we now have a length and number added to a length and number Y is B and D B times D a length n number it's a length and number because it's the product of two lengths and over two numbers so a length and number added to a length and number is another one alpha and additions so from this middle guy that we just did a little fixing to we just did three alpha and additions we've already done more additions than we did with our for multiplication method for multiplications but we reduce the amount of multiplications which was weighing us down so now we have this result from the middle let's bring back our original equation we did three alpha and additions from the middle guy and the two edge guys will just be nation but what we need to think about is we're gonna be adding something length 2n to something length n how many additions is that that is one alpha and additions so the total additions across the whole equation is for alpha and additions so what we need to see is we just reduced our multiplications to three multiplications but what we did was we increased our additions to four alpha N and that's not a bad thing because we're going to see how that improves things so let's analyze a recurrence for this okay so let's draw a recurrence so let's draw our equation so now we have our equation and what we need to see is how many times do we fork and we just established we reduced our multiplications from four to three so we do three times what does the sub-problem break down into remember we have two lengths and numbers we cut them in half and we're doing the same thing we're passing length and over two numbers X and y into our sub-problem so the size of the sub-problem stays and over two we break down in half so and over two plus what how much work do we do at this level in terms of atomic additions so remember we just increased our additions and reduced our four kings so we have four alpha n atomic additions so this is our recurrence and now that we have our recurrence we can actually look at building a tree and seeing if this actually helps us and it's just like before okay so we have our original n and what we're going to do is we're going to do three for Kings three multiplication recursive calls happen okay we broke them down into three forks and now we have sub-problem size of n over two we've seen this before and now we do another forking of three going downwards okay and now we have all these guys right here so let's count how many subproblems we have top level we have one this level we have three this level we have nine how much work is done in each level at the top level we do four alpha n work at the next level we do for alpha and over to work at the next level we do for alpha n over for work remember that's our sub problem size passed to our addition or that our did our additions are contingent on the sub-problem size so now do you see how we're doing powers of 3 we have 3 to the 0 we have 3 to the 1 we have 3 to the 2 9 nodes right so we can generalize 3 to the I 3 to the I times 4 alpha what for alpha times and over what we see this is 2 to the 0 2 to the 1 2 to the 2 all we need to see is do we need to draw the patterns we just need to see the patterns it's not it's not that difficult to see that then the denominator is going in powers of 2 and that's how we noticed that so what we see is we do add over 2 to the I and how many atomic multiplications happen at the last level how many levels do we have we have log n levels how many for Kings do we do at each level we do three for kings so 3 to the log n right so think about this 3 to the 0 3 to the 1 3 notes 3 to the 2 9 notes so does that make sense so the cost of a atomic multiplication times the amount of atomic multiplications which is gonna be 3 to the log n so this is going to sink in with time but this is what we do we need to sum the work for the additions and we need to sum the work for the atomic multiplications so we can do that now so what do we do we sum the work done in our recursion tree which is the additions that happen 0 to the second-to-last level which is technically the last level addition the base cases are our final level which are expressed right there the time it takes for our atomic multiplication times the amount of atomic multiplications which is going to be 3 to the log n and this gives us the work for this algorithm and this is called keiretsu a multiplication I should have mentioned that in the beginning but it'll be in the video title but this gives us this equation if we solve this and again it's a pretty lengthy process we can just jump to the results so what we see is eventually we get a result of how many multiple atomic multiplications and to the log three so okay we did it we weren't able to become faster than n log n but we were able to achieve a new bound which is a bound which is n to the one point five eight multiplications or atomic multiplications so is like it I think this is just like intriguing this is literally a faster way to do multiplication this is this is this literally at the time it was discovered pushed the boundaries of our understanding of how fast we could do something as simple as multiplication and I know this video kind of is useless for this channel and is useless kind of in general to know at all you won't use this probably but anyway - my point is at one point it was completely believed that the best we could do is N squared multiplications and someone was able to figure out a way to do it faster and the implications of this apply to other problems in life is just mind-blowing and I think that's why algorithms are fascinating they kind of suck to learn because they're really boring and they're boring but this this is this is fascinating we were able to find well technically not us but yeah we we we found a faster way to multiply to a order much much faster than N squared well not much much faster but doing n to the 1.58 is faster than doing N squared in terms of time this is keiretsu by multiplication and this is faster multiplication this is how it happens or works alright so normally I want to focus on algorithms like merge sort quicksort or algorithms you get any interview but I don't know what I kind of want to do like I want to do videos on algorithms because that's computer science but at the same time you don't really need to know this stuff at all for an interview so I'm going to slowly try to find the balance in this but I thought this was a cool concept and there were many people confused in my class and I really don't think any of this should confuse people I think it just requires the right teaching but anyway if you liked this video hit the like button subscribe to the channel my goal is to build one of the world's largest software engineering resources in the next one to two to three years and hopefully it happens and another awkward outro [Music]