The Fastest Multiplication Algorithm

Keep exploring at ► https://brilliant.org/TreforBazett. Get started for free for 30 days — and the first 200 people get 20% off an annual premium subscription!

How can you multiply two enormous numbers? We all learn an approach in school which has n^2 total multiplications by single digit numbers. The first improvement was the Karatsuba Algorithm which uses a divide and conquer approach and a bit of clever algebra to reduce 4 multiplication to 3 (in 2x2 case) and more generally to about n^1.58 multiplications asymptotically. For a computer with a 32-bit hardware multiplier, one can iteratively apply the approach until the numbers are within the size of the multiplier. Toom-Cook is a generalization of the Karatsuba Algorithm and is useful in various cryptography applications, but a real change happened with Schonhage-Strassen which use discrete fast fourier transforms to get to O(n log n log log n) complexity, used for applications like the Great Internet Mersenne Prime search. The theoretical best result is Harvey and Hoeven who achieved O(n log n), albeit this becomes more efficient for only impractically large numbers.

0:00 Review of normal multiplication
1:42 The Karatsuba Algorithm for 2x2
3:32 Example of Karatsuba
4:34 Karatsuba for larger numbers
5:45 Complexity of Karatsuba for size 2^k
7:09 Computer architecture and hardware multipliers
8:26 Newer algorithms (Schonhage-Strassen, and Harvey and Hoeven)
12:46 Brilliant.org/TreforBazett

Check out my MATH MERCH line in collaboration with Beautiful Equations
►https://beautifulequations.net/pages/trefor

COURSE PLAYLISTS:
►DISCRETE MATH: https://www.youtube.com/playlist?list=PLHXZ9OQGMqxersk8fUxiUMSIx0DBqsKZS
►LINEAR ALGEBRA: https://www.youtube.com/playlist?list=PLHXZ9OQGMqxfUl0tcqPNTJsb7R6BqSLo6
►CALCULUS I: https://www.youtube.com/playlist?list=PLHXZ9OQGMqxfT9RMcReZ4WcoVILP4k6-m
► CALCULUS II: https://www.youtube.com/playlist?list=PLHXZ9OQGMqxc4ySKTIW19TLrT91Ik9M4n
►MULTIVARIABLE CALCULUS (Calc III): https://www.youtube.com/playlist?list=PLHXZ9OQGMqxc_CvEy7xBKRQr6I214QJcd
►VECTOR CALCULUS (Calc IV) https://www.youtube.com/playlist?list=PLHXZ9OQGMqxfW0GMqeUE1bLKaYor6kbHa
►DIFFERENTIAL EQUATIONS: https://www.youtube.com/playlist?list=PLHXZ9OQGMqxde-SlgmWlCmNHroIWtujBw
►LAPLACE TRANSFORM: https://www.youtube.com/playlist?list=PLHXZ9OQGMqxcJXnLr08cyNaup4RDsbAl1
►GAME THEORY: https://www.youtube.com/playlist?list=PLHXZ9OQGMqxdzD8KpTHz6_gsw9pPxRFlX

OTHER PLAYLISTS:
► Learning Math Series
https://www.youtube.com/watch?v=LPH2lqis3D0&list=PLHXZ9OQGMqxfSkRtlL5KPq6JqMNTh_MBw
►Cool Math Series:
https://www.youtube.com/playlist?list=PLHXZ9OQGMqxelE_9RzwJ-cqfUtaFBpiho

BECOME A MEMBER:
►Join: https://www.youtube.com/channel/UC9rTsvTxJnx1DNrDA3Rqa6A/join

MATH BOOKS I LOVE (affilliate link):
► https://www.amazon.com/shop/treforbazett

SOCIALS:
►Twitter (math based): http://twitter.com/treforbazett
►Instagram (photography based): http://instagram.com/treforphotography