Karatsuba Algorithm Explained with Examples

Karatsuba Fast multiplication algorithm is explained with examples in this video tutorial for n digit by n digit multiplication. It is shown how the complexity of multiplication is reduced from O(n^2) of traditional grade school multiplication to O(n^1.6) of faster multiplication using Karatsuba method. This result in reduced computation time to achieve large n digit by n digit multiplication.

[@areyouraphael]

I don't know why geeks for geeks and Briliant use such confusing math jargon. This video helps lots!

[@STEMprof]

Thanks Zeon! glad that video is helpful.

[@brianbrennglass8012]

This is the first time I have ever commented. Your video helped solidify concepts that I'm learning through a Coursera course. Your explanation is more succinct and graspable than Columbia professor Tim Roughgarden's

[@STEMprof]

Appreciate your comment & feedback. Glad to hear that the video is helpful.

[@srikanthpanasa9648]

It helped me in my research, thanks for the video

[@STEMprof]

Thanks Srikanth. Appreciate your comment.

[@animohene8304]

Thank you for the break down and great explanation

[@STEMprof]

You're welcome. Glad that you liked this video. The Generalization of Karatsuba Algo, Toom-Cook (Toom3) is also explained with Examples in this follow-up video: czcams.com/video/1XiSyNzMX6Q/video.html that I hope is interesting as well. 🙋‍♂️

[@sfallon7]

Thank you for this great explanation.

[@STEMprof]

You are welcome. Thank you for watching. Glad that this Karatsuba Algorithm video is helpful.

[@amisaraaah]

thank you for ur help 🙏

[@STEMprof]

You are welcome! Glad that this video is helpful.

[@amisaraaah]

@@STEMprof pls provide Toom Cook3 multiplication as well 🙏🏼

[@shubhampandey4284]

@@amisaraaah yes sir

[@STEMprof]

@@amisaraaah Sure, Toom-Cook (Toom3) Algorithm Explained with Examples (Generalization of Karatsuba Algo) in this follow-up video: czcams.com/video/1XiSyNzMX6Q/video.html

[@wafikiri_]

A recursive cascading algorithm until only single digit multiplications are involved, then cascading back to sum results. Not too easy, but not too difficult, either. I've coded worse recurrent things.

[@STEMprof]

The Generalization of Karatsuba Algo, as Toom-Cook (Toom3) Algorithm is also explained with Examples in this follow-up video: czcams.com/video/1XiSyNzMX6Q/video.html
Also an interesting sorting in Python is duscussed in czcams.com/video/JB60xI1eTT8/video.html
I hope these videos are useful as well. 🙋‍♂️

[@bonbonpony]

What if the numbers are of different lengths, and if those lengths are not powers of 2?

[@STEMprof]

Thanks Bon for comment & questions. Answering them would require a separate video post :)

[@adityabhattacharyya5971]

i think you put zeros on the left of the digits
for example if the numbers are 1133568 and 583902, you make them 01122568 and 00583902

[@christopherellis2663]

Four columns of digits 4²=16 multiplications ✖️
KA,
abcd
defg.
Pairs ab ac ad bc bd cd
ad bc cf dg only 10 multiplication ✖️
What is the point of complicating the procedure?

[@wafikiri_]

Sums in a computer take less time than multiplications, by far. In binary, numbers require many more digits than in decimal, and every multiplication of n × n binary digits requires n displacements to the right of one of the factors (division by 2, getting the residue) and n displacements to the left (multiplication by two) of the other factor, then adding it to the result each time the residue isn't 0 but 1, which is half the time on average: (n/2) sums, each sum involving n to 2n pairs of binary digits, 3n/2 pairs in average, plus adding the carry bit all the time (3n/2) whether it's 0 or 1: so, 3n additions by n/2 displacement steps makes 1.5 n² additions. Displacements take almost no time, adding does, so it's 1.5 × (n×single_binary_digits_addition_time)²; if we can get rid of 40% multiplications, even if we have to add and subtract 50% more, we get a significant reduction in overall multiplication time.

[@xkm-thebasetecchannel3823]

So this makes multiplication much slower.

[@MichaelCorlew]

For humans, yes. For computers, it makes it faster.

[@STEMprof]

Thanks a lot MC

[@TheSinisterPorpoise1]

This is not a good explanation.

[@STEMprof]

Thank you for watching this Karatsuba Algorithm video and for sharing your feedback. It would be helpful if you elaborate and explain which portion can be presented better.

[@mentore6667]

very poor explained, especially when you change the (12+43)*(56+78) ==> (1200+43)*(5600+ 78) WHY THIS COMPARISION ???????

[@STEMprof]

Thanks for your interest & comment. How would you improve the explanation then? What is your recommendation?

[@zZE94]

He didn't change it to that. That is just what Karatsuba found that using the digits that way results in one less multiplication.

[@moali5279]

It's essentially FOIL (First Outer Inner Last) from polynomial stuff (sorry haven"t dealt with algebraic terms for more than a decade)