Fast Multiplication: From Grade-School Multiplication To Karatsuba's Algorithm

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Can we multiply 2 numbers using less than n^2 atomic multiplications? Yes, we can.

You don't need this for the interview.

++++++++++++++++++++++++++++++++++++++++++++++++++

[BackToBackSWE]

Table of Contents:

The Problem Introduction 0:00 - 0:42
Analyzing Grade School Multiplication 0:42 - 2:09
How Do We Think About Doing Better? 2:09 - 3:06
Ok...Can We Do Better? 3:06 - 3:30
Let's Try A Divide & Conquer Approach 3:30 - 4:22
Redefining x & y In Terms of Our Segments 4:22 - 6:11
Multiplying The New Definitions Together 6:11 - 6:53
We Now Have An Equation For The Decomposition 6:53 - 8:14
Raw Divide & Conquer Approach: Exact Additions 8:14 - ...
Establishing The Worst Length From Multiplications 8:44 - 9:24
Handling The 2 Multiplications On The Edge 11:15 - 13:47
End of "Raw Divide & Conquer Approach: Exact Additions" 13:47
Raw Divide & Conquer Approach: Recurrence 13:47 - 16:43
Raw Divide & Conquer Approach: Solving The Recurrence 16:43 - 21:50
Raw Divide & Conquer Approach: Summing The Work 21:50 - 23:37
A Breakthrough: Karatsuba's Insight & Analyzing Additions 23:37 - 27:18
Karatsuba's Algorithm: Recurrence 27:18 - 28:14
Karatsuba's Algorithm: Solving The Recurrence 28:14 - 30:28
Karatsuba's Algorithm: Summing The Work 30:28 - 31:17
How Did Karatsuba's Do? 31:17 - 32:48
Wrap Up 32:48 - 33:50


Mistakes:
31:20 -> O(n ^ lg(3) ) is the asymptotic bound on the additions. Karatsuba's does not do this exact amount of additions in the worst case since constants were dropped. If you look at the equation on the board, it can be further simplified to see that there will be constants in front of the atomic multiplication symbol.

Karatsuba multiplication is not the fastest method for multiplication. Wikipedia: "The Toom–Cook algorithm is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm is even faster, for sufficiently large n."

[hanat]

my heart jumped when I heard him speak Amharic lol but loved the content. glad to have come across this channel, a new fan!

[sleepingsounds]

Wow Ethiopiawi neh ende ...
Keep it up bro you are incredible

[abelkidanemariam]

when he speaks amharic i started searching for another opened chrome tab

[OmarAhmed-zgfw]

Wow, I feel miserable. That was my algorithms year project, 4 years ago and i totally forgot it and forgot its logic along with those Latin letters and yet I'm here stumbled upon this video while i'm preparing for my interview at Amazon.

Love your work and the effort.
Keep it up dude.

[geraldcerna]

When the video started I was like, "OK, it's time to open the subtitles." LOL. But as always, great video and a very articulate explanation. Thanks!

[tonyz]

I had struggles with the medium level questions but after watching your videos, they don't seem confused anymore. I am going to purchase the one year subscription of you website.

[ariellelucca]

For my master's I'm doing a research on applying KOM algorithm on hardware. It is a very interesting topic for it applies on my research subject. So I just want to tell you that, even though for most people this may not be important, for certain people it will be a treasure. So, thank you!

[achyuthvishwamithra]

Thank you for this video, this greatly helped me in understanding Karatsubi algorithm which is used in my course for polynomial multiplication. Superb content!

[alessiodenny]

excellent !! thanks . You are a great teacher. Could not understand this topic in school after 3 hours of lectures, and I understood it in 5 minutes after watching your video.

[saurabhmahra]

CS guys are just mathematicians wearing ninja masks.
You're awesome man, great video. Honestly, I had never seen such detailed complexity analysis for Karatsuba's Algorithm, and believe me it is important. I have seen CP problems based on the application.

[yoyokojo]

Thank you! I could not bear whatch my profs dull video-lectures on this topic anymore, im happy i found someone enthusiastically explaining this by examples!

[piyushpathak]

his free course is far better than the many paid courses of some giant educational company

[raghavendrakaushik]

Great explanation,
cleared many of the queries!
thanks a lot

[juliancabezaspena]

I am having this in my algorithm class, this really helped me!!!

[roberthoffmann]

Thank you so much! Really rescued me and i like your positive vibe!

[clee]

Hey! I really appreciate your work and you've been helping me a lot throughout my studies!!! Can you please make more posts on Greedy?

[vyomchandragallani]

Very nice explanation, very nice work, and when I see detailed description of the video and in comment, really hard working man !! Keep it up ! And thank you very much for this kind of explanation 🙌🙌🙌

[davidcrowell]

(a+b)(c+d)-ac-bd (fully expands to)
ac+ad+bc+bd-ac-bd (cancelling out terms to)
ad+bc (the middle term of the upper expression)

[ericwilson]

Thank you so much. I wish my professor had watched this before attempting to teach it. Just brilliant.