#multiplication#karatsuba#harvey-hoeven
35K subscribers • 1 video on Hallway
Intermediate. Assumes working knowledge.
3.1K views6 years ago1 recommendation
Computer scienceAlgorithmsComputation and complexityMath for programmers
How computer scientists optimized multiplication algorithms, culminating in the O(n log n) complexity breakthrough.
You probably learned how to do long multiplication by hand in school. Computers used *the same algorithm* to multiply large numbers together, until computer scientists discovered much, much faster methods, including one published this year that's "perfect!" - Links for the Curious- THUNK Discord! - discord.gg/YHVjeSk Mathematicians Discover the Fastest Way to Multiply, by Kevin Hartnett - quantamagazine.org/mathematicians-discover-the-perfect-way-t… Integer multiplication in time O(n log n) (Harvey & Hoeven, 2019) - hal.archives-ouvertes.fr/hal-02070778/document Polynomial multiplication over finite fields in time O(n log n) (Harvey & Hoeven, 2019) - texmacs.org/joris/ffnlogn/ffnlogn.html David Harvey’s personal Q&A about the paper - web.maths.unsw.edu.au/~davidharvey/research/nlogn/index.html The Complexity of Computations (Karatsuba, 1995) - ccas.ru/personal/karatsuba/divcen.pdf Fast multiplication of large numbers (Schönhage & Strassen, 1971) - link.springer.com/article/10.1007%2FBF02242355 Multiplying 41*37 with Fast Fourier Transform by hand - youtube.com/watch?v=YDhsLhTK3Bs 3. Divide & Conquer: FFT, by MIT OpenCourseware - youtube.com/watch?v=iTMn0Kt18tg Mathematicians may have found the fastest way to multiply huge numbers, by Emily Conover - sciencenews.org/article/mathematicians-may-have-found-fastes…What people say. Recommended as an accessible overview of multiplication methods and the quest for mathematical optimization.
u/NotExecutablein r/programming • Recommends
On “Mathematicians Discover the Perfect Way to Multiply | WIRED”