How Karatsuba's algorithm gave us new ways to multiply

before we start with karatsuba's fast multiplication algorithm we should first look at how the history of multiplication began unlike the intro suggests our story didn't start with genesis on the fifth day god created the world it began in moscow in 1960 back then computer science was still young and it was a time where finding better and faster algorithms was the name of the game even as soviet superstar mathematician andre kolmogorov was looking at improving algorithms specifically he was tackling the problem of multiplication he analyzed different possible algorithms but in the end he arrived at a shocking conjecture multiplication couldn't actually be done any faster precisely he said that any algorithm for multiplying two n-digit numbers requires of the order of n-squared steps of computation except you know he said it in russian but to explain to you what exactly is conjecture is saying let's first get warmed up with a simpler problem the problem statement for addition is as follows given two numbers each having n digits calculate their sum and there's a pretty straightforward algorithm for that we add the individual digits from right to left occasionally our result has two digits so we get a carry and we have to make sure we account for that carry in the next edition so far this is something you've learned in second grade but let us ask how many steps of computation are needed since we do n additions and on top of that we might have to care for up to n carries this gives us up to two n additions in total if solving a problem takes at most a number of computation steps proportional to n rewriting computer science that it takes order and steps i claim that order n is also the fastest an algorithm can be even if we had a god-like algorithm an algorithm so ingenious it somehow wouldn't even need to look at the input well it still has to output all digits any algorithm has to spend n or n plus one steps outputting the result and so at least n steps are always needed if an algorithm takes at least a number of computation steps proportional to n we say in computer science that it takes omega n steps so if we know that our algorithm needs at most proportional to n many steps and any algorithm needs at least proportional to n many steps anyway then we know that we have found an algorithm that is as fast as possible so we could consider this altered conjecture solved any algorithm for adding two engineered numbers requires of the order of n steps not only that but our standard algorithm from elementary school actually reaches this optimal run time now hold on i think i have some explaining to do you're probably complaining what's up with this proportional why do we claim that the algorithm is optimal if in fact it is two times lower than the theoretically best possible algorithm what's the point of o and omega here's the problem in computer science what exactly a step of computation is has room for interpretation for example what if we just remember whether the last edition had a carry whenever there's a carry we could for the next edition have our algorithm just output a digit to one larger than usual there's nothing stopping us from redefining addition in this way the computer doesn't know so we would in a sense do what used to be two steps in one step and you can see that we then only have to do n plus one steps at most or here's a real life example the device you're watching this video on is probably a 64-bit device so it can add 64 digits in one step meaning that it could add numbers with runtimes as low as n divided by 64 steps 64 times faster than even the fastest possible algorithm what's up with that there is a theorem called the linear speedup theorem that makes this precise given an algorithm with runtime t it essentially says that you can artificially slow down or speed up the algorithm by switching to a machine that simply does more or fewer steps per step so to speak while the algorithm itself basically stays the same and in this sense you can't concretely say how fast a problem can be solved because for any algorithm that solves that problem there always exists an even faster implementation on another machine so to capture the essence of an algorithm we ignore the constant factor in the front meaning that n counts the same as 2n which counts the same as 3n and so on instead real improvements have to come from algorithms that are faster by more than just a constant factor we group runtimes according to their order and we classify algorithms by whether they are linear quadratic or cubic and what not this idea that you cannot precisely give a runtime for how long it takes to solve a problem is omnipresent in computer science and i hope it could clarify why i hope that you understand now that why when you go on wikipedia and read about algorithms you'll see that they never give concrete run times and instead always use this o and omega notation so now that we're finally warmed up let's go back to kolmogorov's conjecture what is kolmogorov trying to tell us let's look at the problem this video is actually about if we want to multiply two n-digit numbers we know from elementary school that we write down each digit n times such that every digit from one number gets paired up with every digit from the other number we multiply all those pairs together and for products with multiple digits we carry and finally adding row by row gives us the final result as before let's count the number of computational steps since both numbers have n digits we have n times n pairs of digits so we do n squared individual multiplications on top of that we do n squared carry overs and finally we do n minus 1 additions let's be generous and round that up to n additions normally each addition would need 2 n steps but here our numbers have gotten twice as large so we need 4 n steps over all n additions this gives us four n squared steps so in total we need six n squared steps and since we ignore the constant in computer science our elementary school multiplication algorithm has a runtime of order n squared when kolmogorov announced his conjecture he was well aware of this fact but he also looked at other multiplication algorithms like the russian multiplication an algorithm number file made a video about and every time he analyzed a runtime it was order n squared so mankind has multiplied for millennia and has never found a faster algorithm maybe there's a reason for that maybe there is no faster algorithm maybe so-called mogher conjectured omega and squared steps are always needed so what he's essentially saying is that the good old elementary school multiplication method is the best that we can do and no faster algorithms exist but from the title of this video you could probably guess that oh boy was he wrong so in 1960 kolmogorov organized a seminar in which he amongst other things presented his conjecture many highly respected mathematicians attended this seminar but also that it unknown student anatoly karatsuba could be found amongst the participants and also he tried his luck by tackling kolmogorov's conjecture and to everyone's surprise he could not only disprove his conjecture but he found an algorithm faster than n squared within a single week this is how he did it let's begin by multiplying two numbers with just two digits remember that in our standard algorithm we would multiply the ones with the ones digit the tens with the ones and vice versa and lastly the tens with the tens digit we add up and do some carries if necessary but otherwise this requires four individual multiplications but kurotuba could do it faster he could do it with only three multiplications the trick is that he first adds the digits together and multiplies these sums by expanding you'll see that this equals all four products from before just summed up this insight is the main idea behind the entire algorithm you could say that karatsuba simply rediscovered the distributive rule but then he continues similar to before in his second and third multiplication he calculates the first and the last digit and by subtracting both of those products from the big sum he extracts the remaining two products needed for the middle digit some carry overs if necessary and he's done so karatsuba has this really interesting tradeoff where he spends extra time adding and subtracting but therefore only has to do three multiplications is the tradeoff worth it and how does this idea help multiply numbers with more than two digits let's for the general case assume that the number of digits is an exact power of two because if not we can just fill up the missing digits with zeros this assumption simplifies the algorithm and you can check afterwards that this merely increases the runtime by a constant factor a constant factor we can as usual ignoring computer signs we begin by applying the principle from earlier except that instead of only the lower digits we now calculate the whole lower half likewise instead of only the upper digits we calculate the whole upper half and we also have the sophisticated middle part where we add the halves together multiply to get the big sum and subtract from it the lower and upper halves we calculated earlier in the two digit case the only overlap we had between the three parts which are some carries but now the overlap is so big we need to do an addition over the whole thing i should mention it can happen that because the middle part starts with an addition that the numbers end up with one more digit but you can check for yourself that this can be rectified with a few more additions if necessary just make sure they are done at the correct position putting the digits at the correct position in general is not hard it's just a lot of bookkeeping like if i multiply the third digits with that fifth digit that influences the eight digit in the solution but you already knew that from the elementary school algorithm anyway keeping track of all the computation that has happened so far we can start analyzing the runtime to remarks i haven't explained subtraction but it's easy to see that this can be done similar to addition and that it needs two n-steps furthermore some of the input is half and some of the input is now twice as large so we might need n or four n steps respectively you can go over all computation steps and let's be generous i think that 20n steps suffice to capture everything well almost everything except for three things we still need to include the three multiplications of half the original size how long did they take wasn't it something like six n squared steps maybe if you use this low elementary school algorithm no just use current super's algorithm again and as we just saw they too have a runtime of 20n except since the input is half the original size by now their runtime is only 20 and a half but don't forget the current supers algorithm again generates three more multiplications each time with the input half further giving us nine multiplications with a runtime of 20 and fourth and so on and so on until the algorithm has broken up the input so far that no more card super is needed and we arrived at single digit multiplications let's calculate the total runtime let t denote that total runtime the first iteration took 20 n steps while for the next iteration we need to do three times the work but therefore half the input and for each successive iteration we pick up another factor of three but therefore get to half the number of digits again continue in this fashion until we've halved k times at which point we gained a factor of 3 to the k but therefore completely eliminated n this gives us a huge sum and we can start simplifying it by taking out the factor of 20n the informed viewer recognizes what remains in the brackets a geometric series and i know from high school that there exists a nice formula for that simplifying further the minus 1 in the denominator reduces it to a half and a minus 1 in the numerator well this doesn't simplify to anything but we can just ignore it and then equality still holds we cancel a half from both sides of the fraction and now remember that n was defined as 2 to the k so those two cancel two we move around the factor of three and there we have it a really nice and simple expression for the runtime just one last thing it would be nice to know the runtime not in terms of k but in terms of n since n was defined as 2 to k n to the 1.6 is certainly more than 3 to the k why 1.6 that 1.6 is chosen because 2 to the 1.6 itself is just a bit more than 3 which allows us to plug in the n to the 1.6 in place of 3 to the k so all in all the runtime is no more than 60n to the 1.6 or as we computer scientists say order n to the 1.6 n to the 1.6 is lower than linear but faster than quadratic so karatsuba indeed managed to beat the elementary school multiplication algorithm just as a warning even though this is faster in theory in practice i don't know the algorithm is certainly too complicated for any human to use effectively and it has such an overhead that in modern hardware it becomes only faster than the standard method for numbers with several hundred bits which happens to be the kind of numbers you find in cryptography but otherwise people mostly still use the simpler standard method but hey kartsuba managed to disprove kolmogorov's conjecture funny story according to the legend kartsuba told kolmogorov about his discovery and kolmogorov was impressed he was so impressed in fact that he wrote up the discovery and submitted it as a paper in the name of card super but without katsuba knowing about it the paper got accepted and they returned it to the author by mail it was only then after it got published and karthuba opened the letter that he held his own paper in his hands for the first time now that people realized that the quadratic barrier could be broken everyone wanted to multiply faster but the algorithms became much more sophisticated so for the rest of this video i'll just give a high level summary of the subsequent history the next big improvement by schoenhagen strassen came after the invention of the fast fourier transform for those viewers who are a little bit familiar with the fourier transform i can give you the general idea if we look at how we multiply in our standard method and focus just in a single digit if you think about it what we're doing when calculating that specific digit is basically a convolution of our two numbers and as that informs you knows there's the shortcut for convolution by applying the fast fourier transform onto the input multiplying the two vectors together element by element and then applying the inverse fourier transform multiplying element by element and times is order n and if you're familiar with the intricacies of the fast fourier transform then you know that it can be done in order n log n time same for the inverse fft so you would expect the total runtime of order and log n there are some details missing though because multiplying complex numbers is not really a constant time operation so in the end scherenhog and strassen actually get order n log n times log log n but the conjecture that the log log n factor can be removed and that a clean n log n can be achieved after that no big discoveries were made for 36 years until martin fuhrer found an algorithm with a runtime of n log n times k to the log star n where k is a constant he didn't even specify for those who don't know what log star is it is the iterated logarithm the iterated logarithm of a number is equal to how often you can apply the logarithm to it until you reach 1 or less log star is a really really slow growing function log star of the number of atoms in the universe is 5. so even though k was unspecified whatever k to the log star n might be for all inputs that fit inside the universe it's no more than k to the 5. so it's basically a constant and in this sense fewer found an algorithm really close to n log n by 2018 k itself was brought down to four and finally in 2019 the long sought-after n-log n algorithm was finally found by yoris thunderhiven and david harvey a cute fact about this algorithm is that it uses a thousand seven hundred and twenty nine dimensional fourier transform and their techniques become useful only for numbers with more than two to the thousand seven hundred and twenty nine to the twelve digits not numbers above this but numbers with more than this many digits for smaller numbers they still recommend using the standard algorithm so now that we found the n log n algorithm how do we continue it is conjectured that multiplication needs omega and log n steps and that therefore the latest algorithm is the best possible but we should be careful with that assumption because we all know how such an assumption went for kolmogorov there are some simpler restricted computational systems though where omega n logan actually is a known lower bound david harvey himself said that he is not yet fully convinced by these simpler systems but otherwise it wouldn't surprise any of us if that really turns out to be the true lower bound and that we're now at the end of the history of multiplication algorithms

Channel: Nemean

Views: 373,133

Rating: 4.8923874 out of 5

Keywords: Computer Science, Mathematics, Algorithms

Id: cCKOl5li6YM

Length: 18min 47sec (1127 seconds)

Published: Sun Aug 22 2021