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'.
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
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!
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.
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.
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
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.
The best explanation i ve ever came accross..Thank you sir
Thank you for this clear explanation!!!
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.
Great explanation!! Didn’t understand it in class but you helped me get it :)))
Maybe the best lecture I've ever had
Thanks a lot for this material, keep it up.
Beautifully explained!
Fantastic video and explanation!
Wonderful explanation. thank you, sir !
shut up
Thank you sir the best explanation....
1:34 - 4:03 is all i needed to know as a refresher. Thanks!
thank you! really nice explaination.
This channel is a goldmine
It was amazing to watch this video.
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'.
He addressed this issue in the video :)
Great Video ! but upon which criteria is the padding happening in 3:30? Why did we add 4 0's to the first, none to the second and 2 to the last?
Such a clever little trick.
Great explanation thanks
we were going well, until the recursion and the agebra started, I got completely lost in that part.
Very good explanation!!!
Which device are you using to write with as you talk?
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
Useful for gate aspirants.
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!
thank you carlos
How you got that zeros in the last step 5?
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.
Very interesting !!
Nice :)
Where can we find assignment?
Great explanation! In contrast to looking at my script after watching this video I finally understood this topic! :)
Thank you for the lecture, what happens when the numbers are of odd digit? eg multiplying 123 by 456
a = 01 or 1, b = 23, c = 4, d = 56
As always, Gauss saves the day @11:04
I honestly still prefer the old one
Computers don't
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.
Thanks a lot!
thank you so much
WOW!!!!
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.
Now we know what is the level of Stanford
Is Coursera stanford algorithm course contain same videos
'yup'
How the trick is related to Gauss? In the original Karatsuba algorithm published in 1960, there are not references to Gauss...
Gauss was the person that noticed that you can do 3 multiplications instead of 4.
@@Nynxxx it was Anatolii Karatsuba
it doesnt work with 2 digits multiple 2 digits right, does it?
What decides padding with 0s
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
What happens if the quantity of ciphers is odd?
what if the value of 'n' is odd?
add +1 to N
How do you decide how many 0s following 2840?
same here
4:09 should not understand what i did
me:*understands*
also me:*confused*
you could understand what he did, but there's no way to understand why it works unless you work out the derivation for why subtracting 3 helps here...
what if x and y don't have same digits of numbers, how to define n?
Pad with 0. Or round up the n/2.
@@ankushmenat I understand padding with zeroes, but why would rounding up n/2 work?
@@thelastcipher9135 In the case when the number of digits in any number becomes odd.
@@amanranjanverma right. I thought he meant the rounding up works for the lack digit as well which is what confused me. thanks.
padding with 0's on the left side will also make n even.. isnt it?
what about 123456 * 789123 or 12345 * 123 ??? these are just example I'm talking about numbers with more than 100 digits legnth
You sound like a smarter ben affleck for some reason
I'm not baffled, it's the distributive property all day long to see that it works. Excellent explanation overall, though.
man. the transcript of the video was entirely taken from Algorithms Illuminated part 1. even the word "inscrutable" hahahahahah
5 min and I got it!
prove it
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.
The student, Karatsuba, more intelligent than the teacher!! Must have been a genius.
why
are chacha hindi me bolo yaar bak bak kar rahe ho sirf....
sir me dard ho gya marde.
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.
This method doesn't work for me i did 5794+4123 I got an answer of 13557162 when its 27114324
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.
@@nelbr why do u add 4 zeros to the back of 2337 and 2 zeros to the back of 5165 when u add it at the end?
@@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.