How can we multiply large integers quickly? (Karatsuba algorithm) - Inside code
Ғылым және технология
Source code: gist.github.com/syphh/0df7faf...
🔴 Learn graph theory algorithms: inscod.com/graphalgo
⚙ Learn dynamic programming: inscod.com/dp_course
💡 Learn to solve popular coding interview problems: inscod.com/50problems_course
⌛ Learn time and space complexity analysis: inscod.com/complexity_course
🔁 Learn recursion: inscod.com/recursion_course
NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent
I also post content on LinkedIn (inscod.com/linkedin) and Instagram (inscod.com/instagram)
Пікірлер: 161
Discover the new graph theory algorithms course: inscod.com/graphalgo 🔴 / \ 🔵-🔴 | | 🔴-🔵
I believe there's a typo at 6:01 - the fifth line should say "(a+b)(c+d)-ac-bd"
Jeez, you explain this very well. You don’t explain material in a generic way. Also, I love the animation.
@insidecode
2 жыл бұрын
Oh thanks a lot!
this is a very well done video, the animation and the color palate are really smooth and the explanation is clear as day.
Great platform and very helpful!! Keep Going! One of the rare channels which explain algorithm design in such depth...
this is a very well done video, the animation and the color palate are really smooth and the explanation is clear as day. Subscribed.
@insidecode
2 жыл бұрын
Thanks a lot for your comment!
amazing explanation,short and brief...made the concept easy for me. thanks 😍
This is amazing!! I learnt so much not just about the algorithm, but key concepts like merge sort, masters method and more. I'm waiting for the day you blow up 🔥 def sending this one to my friends
@insidecode
2 жыл бұрын
Amazing! Thanks for the comment and the support
Great explanation ! Underrated 100%
Best explanation of karatsuba algorithm.
Exactly what I was looking for Thanks !
Fantastic and easy to understand tutorial! Just want to point out that the last line of code might not work in the case of an odd number of digits, since you calculate half with n//2.
Very well done video. I appreciate the care and quality.
thank you!! best explanation of the concept imo
One minor thing that is missing here is how to Actually calculate big numbers that don't fit regular programming primitives as Int or Double
Thank you for this video. Keep growing. It would be so great if in future you plan on making a course on data structures & algorithms- would probably be something to watch out for whenever computer geeks open youTube.
@insidecode
2 жыл бұрын
Thanks for your suggestions
Some feedback about calculating the time complexity you say, the return statement has complexity O(n) but if you observe closely, the whole return statement is filled with O(1) operations, I think the function "ad_plus_bc" has complexity of T(n/2)+O(n), because it has a subtraction operation, subtracting/adding has complexity of O(n) The overall expression of complexity is correct. T(n) = 3T(n/2) + O(n) + O(1), where O(1) can be ignored in the presence of O(n)
Apart from good explanation. The entire presentation is also so satisfying and I can see u put a lot of work behind it. Do more of them we will keep supporting you sir.
@insidecode
2 жыл бұрын
Thanks a lot!
this video saved my life! thanks
This is some high quality material. Really appreciate it.
@insidecode
2 жыл бұрын
Thanks a lot!
Brilliant video. Thank you so much
thanks for the video explaination. also, note that 1.58 is read as one point five eight, not one point fifty eight.
Hi, PLEASE create more videos like this and Also add videos to playlist for easy lookup. Really appreciate it. Algo/problems related to Data science would be great as well.
@insidecode
2 жыл бұрын
Thanks for your suggestion!
Amazingly clear
Just wow! Thanks man... Keep up the good work!
@insidecode
2 жыл бұрын
You're welcome!
teaching can't be better. thank you.
Great explanation, Thank you
With quantum computer memories sometime in the future, if read only quantum memories could be invented, then huge indexed table could be used for instantaneous results. For single value function like trig functions, read only index tables would have advantage of single clock speed and absolute accuracy, as it is my understanding that different approximations have needed accuracy for only portions of the number space.
great explanation thanks alot for saving the day
Brilliant explaination
This tip seems very helpful. Thank you for sharing
@insidecode
2 жыл бұрын
You're welcome!
amazing explaination bro!
Amazing explanation
Never knew about this,might come in handy Thanks :)
@insidecode
2 жыл бұрын
You're welcome!
Thank you this is so helpful :)
I never knew that there is another algorithm to multiply. Thanks for increasing my knowledge 😍😍🥰🙏✌️
@insidecode
2 жыл бұрын
You're welcome!
Subscribed Sir,Amazing work
Ur explanation is very clear i hope to make more videos about unknown topics in computer science well done bro .
@insidecode
2 жыл бұрын
Thankss
@BELLAOUAR_Mahmoud
2 жыл бұрын
@@insidecode u deserve more .
Thank you!!
informative, thanks
beautiful ty
wow this helped so much thanks youuuu!!!!
@insidecode
Жыл бұрын
You're welcome!
fascinating!
Thx a lot
Nice man 👍 keep up the good work
@insidecode
2 жыл бұрын
Thanks!
very great explanation!
@insidecode
2 жыл бұрын
Thanks!
thanks
hey amaizing video but i dont get it why in the time complexity calaculate the sum require o(n) it all sum why not o(1)? i mean at 8:20 at the below statement ?
Great content. Thank you
@insidecode
2 жыл бұрын
You're welcome!
wow , its always worth watching
@insidecode
2 жыл бұрын
Thanks!
This is helpful .. Thumbs up!
@insidecode
2 жыл бұрын
Thanks!
nice job
Aw this is amazing
very helpful video, thanks heaps
@insidecode
2 жыл бұрын
You're welcome!
Amazing Video!
@insidecode
2 жыл бұрын
Thanks!
This channel only need playlist clarification and it is perfect!
@insidecode
2 жыл бұрын
I'll make playlists then
@jeffbezos3942
2 жыл бұрын
@@insidecode Thank you!
@insidecode
2 жыл бұрын
@@jeffbezos3942 You're welcome!
Amazing
Really really useful
@insidecode
2 жыл бұрын
thanks!
Hi bro, that's realy high quality content I love ❤❤❤❤❤❤❤your accent daaam. Keep doing, Love from India🇮🇳🇮🇳.
@insidecode
2 жыл бұрын
Thanks a lot man
I was wondering from some time ago if Toom-4 is equivalent with Karatsuba , from a complexity point of view, but that looks a bit impossible. Lately , I was able only to come with this. Considerring Toom-4 and also Toom-4 added those two terms multiplications (the ones from middle ), which are more like K-idea, only with two more multiplication comparing too Toom-4. (so we got 4+3 vs 4+5 complexity dilema). those 5 multiplications terms computed are all following some simple rule for product of 2 coetients and other 2, no matter which one of the 5 mult term we chose. So we might be able to reach to the conclusion that we can find the method Florin-4, Florin-8, etc, no so sure about its complexity thow so this may be just some joke offered by me to anyone wish to verify its complexity. Thank You, I like these style of videos on KZread! ^_^ P.S. digging this out i was needed to reformulate the K-idea , both with Toom one, by switching from geometric progressions to something more oriented on adds n diffs instead coetient products that looks the same to diffs that look the same. But this is a bit too complex to me, a bit hard to get the job done, need meds 2 times a day in any case, I mean only to be able to put these here, for example. Thank You! :-)
@mehdididit
2 жыл бұрын
Mucho texto
@florinmatei8846
2 жыл бұрын
@@mehdididit I agree, I talk too much since I know myself >
@florinmatei8846
2 жыл бұрын
@@mehdididit Alrite, here some more nonsense, that might worth some translation 🙂 consider ca in mod normal, logica de tip chat bot sau click programming / logic explorer, pentru utilizatori incepatori din gimnaziu/liceu ar cam trebui sa mearga binisor, ma gandesc ca macar atata pedagogie cibernetica ar cam trebui sa se gaseasca pe lume, spre exemplu la programarea in basic, sa ofere pe post de "mutare" din partea computerului, cateva optiuni pentru urmatoarea nstructiune de inserat , doar cu un click, in viitorul mic cod sursa al rutnei respective, provocarea fiind ca la per total, aplicatia gen logic explorer sa ma arate a ceva. Multumesc frumos!
thank u a lot bro .... best video ;)
@insidecode
2 жыл бұрын
You're welcome!
Beautiful!
@insidecode
2 жыл бұрын
Thank you!
An algo optimisation idea that can be inspired by the hardware predication techniques, applied to soft data numbers to be multiplied, arraies to be multiplied, others may too, I think that may give us something to think about. Never tested nor verified by me, sorry! :-)
awesome man immediately subscribe to your channel
@insidecode
2 жыл бұрын
Thanks!
Fantastic as usual! May I ask what program you use to do your videos?
@insidecode
2 жыл бұрын
Thanks! I make the slides with PowerPoint
@eriklonnrot9313
2 жыл бұрын
Hahahahaha i was expecting some rare program, thats amazon amazon slides bro. Keep it simple
How do we do this if we have odd lengths of numbers?
Thank u sir
@insidecode
2 жыл бұрын
You're welcome!
How to solve it using array by storing two numbers in 1D array with help of 2D array
The best channel
@insidecode
2 жыл бұрын
Hey thanks!
goated video
How does this work IN PRACTICE for standard 64 bit binary machines? Is there REALLY a savings? Or are much larger numbers (256 bit) needed for a practical improvement? Has this ever actually been implemented into processor microcode? If so, how did it work out?
@kwanarchive
2 жыл бұрын
According to Wikipedia, at least 320-640 bits.
nice man
@insidecode
Жыл бұрын
Thanks for watching!
His speech melody tells 'it's all very simple, seeee?' - My brain sounds drop to 40hz.
you are super awesome
@insidecode
2 жыл бұрын
Thanks!
Need more such
@insidecode
2 жыл бұрын
The next videos will all be about CS algorithms!
سبحان الله والله عرفت accent تعك دزيرية 😂 Anyways, thanks for the information it was really helpful, keep going 💜💜
@insidecode
2 жыл бұрын
You're welcome kho
thanks a loot
I wrote a code similar to this but while running it for inputs of 8 digits and more, I'm getting recursion max depth reached error. Any idea how to solve this?
@insidecode
2 жыл бұрын
Very your base cases, make sure the code is stopping at some point, try to print the parameters to see where it's stuck
@tastes-like-straberries
2 жыл бұрын
@@insidecode yes thanks! I figured out the issue
@insidecode
2 жыл бұрын
You're welcome!
cool ♣
It should be (a+b)(c+d) and you solved for that only but you have written (a+c)(b+d) at 6:10
@insidecode
2 жыл бұрын
Yup that's true thanks for mentioning it
is there another way to get 3 multiplications?
I can't understand why we store n // 2 in the variable half , I know it gives a wrong answer if we don't do that but why ?
@insidecode
2 жыл бұрын
Technically you don't need to do it, you can write n//2 everywhere but using a variable gives a more understandable code
Pardon me but i m still confused how does exactly it reduces the time complexity than the old way, i see a lot of arithmetic in this method too?
@KahHongTan
2 жыл бұрын
The trick is the part at 3:26. Divide and conquer works only if breaking a problem down and dealing with the sum of those smaller chunks is easier. It might not be, you might just end up with many small problems which added up is still the same problem. This is the case if you split two numbers you want to multiply, now you have twice the number of multiplications of integers half the original size. Split again, now 4 times the number of multiplications with integers of a quarter size. Same problem. But here, whenever you split two integers there's 3 new multiplications instead of 4. So you get to split the integers in half without doubling the multiplications needed.
u da goat no bap
I have a fat expensive algorithm book in my hand that could not even explain how x became a*10^(n/2) + b. Yet it only took you 10 seconds to explain it...
When I was in university I was assigned to implement this algorithm, and I struggled to understand it.
gooddddd
Nice video but i don t understand why do we need this. Cant we just multiply the numbers? Initially i thought that the method will be for that numbers that when are multiplied are giving a very large number that doesn t fit into long long or double.
@insidecode
Жыл бұрын
It's not about overflow because because we could use strings instead anyway, it's about the method we use to actually multiply the numbers. For small numbers we can use the brute force method we all know, but for big numbers, it's better to use the Karatsuba algorithm because it's faster
@Fred2-123
Жыл бұрын
It is for numbers that have hundreds of digits. Think about numbers like the number of nanoseconds since Jan 1, 1492. Or pi to the 100'th decimal place. On a 32 bit machine, what if you need to multiply two 14-digit numbers.
PayPal link for paying back for this amazing explanation?
That algorithm is used to multiply big Matrix right?
@insidecode
2 жыл бұрын
just integers, maybe you're talking about Chain matrix multiplication?
@arquier
2 жыл бұрын
@@insidecode yes, looks like it can be applied on that case too
Why calculating the result takes O(n)?
@sethdon1100
Ай бұрын
Addition digit by digit is an O(n) for n digits
This begs to be a homework problem in recursive LISP. Using binary numbers. LOL
Calculator was made for the math💀💀
Did not understand why there's O(n) ? All the operations are O(1)
@sethdon1100
Ай бұрын
Additions
I don't get it, why n is 2?
@insidecode
2 жыл бұрын
Where did you see that n is 2?
If you talked a bit slower and clearer would be a 10/10
How u got 5,8
@insidecode
2 жыл бұрын
In the code, you can see that we're recursively calling the function thrice, once to calculate a*c, once to calculate b*d, and once to calculate (a+b)*(c+d). And in the node where we calculate 14*35, splitting the two numbers into two parts give us a=1, b=4, c=3, and d=5. So 5,8 comes from the fact that we want to calculate (a+b)*(c+d), which is (1+4)*(3+5), which is 5*8
@eternalthoughts3778
2 жыл бұрын
@@insidecode thank you for your patience,I never expected u will reply comments
@insidecode
2 жыл бұрын
@@eternalthoughts3778 haha why wouldn't I?
any uetian present
that doesn't look quicker or simpler
@insidecode
2 жыл бұрын
It's quicker for large numbers, Karatsuba algorithm has an O(n^1.58) time complexity while the brute force method has an O(n²) complexity
Avik ims pimro whatever you teamch