Uploaded November 2019 | Updated September 2026, 1 week ago
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-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) - 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) - 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-fastest-way-multiply-huge-numbers
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-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) - 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) - 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-fastest-way-multiply-huge-numbers
