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/...

COURSE PLAYLISTS:
►DISCRETE MATH:    • Discrete Math (Full Course: Sets, Log...  
►LINEAR ALGEBRA:    • Linear Algebra (Full Course)  
►CALCULUS I:    • Calculus I (Limits, Derivative, Integ...  
► CALCULUS II:    • Calculus II (Integration Methods, Ser...  
►MULTIVARIABLE CALCULUS (Calc III):    • Calculus III: Multivariable Calculus ...  
►VECTOR CALCULUS (Calc IV)    • Calculus IV: Vector Calculus (Line In...  
►DIFFERENTIAL EQUATIONS:    • Ordinary Differential Equations (ODEs)  
►LAPLACE TRANSFORM:    • Laplace Transforms and Solving ODEs  
►GAME THEORY:    • Game Theory  

OTHER PLAYLISTS:
► Learning Math Series
   • 5 Tips To Make Math Practice Problems...  
►Cool Math Series:
   • Cool Math Series  

BECOME A MEMBER:
►Join:    / @drtrefor  

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

SOCIALS:
►Twitter (math based):   / treforbazett  
►Instagram (photography based):   / treforphotography