퓌러 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''퓌러 알고리즘'''(Fürer's algorithm)은 스위스 수학자 [[마르틴 퓌러]](Martin Fürer)가 발표한 [[정수]]를 빠르게 [[곱셈|곱하는]] [[알고리즘]]으로, <math>N</math>자리 정수 두 개를 <math style="vertical-align:-15%">O \left(n \log n\ \cdot 2^{O(\log^* n)} \right)</math>[[시간복잡도|시간]]에 곱할 수 있다.  여기서 {{nowrap|{{log-star}}''n''}}은 [[반복 로그]]이다.

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

{{수론 알고리즘}}
{{토막글|컴퓨터 과학}}

[[분류:컴퓨터 산술 알고리즘]]
[[분류:곱셈]]