쇤하게-슈트라센 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''쇤하게-슈트라센 알고리즘'''(Schönhage–Strassen algorithm)은 두 [[정수]]를 매우 빠르게 [[곱셈|곱할 수 있는]] [[알고리즘]]으로, <math>n</math>자리 정수 두 개를 <math>O(n \cdot \log n \cdot \log \log n)</math>[[시간복잡도|시간]]에 곱할 수 있다. 이 알고리즘은 1971년에 등장하여 [[카라추바 알고리즘]]과 [[톰-쿡 알고리즘]]을 능가하였고, 2007년에 [[퓌러 알고리즘]]이 등장하기 전까지 두 개의 정수를 곱할 때 쓰이던 가장 빠른 알고리즘이었다. [[고속 푸리에 변환]]을 재귀적으로 사용하며, 여기에 약간의 기술을 추가하여 두 수를 곱하는 알고리즘이다.

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

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