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
Смотрите видео The Fastest Multiplication Algorithm онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Dr. Trefor Bazett 08 Май 2023, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 117,03 раз и оно понравилось 4.7 тысяч людям.