1 3 Karatsuba Multiplication 13 min

Рет қаралды 202,415

Stanford Algorithms

7 жыл бұрын

Пікірлер: 93

@PriyaMishra-gj9kl 6 жыл бұрын

The best explanation i ve ever came accross..Thank you sir

@sashavolkova9143 5 жыл бұрын

Thank you for this clear explanation!!!

@patrickfulton6405 4 жыл бұрын

Great explanation!! Didn’t understand it in class but you helped me get it :)))

@TheDQR 5 жыл бұрын

Thanks a lot for this material, keep it up.

@aristowow 6 жыл бұрын

Maybe the best lecture I've ever had

@AL-go2mv 6 жыл бұрын

Fantastic video and explanation!

@m.raflyyanuar9886 9 ай бұрын

Beautifully explained!

@ankitakri8431 4 жыл бұрын

Thank you sir the best explanation....

@rustam101 6 жыл бұрын

thank you! really nice explaination.

@KuchhLamhe 7 жыл бұрын

It was amazing to watch this video.

@esrayeniaras9292 4 жыл бұрын

Great explanation thanks

@vaibhavlodha5398 6 жыл бұрын

Wonderful explanation. thank you, sir !

@parikshitrajpara5706 3 жыл бұрын

shut up

@murali9649 2 жыл бұрын

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.

@crateer 4 жыл бұрын

1:34 - 4:03 is all i needed to know as a refresher. Thanks!

@annizheng428 3 жыл бұрын

Very good explanation!!!

@davidjiang7929 3 жыл бұрын

This channel is a goldmine

@v1das007 5 жыл бұрын

Such a clever little trick.

@carlos98132232 3 жыл бұрын

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!

@Sabanar495 3 жыл бұрын

thank you carlos

@SADHGURUUnplugged 5 жыл бұрын

Useful for gate aspirants.

@ademabdelmoula8080 10 ай бұрын

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?

@Rahul-Nalawade 5 жыл бұрын

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'.

@alexandernizhnikov5529 3 жыл бұрын

He addressed this issue in the video :)

@Pedritox0953 2 жыл бұрын

Very interesting !!

@codingjhames 6 ай бұрын

we were going well, until the recursion and the agebra started, I got completely lost in that part.

@fusedglass01 2 жыл бұрын

Which device are you using to write with as you talk?

@ninup1668 3 жыл бұрын

How you got that zeros in the last step 5?

@vikasvenkatraman2645 6 жыл бұрын

Nice :)

@calvintey9424 3 жыл бұрын

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

@kainaul7215 3 жыл бұрын

thank you so much

@dennisdavari5050 4 жыл бұрын

Great explanation! In contrast to looking at my script after watching this video I finally understood this topic! :)

@rfowkes1185 Жыл бұрын

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.

@chrisengland5523 Ай бұрын

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.

@aterribleyoutuber9039 Жыл бұрын

Thanks a lot!

@gouripanda7517 5 жыл бұрын

Where can we find assignment?

@sivabonthada1076 2 жыл бұрын

WOW!!!!

@lazywarrior 2 жыл бұрын

As always, Gauss saves the day @11:04

@movocode Жыл бұрын

Now we know what is the level of Stanford

@gafarraji 6 жыл бұрын

Thank you for the lecture, what happens when the numbers are of odd digit? eg multiplying 123 by 456

@jatinwadhwa7050 6 жыл бұрын

a = 01 or 1, b = 23, c = 4, d = 56

@somyadeepshrivastava6745 5 жыл бұрын

Is Coursera stanford algorithm course contain same videos

@gouripanda7517 5 жыл бұрын

'yup'

@adhikarimahesh2680 3 жыл бұрын

What decides padding with 0s

@muhammadsarimmehdi 2 жыл бұрын

I honestly still prefer the old one

@alex_turing 15 күн бұрын

Computers don't

@MichelJosephCardin Жыл бұрын

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

@moatef1886 5 ай бұрын

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

@ankitrawat1385 6 жыл бұрын

what if the value of 'n' is odd?

@carlospazuzu 5 жыл бұрын

add +1 to N

@finaalfionita8392 Жыл бұрын

it doesnt work with 2 digits multiple 2 digits right, does it?

@paraskevidimoraga5960 4 жыл бұрын

How do you decide how many 0s following 2840?

@Ak-zm3ce 2 жыл бұрын

same here

@scitwi9164 6 жыл бұрын

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

@scitwi9164 6 жыл бұрын

*"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".

@scitwi9164 6 жыл бұрын

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.

@BipinOli90 6 жыл бұрын

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.

@rashmitpankhania6513 5 жыл бұрын

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

@bonbonpony 3 жыл бұрын

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.

@mmfStudent 2 жыл бұрын

How the trick is related to Gauss? In the original Karatsuba algorithm published in 1960, there are not references to Gauss...

@Nynxxx 3 ай бұрын

Gauss was the person that noticed that you can do 3 multiplications instead of 4.

@mmfStudent 2 ай бұрын

@@Nynxxx it was Anatolii Karatsuba

@MasterMindmars 4 жыл бұрын

What happens if the quantity of ciphers is odd?

@gackerman99 9 ай бұрын

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.

@pawelloozik 7 жыл бұрын

5 min and I got it!

@parikshitrajpara5706 3 жыл бұрын

prove it

@rifatjahan4739 2 жыл бұрын

4:09 should not understand what i did me:*understands* also me:*confused*

@kranberrysucks Жыл бұрын

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...

@cheddargt 4 жыл бұрын

You sound like a smarter ben affleck for some reason

@dd1.d 3 жыл бұрын

what about 123456 * 789123 or 12345 * 123 ??? these are just example I'm talking about numbers with more than 100 digits legnth

@KJZheng-or4ik 5 жыл бұрын

what if x and y don't have same digits of numbers, how to define n?

@ankushmenat 5 жыл бұрын

Pad with 0. Or round up the n/2.

@thelastcipher9135 5 жыл бұрын

@@ankushmenat I understand padding with zeroes, but why would rounding up n/2 work?

@amanranjanverma 5 жыл бұрын

@@thelastcipher9135 In the case when the number of digits in any number becomes odd.

@thelastcipher9135 5 жыл бұрын

@@amanranjanverma right. I thought he meant the rounding up works for the lack digit as well which is what confused me. thanks.

@codeOdesign 5 жыл бұрын

padding with 0's on the left side will also make n even.. isnt it?

@gman21xx 6 жыл бұрын

I'm not baffled, it's the distributive property all day long to see that it works. Excellent explanation overall, though.

@franzscheerer 2 жыл бұрын

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.

@hesamrezamotiei2259 2 ай бұрын

man. the transcript of the video was entirely taken from Algorithms Illuminated part 1. even the word "inscrutable" hahahahahah

@cosmicfugue1226 Жыл бұрын

The student, Karatsuba, more intelligent than the teacher!! Must have been a genius.

@endykartoshka 2 жыл бұрын

why

@mdsahilkhan6075 3 жыл бұрын

are chacha hindi me bolo yaar bak bak kar rahe ho sirf.... sir me dard ho gya marde.

@FredoCorleone 5 жыл бұрын

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.

@joancolmenares9357 5 жыл бұрын

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.

@stormsith5169 Жыл бұрын

This method doesn't work for me i did 5794+4123 I got an answer of 13557162 when its 27114324

@nelbr Жыл бұрын

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 Жыл бұрын

@@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?

@nelbr Жыл бұрын

@@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.