multiplying two numbers together might seem like a pretty innocuous piece of mathematics we all learn how to do this in high school for instance but if your two numbers are enormous for example in cryptography you're trying to find the largest prime numbers then the efficiency of the algorithm to multiply enormous numbers starts to really matter and in this video I want to take you on a little bit of a journey of the development of increasingly sophisticated multiplication algorithms let's quickly review that grade school algorithm if I have two numbers like 32 multiplied by 56. now the basic mechanism goes something like this I'm going to take the two things in the ones column multiply them to get 12. some of you like to write the one up at the top or I'm going to leave it down at the bottom and then you might multiply 3 times 6 and get 18 but it shifted over by one you could put it zero after the 18 if you like then you multiply the five and the two you get a 10 also shifted over by one and finally you're multiplying the 3 three and the five that gives you a 15 shifted over twice it's 1500.
add those four numbers up and you get 1792 Final Answer depending on exactly how you were taught and where in the world you might organize your information a little bit differently but this is the basic algorithm that most of us are familiar with and what I really want to note is that in this algorithm you have to do four different sub multiplications four different multiplications of single digits like two times six is twelve after you get those four results then you have to add them up so there's four multiplications and three additions to do this algorithm and in general if you're multiplying two n digit numbers together it takes N squared total multiplications to get your answer a different take on this is if I look at a number like 32 I can think of this as three times ten plus two in general if a number has digits like a b then what I really mean by this is a times ten plus b and live similarly c times ten plus d so if I multiply these two things out then what what I times 10 a d plus BC times 10 and timely BD just times one that is there are four different multiplications as we've seen before this is the same algorithm you know and love I've just perhaps organized it differently on the screen but now I'm going to do a trick let me look at that middle term that tens term the a d plus BC times 10 term I'm going to replace these two multiplications by one multiplication it's just a little bit of algebra there's almost nothing to it if I expand out a plus b times C plus d i get terms like a c and b d and so I just subtract them off and these two things are equal but now I notice that a B plus C D well there's one multiplication there and then there's two more a c and b d but AC and BD are multiplications I have to do anyways I have to do AC I have to do BD and so now I have a total of only three single digit multiplications that I need to do in this algorithm this is called the carrot Suba algorithm now while I have a gain that I have less multiplications to do I do have more additions to do but as we're going to see a little bit later and depending on your computer's architecture multiplications are going to be the thing that slow us down so having to do less multiplications even at the cost of more additions is going to be a net benefit to us okay so let's run that carrot Suba algorithm out for our 32 times 56. I still have to do the ones and I still have to do the 100s the 12 and the 15 are exactly the same but in the middle that's going to change by the algorithm I'm going to expand this out and then if I plug in the numbers the result that I get is just going to be 28 but indeed 12 plus 280 plus 1500 is the same thing as 1792 the same result we got before now I actually think that this is slower for us humans doing small numbers like this hardly this is because single digit multiplication is something we've all memorized we've all memorized this times table so you can say 7 times 8 and you immediately know the answer so getting less single digit multiplications which for humans we've memorized in the cost of having to do more additions is actually slower for us humans for these small numbers the kerasuba algorithm isn't going to replace your mental math quickly but where it's going to shine is when I consider larger numbers let's just go a little bit larger up let's do an eight digit times an eight digit because I can do carrot silver over and over and over again first I'll try color coded in the same way where I break a number up as an A and A B and A C and A D really what I'm saying is this is one two three four times ten thousand plus five six seven eight if I imagine thinking of the ABCD sort of blocks that keep together I'm going to get four different sub multiplications that I'd have to compute out but carrot subba says that instead of four sub multiplications I only need three indeed these two sort of diagonal ones can be condensed into just a single multiplication and then same let me take any one of these multiplications I have to do that's now four by four well I do the same thing I can write this as a times a hundred plus b so 1200 plus 34 and 9100 plus one I try to think about what would be the four different sub multiplications I need to do and two of them buy the caratsuba algorithm I can remove down to one multiplication and then two by two we've already seen how I can take two by two and just a three one by one multiplications and so I can take this divide and conquer approach and just do it over and over and over again let's imagine I'm taking two numbers of size 2 to the power of K and multiplying them it's not exactly two to the K you can just imagine having a few more zeros at the front until it's the closest power of two but with two to the K's this is going to be mostly efficient because now I can imagine having and having and having just as we did before eight four two one I can do that when it's powers of two and for every stage where I take a number up and I break it in half then I can say that there's three multiplications that stage so in general there's going to be three to the K multiplications needed to multiply out to two to the K numbers I can do just a little bit of a fun log stuff like three to the K that's the number of multiplications if n is 2 to the k then k is logarithm base 2 of n so I can just write this as 3 to the logarithm base 2 of N I can use some log rules to Interchange the 3 and the n and if I compute out what log base 2 of 3 is it's 9 to about 1. 58 and this is an improvement because the algorithm that you and I all know that we are taught in school took N squared multiplications and now we only need about n to the 1.
58 as n becomes arbitrarily large we've got a faster algorithm now to be fair this all depends on what your computer is actually doing that is they've either got Hardware circuitry in the actual chip or very low level microcode that has the ability to multiply numbers together if they're going to be of a certain size so for example you might have a 32-bit by 32-bit Hardware multiplier which is able to quickly use its Hardware to multiply any numbers as long as you can express them in 32 bits so if that was the case then what you might do with the carrot Suba algorithm is not use powers of tan like I Illustrated when I was doing this just for us humans that are familiar with powers of 10. you might do a breakup in powers of 2 to the 31 leaving maybe one extra digit for dealing with carrying so that is you might take any number and you might express it as a times some power of 2 to 31 plus b and here the A and the B can both be expressed within the 32 digits and so this means that for enormous numbers numbers way bigger than just 32 bits you can recursively apply the carrot Suba algorithm until you get down to multiplying two numbers that can be written within 32 bits and you do that now with the hardware multiplication in your computer okay so what I've told you so far was really just the beginning of a story I told you about the carrot Suber algorithm it came about in 1960 and as we talked about its complexity is n to the 1. 58 multiplications for large values of n very quickly after karatsuba there was a generalization tomb cook and this has been implemented in a lot of different computers now for small numbers just the normal N squared algorithm is actually faster because you've got this extra overhead with memory and with additions but for numbers after about 10 to the 96 the tomb cook or carrotsuba algorithms tend to dominate The N squared algorithms and for a bunch of different applications as I mentioned before cryptography they're carried out with some version of one of these types of algorithms that isn't the end of the story because after karasuba and tomb cook Sean hadga strason came out with a fundamentally different algorithm in 1971.
oh by the way this strason is the same strason that did these algorithms for large matrix multiplication I've done a video on that you can check it out Sean agastras said aren't just using this little bit of algebraic trickery I showed in this video they're using the Machinery of discrete fast Fourier transforms and like to unpack in a different video but for this video the fast Fourier transforms allowed for this new algorithm that is substantially faster than what we've seen before and it has applications for example I I've talked previously in the channel about the great mercen Prime search finding these enormous prime numbers well it turns out that after somewhere between tens and hundreds of thousands of digits the Sean had a strasset algorithm starts to beat out the tomb cook algorithms that we had before that that were used for these sort of lower level things like cryptography and indeed this algorithm is basically sort of the go-to algorithm that's actually implemented for computing these really large numbers but this still isn't the end of the story because this order of n Times log n Times log log and was always a little bit weird to Sean haga and strassen because they use fast Fourier transforms and because fast Fourier transforms have an inherent n log n complexity to them it wasn't likely that you could get faster than n logarithm event but they did conjecture that you could get rid of the log log n part and the best of these algorithms in this sort of class using these Fourier transforms could thus just be n log n and while there has been some improvements chipping away over the years that best conjectured result didn't come until 2019 with Harvey and hovet they managed to come up with a new algorithm still using uh fast Fourier transforms but using them more aggressively using more of them and managed to get to that conjectured result n log n complexity and so this is sort of Presumed to be the best possible result here unless possibly someone comes up with a completely different type of approach because of the intrinsic complexity within Fourier transforms and this result is theoretically fascinating but it's what we sometimes call a galactic algorithm this we don't Implement in code nobody's using Harvey Hoven today to try to compute out these enormous numbers and the main reason for this is just you need enormous numbers for this new algorithm to actually be better than the Sean hagenstrassen algorithm they've got one possible number so it's no one to be better after 2 to the 1729 to the power of 12 this outrageously enormous number maybe that can come down a little bit in time but still we're talking about vast vast fast numbers beyond the level of applications that we're using today and it's actually kind of interesting as I mentioned a lot of this depends on your computer architecture design but sort of beyond what I'm trying to talk about in this video but it is worth noting that the gap between Hardware multiplications and additions in computer architecture has come down a lot and actually in some cases has even flipped the other way around and multiplications can even be faster and so despite his theoretical Intrigue the Practical applications of this new algorithm is in indeed somewhat limited if you are interested in deeply learning about all sorts of cool algorithms like these ones then I strongly recommend today's sponsor brilliant. org brilliant is an online learning platform and they have thousands of lessons across mathematics computer science and more that all are delightfully interactive you might specifically like this course on algorithms and data structures it Dives more into for instance the Big O notation that I was using pretty casually in this video one of the things I really appreciate about brilliant is how they are constantly getting you to self-assess your own understanding and when you get something wrong they are there to help you figure out what the right answer is as a math professor I know that this kind of active student-centered learning is highly effective and that's why I'm so proud to be sponsored by brilliant to try everything that brilliant has for free for a full 30 days go to brilliant.
