Binary Exponentiation
Binary exponentiation (또는 제곱하는 거듭제곱으로 알려진)은 O(log n)의 곱만을 사용하여 a^n을 계산해도록 하는 trick이다 (naive approach에 의해 요구되는 O(n) 곱 대신에)
그것은 연산과 관련 없이 많은 곳에 중요한 적용을 할 수 있는데, 결합법칙을 가진 어떤 연산과 함께 사용될 수 있기 때문이다:
(X ᐧ Y) ᐧ Z = X ᐧ (Y ᐧ Z)
이것은 modular multiplication, 행렬 곱, 우리가 아래에서 이야기할 다른 문제들에 가장 명백히 적용된다.
Algorithm
a를 n의 지수승으로 하는 것은 간단하게 a를 n - 1번 곱하여 나타내어진다 : a^n = a * a .. * a. 그러나, 이 접근법은 a 또는 n이 큰 경우에 실용적이지 않다.
a^(b+c) = a^b * a^c, and, a^(2b) = a^b * a^b = (a^b)^2
binary exponentiation의 아이디어는 우리가 지수의 이진 표기를 사용하여 그 일을 나누는 것이다.
n을 2 진수로 써보자, 예를들어
3^(13) = 3^(1101_2) = 3^8 * 3^4 * 3^1
n은 정확히 2진수로 floor(log_2^n) + 1 자리이기 때문에, 우리는 오직 O(log n)의 곱만을 수행할 필요가 있다. 만약 우리가 a^1, a^2, a^4, a^8, .... a^(floor(log_2^n)) 을 안다면.
그래서 우리는 그러한 것을 연산할 빠른 방법만을 알 필요가 있다. 운 좋게도 이것은 매우 쉽다. 그 수열에서 한 원소는 이전 원소의 제곱이기 때문이다.
3^1 = 3
3^2 = (3^1)^2 = 3^2 = 9
3^4 = (3^2)^2 = 9^2 = 81
3^8 = (3^4)^2 = 81^2 = 6561
그래서 3^13에 대한 최종 답을 얻기위해서, 우리는 그것들 중 세 개만 곱할 필요가 있다 (n에서 대응되는 bit가 set되지 않아 3^2은 넘어간다).
3^13 = 6561 * 81 * 3 = 1594323
이 알고리즘의 최종 복잡도는 O(log n)이다: 우리는 a의 log n 지수숭을 연산해야만 하고, 그러고나서 그것으로 부터 최종 답을 얻기위해 최대 log n의 곱을 해야만 한다.
다음의 재귀 접근법은 그 같은 아이디어를 나타낸다.
Implementation
처음에 재귀 접근법이다. 그것은 재귀 공식을 직접 바꾼 것이다.
long long binpow(long long a, long long b) { if (b == 0) return 1; long long res = binpow(a, b/ 2); if(b % 2) return res * res * a; else return res * res; }
두 번째 접근법은 재귀없이 같은 일을 한다. 그것은 loop에서 지수를 계산한다. 그리고 n에서 해당되는 설정된 bit로 곱한다. 비록 두 접근법의 복잡성은 동일할지라도, 이 접근법은 싲레로 더 빠를 것이다. 왜냐하면 우리는 재귀 호출의 오버헤드를 갖기 때문이다.
long long binpow(long long a, long long b) { long long res = 1; while(b > 0) { if(b & 1) res = res * a; a = a * a; b >>= 1; } return res; }
처음에 이게 잘 이해가 안됐는데, 비트 연산으로 2진수 단위로 생각하면 편하다.
3^13의 예제에서 13은 1101로 표현된다. 그래서 처음 끝자리 만 비교한다.
그래서 같은 1이 있다면, 결과에 곱해준다. 그런데 그 곱해주는 a는 매번 a^2이 곱해져야 된다.
즉, 3^1 3^2 3^4 3^8 이런식으로 곱해져 나가야 한다.
그리고 비트를 오른쪽으로 한 번 시프트 연산을 한다. 그러면 0110이된다.
그래서 0110 -> 0011 -> 0001 -> 0000
이런식으로 계속 하게 되면서 마지막 맨 끝 자리가 1이기만 하면은 우리가 곱해줘야 한다는 것이다. 그리고 a는 계속 제곱을 하면서.
}
Applications
Effective computation of large exponents modulo a number
문제 : x^n mod m을 연산해라. 이것은 매우 흔한 연산이다. 예를들어, 그것은 modular multiplicative inverse를 연산하는데 사용된다.
해결책 : 우리는 module operator가 곱셈을 간섭하지 않는다는 것을 알기 때문에
( a * b = (a mod m) * (b mod m) (mod m) ), 우리는 직접적으로 같은 코드를 사용할 수 있고, 모든 곱을 modular multiplication으로 대체할 수 있다:
long long binpow(long long a, long long b, long long m) { a %= m; long long res = 1; while(b > 0) { if(b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; }
만약 m이 소수라면, x^n 대신에 우리는 x^(n mod (m - 1)) 계산하여 이 알고리즘을 더 빠르게 할 수 있다. 이것은 Fermat의 소정리를 따른다.
Effective computation of Fibonacci numbers
문제 : n번째 피보나치 수 F_n을 연산해라.
해결책 : 좀 더 상세하게, Fibonacci Number article을 보아라. 우리는 오직 그 알고리즘의 개관만 볼 것이다. 다음 피보나치 수를 연산하기 위해서, 오직 두 개 의 이전의 것들만 필요하다. F_n = F_(n - 1) + F_(n - 2)이기 때문이다. 우리는 이 변환을 설명하는 2 x 2행렬을 구성할 수 있다: F_i와 F_(i+1) 에서 F(i + 1)과 F(i+2)로 가는 변환이다. 예를들어, F_0과 F_1의 쌍에 이 변환을 적용하는 것은 그것을 F_1과 F_2로 바꿀 것이다. 그러므로, 우리는 이 변환 행렬을 시간 복잡도 O( log n)에 F_n을 찾기위해 이 변환 행렬을 n승 할 수 있다.
Applying a permutation k times
문제 : 길이가 n인 수열이 주어진다. 그것에 주어진 permutation k번을 적용해라.
해결책 : 간단히 binary exponentiation을 사용하여 k번 지수승을 해라. 그리고 그것을 수열에 적용해라. 이것은 너에게 O(n log k)의 시간복잡도를 줄 것이다.
Note : 이 일은 permutation graph를 구성하고, 각 cycle를 독립적으로 고려하여 linear time으로 좀 더 효율적으로 해결될 수 있다. 너는 그러고나서 k % cycle크기를 연산하고, 이 사이클의 일부인 각 수에 대한 최종 위치를 찾을 수 있다.
Fast application of a set of geometric operations to a set of points
문제 : n개의 점들 p_i가 주어진다면, 이러한 점들 각각에 m번의 transformations을 적용해라. 각 transformation은 shift, scaling or 한 주어진 각만큼 주어진 축에 대해 회전이 될 수 있다. 또한 주어진 transformations의 한 리스트를 k번 적용하는 "loop" operation이 있다 ("loop" operations는 nested될 수 있다). 너는 O(n * length) 보다 더 빠르게 모든 transformations를 적용해야만 한다. 거기에서 length는 적용될 transformations의 총 개수 이다 ("loop" operations을 다 펼친 후에).
해결책 : transformations의 다른 종류가 그 좌푣르을 어떻게 바꾸는지 봐보자:
- Shift 연산 : 그 좌표의 각각에 다른 상수를 더하라
- Scaling 연산 : 다른 상수로 그 좌표 각각을 곱하라
- Rotation operation : 이 변환은 좀 더 복잡하지만 (우리는 여기에서 상세히 들어가지 않을 것이다), 새로운 좌표들 각각은 오래된 것의 linear combination으로 나타내어질 수 있다.
너가 볼 수 있듯이, 그 transformations 각각은 그 좌표에 대한 linear operations으로 나타내어질 수 있다. 따라서, 한 transformation은 4x4 행렬 형태로 쓰여질 수 있다:
~~
이제, 모든 transformation이 한 행렬로 설명되었기 때문에, 그 transformations의 sequence는 이러한 행렬들의 곱으로 설명될 수 있고, k번 반복의 한 "loop"는 그 행렬을 k승한 행렬로서 설명될 수 ㅣㅇㅆ다 (그리고 이것은 O(log k)로 binary exponentiation 을 사용하여 계산될 수 있다). 이 방식으로, 모든 transformations을 나타내는 그 행렬은 O(m log k)로 ㄱ산될 수 있고, 그러고나서 그것은 O(n)으로 총 O(n + mlogk)의 최종 복잡도 동안 n개의 점들에 대해 각각 적용될 수 있다.
Number of paths of length k in a graph
문제 : n개의 정점을 가진 방향이 있고 가중치가 없는 그래프가 주어진다면, 어떤 정점 u에서 어떤 다른 정점 v로 가는 길이가 k인 경로의 개수를 찾아라.
해결책 : 이 문제는 별개의 자료에서 좀 더 상세히 다뤄진다. 그 알골지ㅡㅁ은 그래프의 인접 행렬 M을 k승 한 것으로 구성된다 (거기에서 i에서 j로 가는 한 edge가 있다면 m_ij = 1이고, 아니면 0이다). 이제 m_ij는 i에서 j로 가는 길이 k인 경로의 수가 될 것이다. 이 솔루션의 시간 복잡도는, O(n^3 log k) 이다.
Note : 그 같은 자료에서, 이 문제의 또 다른 변형이 고려된다: 그 edges들이 가중치가 있고, 정확히 k개의 edges를 포함하는 최소 가중치 경로를 찾는 것이 요구될 때 이다. 그 자료에서 보여지듯이, 이 문제는 adjacency matrix의 exponentiation으로 또한 해결될 수 있다. 그 행렬은 i에서 j로 가는 edge의 가중치를 가질 것이고, 그러한 edge가 없으면 infinity일 것이다. 두 행렬을 곱하는 보통의 연산 대신에, 수정된 것이 사용되어야 한다: 곱 대신에, 두 값이 더해지고, 합 대신에 최소값이 취해진다. 즉:
Variation of binary exponentiation: multiplying two numbers modulo m
문제 : 두 수 a와 b를 곱하고 m으로 나머지 연산을 해라. ㅁ와 b는 내장 자료형에 맞지만, 그것들의 곱은 64-bit integer에 들어가기에 너무 크다. 아이디어는 a * b (mod m)을 bignum arithmetics를 사용하지 않고 연산하는 것이다.
해결책 : 우리는 간단히 위에서 설명된 binary construction algorithm을 적용하고, 오직 곱 대신에 덧셈을 수행한다. 다시 말해서, 우리는 두 개의 수의 곱을 덧셈과 곱셈의 O(log m) 연산으로 확장시킨다 (즉 본질적으로 덧셈이다).
Note : 너는 floating-point 연산을 사용하여 다른 방식으로 이 문제를 풀 수 있다. 처음에 부동 소수점 수로 (a * b) / m 수식을 연산해라. 그리고 그것을 unsigned integer q로 캐스팅해라. unsigned integer arithmetics를 사용하여 q * m을 a * b로부터 빼고, 그 답을 찾기 위해 modulo m을 취해라. 이 솔루션은 오히려 믿을만 하게 보이지 않지만, 매우 빠르고, 구현하기에 매우 쉽다. 더 자세한 정보는 여기에 있다.
댓글 없음:
댓글 쓰기