이진 거듭제곱
이진 거듭제곱은 지수를 이진수로 분해하여 반복 제곱으로 거듭제곱을 계산한다 빠른 거듭제곱 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.
| 분류 | 알고리즘 · 빠른 거듭제곱 |
|---|---|
| 핵심 문제 | 지수를 이진수로 분해하여 반복 제곱으로 거듭제곱을 계산한다 |
| 방법 | 결과를 항등원으로 시작하고 지수가 홀수이면 현재 밑을 곱한 뒤 밑을 제곱하고 지수를 절반으로 줄인다 |
| 계산 비용 | 곱셈 횟수 O(log n), 반복 구현 보조 O(1) |
| 적용 조건 | 연산의 결합법칙과 항등원, 지수 범위가 필요하다 |
| 관련 활용 | 모듈러 거듭제곱·행렬 거듭제곱·빠른 피보나치 계산에 쓰인다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
이진 거듭제곱은 지수를 이진수로 분해하여 반복 제곱으로 거듭제곱을 계산한다 빠른 거듭제곱 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 결과를 항등원으로 시작하고 지수가 홀수이면 현재 밑을 곱한 뒤 밑을 제곱하고 지수를 절반으로 줄인다. 결합법칙이 있는 연산에 적용할 수 있다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 곱셈 횟수 O(log n), 반복 구현 보조 O(1) 적용 전제는 연산의 결합법칙과 항등원, 지수 범위가 필요하다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 모듈러 거듭제곱·행렬 거듭제곱·빠른 피보나치 계산에 쓰인다. 중간 곱 오버플로·모듈러 규칙을 고려한다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]