[MIT 파이썬을 이용한 알고리즘의 이해] 12. 수 2

뉴턴법 오차 분석Permalink

앞선 강의에서 제곱근을 계산하는 뉴턴법을 $X_{i+1} = \frac{X_i + \frac{a}{X_i}}{2}$ 라고 했다.

뉴턴법의 오차를 한 번 분석해보자. $\epsilon_{n}$ 은 n번째 오차(양수 or 음수)이다.

따라서

$\epsilon_{n}$ 은 단계를 거듭할수록 매우 작아진다. 따라서 우변의 분모에 있는 $\epsilon_{n}$ 를 무시한다면 매 단계 오차는 제곱의 절반만큼 감소한다고 볼 수 있다. 매 단계마다 정확도가 2배 되므로 이차적 수렴이라고 할 수 있다.

여러가지 곱셈 알고리즘Permalink

다양한 곱셈 알고리즘에 대해 알아보자.

1. 기본 분할 정복 알고리즘
   숫자를 큰 부분 절반과 작은 부분 절반으로 나누어서 계산하는 기본 방식이다. $\Theta(d^2)$ 의 시간이 걸린다.

2. 카라추바 알고리즘
   앞선 강의에서 본 것처럼 $\Theta(d^{\log_{2}{3}}) = \Theta(d^{1.584})$ 의 시간이 걸린다.

3. 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})$

4. Schonhage-Strassen 알고리즘
   고속 푸리에 변환(FFT)를 사용하는 알고리즘으로 거의 선형 시간에 가깝다. 시간복잡도는 $\Theta(d \log{d} \log{(\log{d})})$ 이다.

여기까지는 파이썬의 gmpy 패키지에서 사용 가능하다. 특히, 파이썬은 큰 숫자의 곱셈에 대해 기본적으로 카라추바 알고리즘을 사용한다.

1. Furer 알고리즘
   $\Theta(n \log{n} 2^{O(\log*n)})$ 의 시간 복잡도를 가진다. $\log*n$ 은 반복 로그라고 부르는데, 로그 값의 결과가 1보다 작거나 같을 때까지 반복해서 로그를 계산하는 횟수를 의미한다. 아주 큰 숫자라도 로그 계산을 하면 1보다 작게 될 때까지는 별로 걸리지 않는다. 즉, 아주아주 큰 숫자를 계산할 때도 유용하게 이용할 수 있다.

고정밀 나눗셈Permalink

이제 본격적으로 고정밀 나눗셈을 논할 준비가 되었다.

$\frac{a}{b}$ 의 고정밀 나눗셈은 $\frac{1}{b}$ 의 고정밀 표현을 먼저 계산하게 된다. 이때, $\frac{1}{b}$ 의 고정밀 표현은 R이 큰 값인 경우에 $\lfloor \frac{R}{b} \rfloor$ 을 R로 나눈 결과다. $R=2^k$와 같은 경우라면 우리는 자릿수 이동을 통해 나눗셈 결과를 쉽게 알 수 있다.

$\frac{R}{b}$ 을 계산하는 데 뉴턴 방법을 사용해보자.

마지막 식을 분석해보자. 일단 $x_i$ 에 2를 곱하는 과정이 필요하다. 그리고 $x_i$ 를 제곱(곱셈)한 뒤에 b를 곱한다. 나눗셈 과정은 R을 나누는 것 하나 밖에 없으며, 심지어 그 나눗셈마저 쉽게 하기 위해 R을 잘 선택해두었다.

예시를 보자. $R = 2^{16}_{(2)}$ 을 $b=5$로 나누는 과정이다. b를 나눗셈에 쉽게 4로 재설정할 수 있다.

$x_0$ 부터 차례로 계산하면 다음과 같다.

이차적 수렴이므로, $x_1$ 에서는 가장 앞 한 자리, $x_2$ 는 가장 앞 두 자리, $x_3$ 는 가장 앞 네 자리를 신뢰할 수 있다. 최종 결과는 다음과 같다.

고정밀 나눗셈에서의 오차 분석Permalink

고정밀 나눗셈에서 역시 각 단계마다 정확하게 계산한 자릿수가 2배씩 증가하므로 이차적 수렴이다.

나눗셈의 복잡도는 $O(\log{n} d^{\alpha})$ 라고 생각할 수 있다. 전체 계산에 필요한 스텝의 개수가 $\log{d}$ 개이고(정확도가 2배씩 증가하니까), 곱셈의 복잡도는 $d^{\alpha}$ 이기 때문이다. 그러나 이게 최선일까?

먼저, $\alpha \geq 1$ 에 대해서, 나눗셈은 각 반복마다 다른 크기의 자릿수를 가지는 숫자를 곱해야 한다. 초기에는 자릿수가 작지만, 나중에는 d자릿수를 계산하게 된다. 따라서 나눗셈에서의 연산 횟수는 다음과 같이 표현할 수 있다.

나눗셈의 복잡도 상한을 보자! 곱셈의 복잡도와 나눗셈의 복잡도는 동일하다.

제곱근 계산의 복잡도Permalink

이제 최종적으로 제곱근 계산을 살펴보자. $f(x) = x^2 - a$ 의 해를 찾기 위해 나눗셈이 필요한 뉴턴법의 첫 번째 단계를 적용한다. d자리의 정확도가 목표일 때, 필요한 반복은 $\log{d}$ 이고 곱셈(나눗셈)의 복잡도는 $\Theta(d^{\alpha})$ 이다. 따라서 복잡도는 $O(d^{\alpha} \log{d})$ 이다.

그러나 첫 번째 단계를 적용할 때 필요한 정확한 자릿수는 작은 상태에서 점차 커진다. 즉, 제곱근 계산에 걸리는 시간 복잡도도 $O(d^{\alpha})$ 가 된다.

별도의 출처 표시가 있는 이미지를 제외한 모든 이미지는 강의자료에서 발췌하였음을 밝힙니다.