The Most Advanced Multiplication Algorithms: Why Karatsuba and FFT beat high-school mathematics

For folks interested in multiplication algorithms (turns out this is a big deal in computer science and math).
1. High school method - O(n^2)
2. Karatsuba - O(n^1.58)
3. Toom-Cook - O(n^1.46)
4. FFT - O(n*log(n)*log(log(n)))
The last algorithm is pretty complex. We explain the intuition behind it in this video.
00:00 Who should watch this?
00:18 Example Problem
01:23 Karatsuba Algorithm
02:38 Time complexity analysis
03:57 Toom-Cook Algorithm
04:48 Problem - Polynomial Multiplication
05:27 Plotting points on a graph
05:57 Plotting nth degree curve
07:00 Multiplication Strategy
07:28 Optimisation Strategy
08:50 Choosing the right points
09:25 Complex Numbers!
10:26 The nth roots of unity
12:56 The impact of complex numbers
14:57 FFT Conclusion
15:52 Thank you!
InterviewReady: interviewready.io/
Karatsuba: en.wikipedia.org/wiki/Karatsu...
Toom-Cook: en.wikipedia.org/wiki/Toom%E2...
FFT: en.wikipedia.org/wiki/Sch%C3%...
You can follow me on:
Github: github.com/InterviewReady/sys...
Twitter: / gkcs_
#SystemDesign #InterviewReady #Coding

[@ananyagupta1409]

that amortization trick was superb

[@abhis3kh]

Awesome - my brain is frying but nicely put together

[@gkcs]

Thank you 😛

[@rishitgupta2050]

Explained in a lucid manner :)
Appreaciate the efforts and enthusisiam!

[@gkcs]

Thank you!

[@vinit.khandelwal]

Toom-Cook sounds like memed version of Tim Cook. Like Solmon Boi

[@gkcs]

Hahaha!

[@RishiRajxtrim]

Karstuba... Kasturba Ji

[@RishiRajxtrim]

🙏👍😊

[@MohammedThavafMT]

Oppenheimer who?