The Fastest Multiplication Algorithm @DrTrefor
The Fastest Multiplication Algorithm  @DrTrefor
Uploaded May 2023 | Updated November 2026, 19 hours ago
Keep exploring at ► 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
►beautifulequations.net/pages/trefor

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

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

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

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

SOCIALS:
►Twitter (math based): twitter.com/treforbazett
►Instagram (photography based): instagram.com/treforphotography
The Fastest Multiplication AlgorithmThis Infinite Integral Tower Actually Converges? Sorta...The surprising patterns found in prime numbersThe Math Behind Climate Models (in 4 levels of complexity)This paradox is weird.The Bernoulli Equation // Substitutions in Differential EquationsWhat does equal actually mean?How to Compute a FOURIER SERIES // Formulas & Full ExampleHigher Order Constant Coefficient Differential Equations: y+y=0 and y-3y+3y-y=0Can ChatGPT reason mathematically?Solving the Gaussian Integral the cool wayEvery proof technique except actually proving it
Dr. Trefor Bazett |

The Fastest Multiplication Algorithm

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER