178. Multiplication Menagerie | THUNK
Channel: THUNK
Date: 2019-11-20

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! - https://discord.gg/YHVjeSk

Mathematicians Discover the Fastest Way to Multiply, by Kevin Hartnett - https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/ 

Integer multiplication in time O(n log n) (Harvey & Hoeven, 2019) -
https://hal.archives-ouvertes.fr/hal-02070778/document 

Polynomial multiplication over finite fields in time O(n log n) (Harvey & Hoeven, 2019) - https://texmacs.org/joris/ffnlogn/ffnlogn.html 

David Harvey’s personal Q&A about the paper - https://web.maths.unsw.edu.au/~davidharvey/research/nlogn/index.html 

The Complexity of Computations (Karatsuba, 1995) - http://www.ccas.ru/personal/karatsuba/divcen.pdf 

Fast multiplication of large numbers (Schönhage & Strassen, 1971) - https://link.springer.com/article/10.1007%2FBF02242355 

Multiplying 41*37 with Fast Fourier Transform by hand - https://www.youtube.com/watch?v=YDhsLhTK3Bs 

3. Divide & Conquer: FFT, by MIT OpenCourseware - https://www.youtube.com/watch?v=iTMn0Kt18tg 

Mathematicians may have found the fastest way to multiply huge numbers, by Emily Conover - https://www.sciencenews.org/article/mathematicians-may-have-found-fastest-way-multiply-huge-numbers