The Most Advanced Multiplication Algorithms: Why Karatsuba and FFT beat high-school mathematics
Вставка
- Опубліковано 5 лип 2024
- 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
Toom-Cook sounds like memed version of Tim Cook. Like Solmon Boi
Hahaha!
Karstuba... Kasturba Ji
that amortization trick was superb
Explained in a lucid manner :)
Appreaciate the efforts and enthusisiam!
Thank you!
Awesome - my brain is frying but nicely put together
Thank you 😛
🙏👍😊
Oppenheimer who?