178. Multiplication Menagerie

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!”

Audio Version MP3

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 Harveys 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 (Schnhage & 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

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

← Back to Episodes