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
Watch video The Fastest Multiplication Algorithm online without registration, duration hours minute second in high quality. This video was added by user Dr. Trefor Bazett 08 May 2023, don't forget to share it with your friends and acquaintances, it has been viewed on our site 117,032 once and liked it 4.7 thousand people.