It could also be step 3 =(a-b)*(d-c) and Step 4 = step 1 + step 2 + step 3. The same results would be obtained. Instead of subtracting large numbers after multiplication, it is before multiplication, making multiplicands smaller. Helps to calculate manually. Number of steps would remain the same so there may not be any appreciable change in execution time in computers.
If you try to code using this algorithm, a note: X * Y = (Step 1)*(10^(n/2+n/2)) + (Step 4)*10^(n/2) + (Step 2). Observe that in Integer programming, n != (n/2+n/2) in case of Odd 'n'.
Great video. At first I did not understand it. I had to watch it twice. Being a not native English speaker makes it a bit harder. Anyways, great content, thank you so much!
def karatsuba(x,y): if x < 10 or y < 10: return x*y else: n = max(len(str(x)),len(str(y))) mid = int(n/2) power = 10**mid a = x//power b = x%power c = y//power d = y%power print(a,b,c,d) ac = karatsuba(a,c) bd = karatsuba(b,d) acpbd = karatsuba(a+b,c+d)-ac-bd return ac*(power**2) + bd + (acpbd*power) My python implementation of karatsuba
Fascinatingly counterintuitive algorithm, but difficult to optimize in reality. Eg. if a,b,c,d are 32-bit integers then (a+b) and (c+d) are 33-bit numbers, and their product is a 66-bit number, requiring extra operations to track, etc.
Yes, assuming that a computer has a single precision multiply instruction giving a double precision result, one can split a (software) double precision multiply into 4 single precision ones and do each of them with the hardware instruction. All you need to do then is to add the four results together with appropriate alignment (ie. shifting). So, can you apply Karatsuba's algorithm to reduce the number of multiplications to 3? In theory, yes, but in practice, as you point out the (a+b) and (c+d) parts no longer fit into single precision registers, so the multiply instruction can't be used without a lot of fiddling about. If you're writing it in assembler, it's probably slightly easier than in a high level language, because you've got access to the carry flag from the additions, so it's a case of an extra addition when the carry is 1. Still a nightmare, though. Therefore in practice it's probably easier and quicker just to do the 4 multiplications.
i was screaming in my head how we have four multiplications with 1/4 as many single digit multiplications as x*y so how is it any better.. as soon as you wrote out (a + b) ( c + d) near the end it clicked.... this simple product minus ac and bd gives us our ad + bc... and this is the entire reason why karatsuba hits that juicy O(n^log_2(3))
Nice explanation :) But one thing bothers me: is this really an improvement? Sure, there are only 3 multiplications now instead of 4. But suppose that a,b,c,d are digits. So we have: a×c is one single-digit multiplication, b×d is one single-digit multiplication, now we need `a+b` and `c+d`, which are single-digit additions, and each of them can produce 2-DIGIT NUMBERS! So the third multiplication is actually another 2-digit by 2-digit multiplication, which is pretty much the same problem we're trying to solve when multiplying (a×10+b)×(c×10+d) ! :P So it will secretly contain three more multiplications and a bunch of additions and subtractions! I used digits to demonstrate the problem, but the "digits" can as well be the multi-digit "limbs" of the numbers, e.g. 32-bit integers. So if a,b,c,d are all 32-bit "digits" (base 2³²), then both `a+b` and `c+d` would have to be 31-bit numbers, or use 64-digit pairs of 32-digit numbers, and those will be the numbers multiplied in the last step, right? Which requires them to be decomposed again into four 32-bit "digits" and run through Karatsuba multiplication. But this seems to be circular, because this multiplication can in turn require the multiplication of another 2-digt numbers, and so on... Something is wrong here :P
*"but the "digits" can as well be the multi-digit "limbs" of the numbers, e.g. 32-bit integers."* So the problem still stands for "sufficiently large enough".
I wasn't worried about the infinite recursion. I was worried that it won't really be that much of an advantage over the usual multiplication algorithm, and in the worst case, it might actually involve more calculations.
In the grade school method, multiplication is O(n^2) but addition and subtraction are O(n). Now in order to improve the complexity of multiplication Karatsuba follows the divide and conquer paradigm. So, the divided tree will be log(n) in height (because on each step it is getting divided by 2 so in log(n) depth it will be completely divided). So leaves of the tree are just 1 digit numbers. So Karatsuba ensures that there will be only 1 digit multiplications and addition and subtraction. This makes it O(n*log(n)). Remember this: (a×10+b)×(c×10+d) gets translated into: a*c with place value of 100 + b*d with place value of 1 + (a*d + b*c) with place value of 10 to find (a*d + b*c) it does (a+b)*(c+d) without multiplying with their place values. now (a+b)*(c+d) = ac + ad + bc + bd , so on subtracting ac + bd we get ad + bc as needed. This makes 2 multiplications into just 1 multiplication which reduces one extra recursive call. So in total there will be 3 recursive multiplications, of numbers with half the digits. After getting results from recursive calls they are added together according to their place value.
time complexity here is O(n^log(n)) and n is the number of times your are multiplying so for the previous case its O(n^log4)=O(n^2) but after only three multiplications it becomes O(n^log(3))=O(n^1.58) so thats an improvement i guess for the large value of n
The way you divided the cake doesn't matter much as long as there's still the same amount of cake in each piece :q It doesn't matter if you divide it recursively or just linearly, if the number of calculations stays the same. There might be 3 multiplications at each level instead of 4, but if the numbers used for the middle term are longer than those for the first and last term, they will still require more multiplications underneath than before. Which means that we didn't really get rid of any multiplications, just hid them underneath our recursive step (pushed down the tree, if you will). In "divide and conquer" algorithms, you don't get advantage from mere dividing the problem recursively - you get the advantage by REUSING COMPUTATIONS from one branch of the tree in another branch, thus making many branches unnecessary. Pushing operations down the tree gives you no advantage at all. What would convince me that this is indeed an advantage, is counting the ACTUAL number of operations from ALL levels, taking into account the LENGTHS of numbers in each operation (i.e. number of digits, or number of bits in each), because this is important. If you don't take this into account, then guess what: I can turn your "m digits by n digits" multiplication problem (which is O(m·n) obviously) into a simple 4×4 multiplication problem by splitting the numbers in half and performing just 4 multiplications :P You think that would be a huge advantage too? :P No, of course not! Because each of these multiplications still require (m/2)·(n/2) sub-multiplications on its digits that have been just hidden underneath.
I've been doing this since I was re-multiplying in adulthood; if it was 89 for instance and then I make it ninty if the other number is single and whatever; I've been doing whatever directions that was going to be the easiest and for me; I can see them all and if they were three digit each or what not; well it was just easier to do it the whatever way that I'd had done it in school because you know what; the last time I needed to do it like back then cause it had many digits; well I had needed to remember for a couple of seconds. It just doesn't really happen to us anymore. We'll use a calculator if there are many calculations to solve and there are many other more important things to be concentrating on instead of trying to figure out things to speed up things that really; if everyone were to have had been concentrating on things as much as this person did; we would have gotten not much further; because this should had been noticed at the beginning of our human calculating assessments. Sad it is really how everyone just are impressed by how long it took to realize things that have been overlooked because of all the students have had been "explained that certain things had had been established to having been established that they were to not having any more thoughts on ever again as it would be a waist of time. Well; a big waist of time is to not being spending all of our time on figuring out everything once and for all and maybe just maybe we could have a chance on not needing to lose our lives as aging and such. I don't even want to watch this video; it saddens me to see all of everyone not taking initiatives towards researching our anatomy to it's fullest in a manner that the same amount of time that would have been spent in fifty years; we could do in on or two or three. With more people more hours and more collaborations and many more research groups that deliver; most jobs; if you can't figure it out;' step aside or ask for help and chances are that someone other then you will be able to figure it out and maybe one day you may be the one to figure one of the things out; but we aren't in any position where we can afford to put all of out eggs in that same basket . Sorry but sometimes I just need to vent and try at the same time to wake some of all of you up. Cheers you all. You know that some day soon; you all will be gathering all of my comments that are here and there; and likely be archiving them within a book; I hope it doesn't drag long enough for the makings of a series' worth of books. LOLOL
Are you trolling? Or are you just not that bright and have an inflated sense of ego. If you think this algorithm is just multiplying numbers by rounding them to the nearest nice number, doing the regular multiplication, and then accounting for the rounding, you're just wrong. Everybody does this, you're not special. Karatsuba multiplication is fundamentally completely different
dunno if starting the book with something so frustratingly unintuitive is a great way to make people feel invited into the world of algorithm analysis. i spent most of this chapter feeling stupid.
It is intuitive. The Divide and Conquer algorithm groups two digits, forming an even polynomial. There are two factors x = a(10^(n/2)) + b y = c(10^(n/2)) + d Then FOILing gives us: xy = ac(10^(n)) + (ad + bc)10^(n/2) + bd. Using additive inverse operation gives us the middle term in the Karatsuba Algorithm. If you want me to write that out, let me know.
It is really super easy, but the algorithm is unknown by most people. I by myself became aware of this alforithm just some weeks ago. I'm really surprised. It is certainly of real importance in cryptography public key algotithms.
Useless detail, bacause the premise of the video was to show that there are other multiplication algorithms in the field, you've proved it as soon as you've shown us the recipe. Introducing recursion that way is also bad from a learning standpoint. He wanted to show he knows his business or perhaps wanted to show he's damn smart.
This is not an introduction to recursion. Recursion, by this point in the pensum, was already introduced by Introduction to Cumputer Science in the previous term. This is a second-term course.
First of all, 5794 x 4123 = 23888662 (check on a calculator). The actual implementation is: 57 x 41 = 2337 (step1) 94 x 23 = 2162 (step2) 151 x 64 = 9664 (step 3) 9664 - 2337 - 2162 = 5165 (step 4) Result = 23370000 + 2162 + 516500 = 23888662 (step 5) Which as you can see, matches the calculator based result.
@@fuminou3271 That's how it works. Check step 5 at 3:22 in the video. To explain why we do that, you need to understand what is being explained in the video from 9:50. Basically, you can see on the formula under recall that we are calculating the 3 values represented by ac, ad+bc and bd. Then we need to multiply ac by 10^n and ad+bc by 10^n/2. Since in this multiplication n is 4, then multiplying by 10^n is adding 4 zeros and multiplying by 10^n/2 is adding 2 zeros.
