Fast Multiplication: From Grade-School Multiplication To Karatsuba's Algorithm
ฝัง
- เผยแพร่เมื่อ 6 มี.ค. 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 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.
Update: There is O(n*log(n)) integer multiplication now: hal.archives-ouvertes.fr/hal-...
Karatsuba Multiplication On Wikipedia: en.wikipedia.org/wiki/Karatsu...
You don't need this for the interview.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech - วิทยาศาสตร์และเทคโนโลยี
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.
Update -> There is O(n*log(n)) integer multiplication now: hal.archives-ouvertes.fr/hal-02070778/document
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."
Wow Ethiopiawi neh ende ...
Keep it up bro you are incredible
my heart jumped when I heard him speak Amharic lol but loved the content. glad to have come across this channel, a new fan!
when he speaks amharic i started searching for another opened chrome tab
hahahahaha what
@@BackToBackSWE great video !!
@@abelkidanemariam6485 lol, what does it mean
@@BackToBackSWE it means he thought the video is in another language and he started looking for another one...which...he had already searched for but was in another chrome tab
Literally the same!
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!
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.
thanks, yw
how to get interview at these companies?? no one is ready to give referral and they dont even look at resume if i send them one
Thank you for this video, this greatly helped me in understanding Karatsubi algorithm which is used in my course for polynomial multiplication. Superb content!
thanks.
Thank you so much! Really rescued me and i like your positive vibe!
ye
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.
Thank you so much. I wish my professor had watched this before attempting to teach it. Just brilliant.
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.
Nice, well we have a lot to go. We are working every day to achieve our mission of giving people exceptional interview outcomes.
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!
hahahaha
Great explanation,
cleared many of the queries!
thanks a lot
great
I am having this in my algorithm class, this really helped me!!!
great yo
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?
nice, yeah
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 🙌🙌🙌
sure - thank you.
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.
Nice
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!
sure
Hey Arielle,
Where can I read about your work ?
Thanks
You are amazing man. Thank you so much for this
sure.
Best explanation of Karatsuba algorithm. Thank you very much.😊
Thank you again, Siddhant :)
Hi thank you for creating this channel really valuable material. I have a general question, am not familiar with any of the content of the channel but I am eager to learn and understand it. I am not sure what playlist to watch first and advanced my way up. It seems that it is important to build my base knowledge and to that I can't jump from one video to another but need to do it in a specific order so each topic I cover will leverage my needed knowledge for another video that dependens on it. I hope you can guide me on the order of learning this material, thx
his free course is far better than the many paid courses of some giant educational company
thanks - appreciate it
I am agree :) Tyou
(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)
nice
Excellent explanation
13:09 ad + bc can be number of length n + 1 too right ? so that will increase one addition. It should be alpha(n+1) then.
16:30 it should be 3.alpha.n according to me. Not that it will make any difference tho,.
Thank you so much John Legend!!!!
sure internet freidn
@@BackToBackSWE hell yeah my friend:)
Always, I Proud of You!!!n Thanks
thank you. your amharic is pretty good.
wowooo, i didn't expect to hear you speak amharic at the beginning. haha
When you opened the video in Arabic (I think), I was worried I wouldn’t be able to follow but would try anyway. Then you broke into English and I thought “good an instructor with a sense of humor”
Noooo!, this vid is super useful to me as a cs student. Can't thank u enough lol
great to hear.
Hey bro, I am continuously following your channel .. It will be helpful if you make more video on Graph based problem-- Find the number of islands, Snake and Ladder Problem,Minimum Cost Path with Left, Right, Bottom and Up moves allowed, etc ...
ok
I couldn't understand much because of the language difference but the graphics helped me, thanks
sorry i don't have good english
dang and ok nice - ur good
WoW! Amazing explanation 👍👍👍.
thanks
Thank you so much!
sure.
breh, you got me there at the beginning xD
Amazing explanation!:)
thx
Do not think any algorithm is too hard for an interview
Recently I interviewed for JP Morgan Chase Internship
Longest Palindromic substring
He wanted me to come up with the Manacher's algorithm
Though I gave him a DP solutions and got through the round.
that's brutal
Hey I'll try do my day to day math in this way and let you know!
Looked it up after "reading" fast doubling for Fibonacci sequence
😅በጣም እናመሰግናለን!
What! you speak my native language! Selam Selam! I really appreciate your great tutorials! Keep it up ! Gobez Anbesa!
hahaha, ay, these are the comments I was aiming to generate. Yeah both my parents are 100% Ethiopian
@@BackToBackSWE Please give my best regards to your parents. They should be proud of you! I am an international student at Du** from Ethiopia. Hope to see you one day!
@@abebe7017 nice, we may meet haha
@@BackToBackSWE i had no idea! your Amharic is pretty good, and keep up the content as it has been really helpful to me as a CS student.
Amazinggg video!
thanks
Why does the multiplication of (n/2)*(n/2) lead to n length number? We have considered a case where 99*99 would lead to 9801 (length 4). However, why did we not consider a number 10 * 10 = 100 (length 3)?
Reference: th-cam.com/video/-dfsxsiGoC8/w-d-xo.html
We are deriving an upper bound for work, 99*99 expresses that worst case. I should have been more precise, I don't remember what I said in this video exactly.
@@BackToBackSWE Thank you, that makes sense :)
Excellent pedagogy. I subscribed. However, the presentation leaves me wondering how someone can remember so much algebra while forgetting a simple language convention: that 'amount' is used with uncountable objects and 'number' is used with countable objects. "Number of levels/additions/multiplications", not "amount of levels/additions/multiplications". Now, this second quesion may show up MY ignorance. Why can't compiler optimization be more easily achieved for large-integer multiplication simply by using a stored table of logarithms broken into sections of increasing base numbers? Speaking of optimization, it took OurSewer and FireFox over a minute to post my second and fourth edited version.
This might be interesting for someone: The name 'Karatsuba' can also be spelled 'Karatuba' in Japanese Romaji (Roman letters) because the syllable 'tu' is pronounced 'tsu'. The series is pronounced /ta chi tsu te to/ instead of /ta ti tu te to/. I had a Japanese boss who said "Fu?" on the telephone instead of "Who?", because in Romaji it's /ha hi fu he ho/, the pronunciation /hu/ being impossible in Japanese.
13:13 What about the carry over to the next position after those four? We still have to add that one too, right?
The carry over additions are ignored when doing the run time analysis for this algorithm. Don't ask why.
Wow you are amazing.
Love from Bangladesh !
wassup, love from the cornfields of America 🌽🌽
@@BackToBackSWE keep teaching us! I am 15 btw, learning ds and algo on my own , u just made it easy for me, thanks!
@@asdfghjkl1770 Nice. Keep learning. Master what you do.
Holy crap, 15 is so young (I'm about to be 20).
You will be rewarded in life for being great at something economically valuable (i.e. programming and computer science understanding). (odd comment but it is kinda true)...it will serve as an entry way for you to do whatever you want later in life (I'm of course not at that point but yeah...it doesn't hurt to be really good at something valuable).
So yeah...get really really good but try to stay human and meet your human needs (like don't isolate yourself in youth like I did)
@@BackToBackSWE Thank you so much for inspiring me ! I really love the process of learning programming , I started learning "how to code" in 2018, 16th nov and fall in love with programming. in my vacation , i guess i spend more than 10 hours a day just learning and writing code probably because it was fun, it was little bit addictive i guess..... my dream is to get a job at Google, and i will make my dream come true!
@@asdfghjkl1770 Nice, I'd even aim higher. You don't just want to work somewhere, you probably have the ambition to change the world and help countless people.
You can do that anywhere, anyway you see fit. Just stay open and stay sharp. And you will do great things. We all can.
i was about to close the video after the arabic.... Thanks to my patience that i waited for an extra two seconds....
bro thanks a lot
sure, np
Well, you lost me at 24.20. I don't get how you expand ad+bc the way you do. My algebra is quite rusty, so is this expansion a known algebraic identity for example? Can anyone elaborate?
distribute and perform the subtractions and it will be clear
Great video! Watched it at 2x was super lucid still. But the dude scratching his itches at 2x wasn't smooth.
Hey, a doubt.
For multiplying 2 numbers of length 4 each you said its 4*4 time, but for multiplying 2 n/2 length numbers, why you added them and said its n time? Why not n^2/4?
can you timestamp it? I made this video a while back so dont remember ti all
@@BackToBackSWE My bad, I got it now. Thanks for the super prompt reply!
@@rishabhgarg4942 oh, sweet
Was so scared for the first few seconds LMAO
why
I don't understand. Why is 2an ( 1an + 1an)? who can explain it help me?. Thank you!
I dont remember the math to be honest shot this a while back
@@BackToBackSWE I have understood it. Example x = 1234 => x1 = 12, x2 = 34 and y = 1234 => y1 = 12, y2 = 34
10^4*x1y1 + 10^2(x1y2 + y1x1) + x2y2. I saw that x1y2 + y1x1 is 1an ( a is addition)
10^4*x1y1 and x2y2 => xxxx0000 ( x1 = n/2, y1 = n/2 => x1y1 xxxx) then I only join xxxx0000 with x2y2 => xxxxxxxx then plus 10^2(x1y2 + y1x1)
So xxxxxxxx then plus 10^2(x1y2 + y1x1) is 1an ( a is addition) and x1y2 + y1x1 is 1an ( a is addition)
So We have 2an :) :)
But What is Big O of this math?
awesome
hey
About 10 days after this video was published, an n*log(n) algorithm was discovered!
Can you share source
@@justcode7326 Just Google for integer multiplication in time O(nlogn)
you can speak Amharic ?
You had me man....hahaha
at 5:50 i was like.. gotcha
thank goodness i skipped 20 minutes and saw algebra that i am miserable at learning now i know to close the tab and hate myself
..uh
Back To Back SWE my attempt at dark humor
@@user-oo2gz9ln8v ye
it is not useless... lol im being homeworked about this for a class.
nice
Me bouta use this for programming to make speedy calculator n stuff B)
great lol
lmfaoo finally a brother
It's my, as in mü MY NY XI
I need to learn math again
Is that Amharic language ?
yeah lol my bad
@@BackToBackSWE nice language. I traveled to Adis multiple times and love it.
"You probably won't use this".... unless its on a 351 exam ;)
hahahahaha, yeah, I'm sharp ✏️✏️
What a WASTE OF TIME... I found another site that just did an example multiplication without all the Math double talk...this was impossible to follow. I'll never come back here again.
ok, bye
i will just choose n^2....
wut
brrrraaaahhhhhhhhhhhh
thanks a lot
new dimension unlocked
Happy 2023! Really glad to help 🎉 Do you know about our 5 Day Free DSA Mini Course? Check it out here - backtobackswe.com/
Oh my god, this guy speaks Amharic! Are you habeshan?
wassup
I like your videos!
@@nebiyuelias1 thx
bro you scared me
Its not useless
Pity you haven't demonstrated
Content is nice but adds on adds are irritating!!
How much did this video cost
why is it 3 multiplications? aren't the only multiplications you do are a*c and b*d?
For karatsuba? Karatsuba has 3 since we re-expressed the middle term. We re-expressed it into an expression that is the multiplication of 2 addition statements.
@@BackToBackSWE ah okay i see, thanks. also to confirm, an atomic multiplication/addition is simply the time it takes for a computer to do a basic multiplication/addition, so does that mean it's more or less the time a computer would take to multiply 2 one digit numbers?
@@yoshi4980 yeah, single digit multiplication or addition
Whiteboard : Am i a joke to you
hahahahahahahaa
ere besmam ethiopiaw neh asdenegetikegn
Hahahaha, I'm sorry for having scared you.
@@BackToBackSWEename geremegn
@@bisratmesfin9546 hahaha, Ethiopian squad out here
I did Computer Science to get away from math and here we are again smh... ** cries in math **
የዚ ግንባር ሚስጥር ተፈታ ለካ ሃበሻ ነህ lol
Hahahaha nice joke
my b