수학자들은 여전히 곱셈의 가장 빠른 방법을 모른다

Mathematicians still don't know the fastest way to multiply numbers

초등학교에서 배우는 곱셈 알고리즘은 O(n²)의 시간이 걸리며, 수천 년 동안 수학자들은 이것이 최선이라고 믿어왔다. 그러나 1960년, 23세의 아나톨리 카라추바가 이 믿음을 뒤집는 알고리즘을 발견했다. 카라추바 알고리즘은 곱셈을 덧셈으로 대체하여 O(n^1.585)의 시간을 달성했으며, 이는 Python과 같은 현대 소프트웨어에 통합되어 있다. 이후 2019년, David Harvey와 Joris van der Hoeven은 O(n log n) 시간에 작동하는 이론상 최고의 알고리즘을 발표했지만, 실용적으로 사용하기에는 숫자가 너무 커서 'galactic algorithm'으로 분류된다. 여전히 O(n log n)이 최적인지 증명되지 않았으며, 이는 이 분야의 성배로 남아 있다.