퓌러 알고리즘

퓌러 알고리즘(Fürer's algorithm)은 스위스 수학자 마르틴 퓌러(Martin Fürer)가 발표한 정수를 빠르게 곱하는 알고리즘으로, ${\displaystyle N}$자리 정수 두 개를 ${\displaystyle O\left(n\log n\ \cdot 2^{O(\log ^{*}n)}\right)}$시간에 곱할 수 있다. 여기서 log*n은 반복 로그이다.

2007년에 만들어졌으며, ${\displaystyle O(N\log N\log \log N)}$시간에 두 정수를 곱할 수 있는 쇤하게-슈트라센 알고리즘을 훨씬 능가하였다. 그러나 ${\displaystyle 2^{2^{64}}}$보다 큰 수에서 복잡도나 속도가 더 빨라지고, 2019년 3월에는 이 알고리즘보다 더 개선된 곱셈 알고리즘이 등장해 아주 큰 두 수를 ${\displaystyle O(n\log n)}$시간 안에 곱할 수 있게 되었다.

이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.