카라추바 알고리즘
카라추바 알고리즘은 큰 정수를 두 부분으로 나누어 4회의 부분 곱셈 대신 3회의 부분 곱셈으로 결과를 구한다 큰 정수 곱셈 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순...
| 분류 | 알고리즘 · 큰 정수 곱셈 |
|---|---|
| 핵심 문제 | 큰 정수를 두 부분으로 나누어 4회의 부분 곱셈 대신 3회의 부분 곱셈으로 결과를 구한다 |
| 방법 | x=a·B^m+b, y=c·B^m+d로 나누고 ac, bd, (a+b)(c+d)를 계산하여 가운데 항 ad+bc를 복원한다 |
| 계산 비용 | 점화식 T(n)=3T(n/2)+O(n), 시간 O(n^log₂3)≈O(n^1.585) |
| 적용 조건 | 자리 분할과 중간 결과·부호·진법을 정확히 관리해야 한다 |
| 관련 활용 | 큰 정수 곱셈 구현에서 학교식 O(n²) 방법보다 큰 입력에 유리할 수 있다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
카라추바 알고리즘은 큰 정수를 두 부분으로 나누어 4회의 부분 곱셈 대신 3회의 부분 곱셈으로 결과를 구한다 큰 정수 곱셈 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 x=a·B^m+b, y=c·B^m+d로 나누고 ac, bd, (a+b)(c+d)를 계산하여 가운데 항 ad+bc를 복원한다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 점화식 T(n)=3T(n/2)+O(n), 시간 O(n^log₂3)≈O(n^1.585) 적용 전제는 자리 분할과 중간 결과·부호·진법을 정확히 관리해야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 큰 정수 곱셈 구현에서 학교식 O(n²) 방법보다 큰 입력에 유리할 수 있다. 작은 입력은 단순 곱셈으로 전환한다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]