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

Опубликовано: 08 Ноябрь 2023
на канале: Gaurav Sen

4,888

147

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: https://interviewready.io/
Karatsuba: https://en.wikipedia.org/wiki/Karatsu...
Toom-Cook: https://en.wikipedia.org/wiki/Toom%E2...
FFT: https://en.wikipedia.org/wiki/Sch%C3%...

You can follow me on:
Github: https://github.com/InterviewReady/sys...
Twitter: / gkcs_

#SystemDesign #InterviewReady #Coding