뉴턴법 오차 분석
앞선 강의에서 제곱근을 계산하는 뉴턴법을 $X_{i+1} = \frac{X_i + \frac{a}{X_i}}{2}$ 라고 했다.
뉴턴법의 오차를 한 번 분석해보자. $\epsilon_{n}$ 은 n번째 오차(양수 or 음수)이다.
\[X_{n+1} = \sqrt{a} \cdot (1 + \epsilon_{n}) \\ X_{n+1} = \frac{X_n + \frac{a}{X_n}}{2} \\ = \frac{\sqrt{a} (1 + \epsilon_{n}) + \frac{a}{\sqrt{a} (1 + \epsilon_{n})}}{2} \\ = \sqrt{a} (\frac{(1 + \epsilon_{n}) + \frac{1}{(1 + \epsilon_{n})}}{2}) \\ = \sqrt{a} (\frac{2 + 2 \epsilon_{n} + \epsilon_{n}^2}{2(1 + \epsilon_{n})}) \\ = \sqrt{a} (1 + \frac{\epsilon_{n}^2}{2(1 + \epsilon_{n})})\]따라서
\[\epsilon_{n+1} = \frac{\epsilon_{n}^2}{2(1 + \epsilon_{n})}\]$\epsilon_{n}$ 은 단계를 거듭할수록 매우 작아진다. 따라서 우변의 분모에 있는 $\epsilon_{n}$ 를 무시한다면 매 단계 오차는 제곱의 절반만큼 감소한다고 볼 수 있다. 매 단계마다 정확도가 2배 되므로 이차적 수렴이라고 할 수 있다.
여러가지 곱셈 알고리즘
다양한 곱셈 알고리즘에 대해 알아보자.
-
기본 분할 정복 알고리즘
숫자를 큰 부분 절반과 작은 부분 절반으로 나누어서 계산하는 기본 방식이다. $\Theta(d^2)$ 의 시간이 걸린다. -
카라추바 알고리즘
앞선 강의에서 본 것처럼 $\Theta(d^{\log_{2}{3}}) = \Theta(d^{1.584})$ 의 시간이 걸린다. -
Toom-Cook 알고리즘
Toom과 Cook이 만든 알고리즘이다. 카라추바 알고리즘을 일반화한 것이라고 보면 된다. 숫자를 k개의 부분($k \geq 2$)으로 쪼갠다. k가 3일 때의 점화식은 다음과 같다.
$T(d) = 5T(d/3) + \Theta(d) = \Theta(d^{\log_{3}{5}}) = \Theta(d^{1.465})$ -
Schonhage-Strassen 알고리즘
고속 푸리에 변환(FFT)를 사용하는 알고리즘으로 거의 선형 시간에 가깝다. 시간복잡도는 $\Theta(d \log{d} \log{(\log{d})})$ 이다.
여기까지는 파이썬의 gmpy 패키지에서 사용 가능하다. 특히, 파이썬은 큰 숫자의 곱셈에 대해 기본적으로 카라추바 알고리즘을 사용한다.
- Furer 알고리즘
$\Theta(n \log{n} 2^{O(\log*n)})$ 의 시간 복잡도를 가진다. $\log*n$ 은 반복 로그라고 부르는데, 로그 값의 결과가 1보다 작거나 같을 때까지 반복해서 로그를 계산하는 횟수를 의미한다. 아주 큰 숫자라도 로그 계산을 하면 1보다 작게 될 때까지는 별로 걸리지 않는다. 즉, 아주아주 큰 숫자를 계산할 때도 유용하게 이용할 수 있다.
고정밀 나눗셈
이제 본격적으로 고정밀 나눗셈을 논할 준비가 되었다.
$\frac{a}{b}$ 의 고정밀 나눗셈은 $\frac{1}{b}$ 의 고정밀 표현을 먼저 계산하게 된다. 이때, $\frac{1}{b}$ 의 고정밀 표현은 R이 큰 값인 경우에 $\lfloor \frac{R}{b} \rfloor$ 을 R로 나눈 결과다. $R=2^k$와 같은 경우라면 우리는 자릿수 이동을 통해 나눗셈 결과를 쉽게 알 수 있다.
$\frac{R}{b}$ 을 계산하는 데 뉴턴 방법을 사용해보자.
\[f(x) = \frac{1}{x} - \frac{b}{R} \\ f^{\prime}(x) = -\frac{1}{x^2} \\ x_{i+1} = x_i - \frac{f(x_i)}{f^{\prime}(x_i)} = x_i - \frac{(\frac{1}{x_i} - \frac{b}{R})}{-\frac{1}{x^2}} \\ x_{i+1} = x_i + x_i^2(\frac{1}{x_i} - \frac{b}{R}) = 2x_i - \frac{bx_i^2}{R}\]마지막 식을 분석해보자. 일단 $x_i$ 에 2를 곱하는 과정이 필요하다. 그리고 $x_i$ 를 제곱(곱셈)한 뒤에 b를 곱한다. 나눗셈 과정은 R을 나누는 것 하나 밖에 없으며, 심지어 그 나눗셈마저 쉽게 하기 위해 R을 잘 선택해두었다.
예시를 보자. $R = 2^{16}_{(2)}$ 을 $b=5$로 나누는 과정이다. b를 나눗셈에 쉽게 4로 재설정할 수 있다.
\[\frac{R}{b} = \frac{2^{16}_{(2)}}{5} \\ \frac{2^{16}_{(2)}}{4} = 2^{14}_{(2)} \\\]$x_0$ 부터 차례로 계산하면 다음과 같다.
\[x_0 = 2^{14}_{(2)} = 16384 \\ x_1 = 2 \cdot (16384) - 5(16384)^2/65536 = 12288 \\ x_2 = 2 \cdot (12288) - 5(12288)^2/65536 = 13056 \\ x_3 = 2 \cdot (13056) - 5(13056)^2/65536 = 13107\]이차적 수렴이므로, $x_1$ 에서는 가장 앞 한 자리, $x_2$ 는 가장 앞 두 자리, x_3 는 가장 앞 네 자리를 신뢰할 수 있다. 최종 결과는 다음과 같다.
\[\frac{R}{b} = \frac{2^{16}_{(2)}}{5} = \frac{65536}{5} = 13107.2\]고정밀 나눗셈에서의 오차 분석
고정밀 나눗셈에서 역시 각 단계마다 정확하게 계산한 자릿수가 2배씩 증가하므로 이차적 수렴이다.
나눗셈의 복잡도는 $O(\log{n} d^{\alpha})$ 라고 생각할 수 있다. 전체 계산에 필요한 스텝의 개수가 $\log{d}$ 개이고(정확도가 2배씩 증가하니까), 곱셈의 복잡도는 $d^{\alpha}$ 이기 때문이다. 그러나 이게 최선일까?
먼저, $\alpha \geq 1$ 에 대해서, 나눗셈은 각 반복마다 다른 크기의 자릿수를 가지는 숫자를 곱해야 한다. 초기에는 자릿수가 작지만, 나중에는 d자릿수를 계산하게 된다. 따라서 나눗셈에서의 연산 횟수는 다음과 같이 표현할 수 있다.
\[c \cdot 1^{\alpha} + c \cdot 2^{\alpha} + c \cdot 4^{\alpha} + ... + c \cdot (\frac{d}{4})^{\alpha} + c \cdot (\frac{d}{2})^{\alpha} + c \cdot d^{\alpha} < 2c \cdot d^{\alpha}\]나눗셈의 복잡도 상한을 보자! 곱셈의 복잡도와 나눗셈의 복잡도는 동일하다.
제곱근 계산의 복잡도
이제 최종적으로 제곱근 계산을 살펴보자. $f(x) = x^2 - a$ 의 해를 찾기 위해 나눗셈이 필요한 뉴턴법의 첫 번째 단계를 적용한다. d자리의 정확도가 목표일 때, 필요한 반복은 $\log{d}$ 이고 곱셈(나눗셈)의 복잡도는 $\Theta(d^{\alpha})$ 이다. 따라서 복잡도는 $O(d^{\alpha} \log{d})$ 이다.
그러나 첫 번째 단계를 적용할 때 필요한 정확한 자릿수는 작은 상태에서 점차 커진다. 즉, 제곱근 계산에 걸리는 시간 복잡도도 $O(d^{\alpha})$ 가 된다.
별도의 출처 표시가 있는 이미지를 제외한 모든 이미지는 강의자료에서 발췌하였음을 밝힙니다.
댓글남기기