ps:거듭제곱의_빠른_계산
거듭제곱의 빠른 계산 (Exponentiation by squaring)
- 어떤 수의 n제곱을 분할 정복을 이용해서 O(logn)에 계산하는 방법.
- 위키피디아에 따르면 Exponentiation by squaring 라는 이름 말고도 square-and-multiply 알고리즘이나 binary exponentiation 등으로도 불린다고 한다. cp-algorithm 에서는 binary exponentiation 으로 소개하고 있다.
- 아이디어는 간단하니 위의 링크 참조.
- 구현은 재귀로 구현하는 것과 반복문으로 구현하는 것 둘다 간단하게 구현가능하지만 파이썬에서는 일반적인 수에 대해서는 내장 pow()가 이미 이 방식으로 구현되어 있으니 (mod까지 제공한다) 직접 구현할 일은 없다.
- 하지만 그냥 스칼라값이 아닌 다른 타입에 대해서 N제곱을 구해야 하는 경우에는 직접 구현해줘야 한다.
- 대표적인 경우는 행렬의 N제곱이다. 행렬의 N제곱이 필요한 경우가 종종 있는데, 그 중 한가지는 상태전이를 행렬로 만들어서 n번 전이된 상태를 계산하는 형태의 DP이다. 동차 선형 점화식의 n번째 항을 계산하는 경우에도 이 방법을 쓴다.
- 다른 사용예로는 다항식을 N제곱해야 해야 하는 경우가 있다. FFT와 같이 쓰인다.
- 직접 구현할 때에는 재귀가 아닌 반복문을 사용해서 구현하자.
- 파이썬 기준 구현 팁은 2로 계속 나누면서 나머지가 1일때만 곱해주는 로직을, 그냥 divmod로 그냥 나눠서 계산하거나, 비트연산으로 계산하거나 하는 방법보다도, bin()함수로 2진수 문자열을 얻은다음에 i번재 문자가 '0'인지 '1'인지를 비교하는게 가장 빠르다;
- teflib.matrix.matpow 에 구현되어 있다.
관련 문제
ps/거듭제곱의_빠른_계산.txt · 마지막으로 수정됨: 2023/02/13 08:15 저자 teferi
토론