MIT - Introduction to Algorithms
- Lecture 12. Square Roots, Newton's Method
제곱근과 뉴턴 방법 Review
Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
제곱근을 계산할 때 몇 번의 곱셈이 필요할까
Review
d = # of digits of precision
반복 횟수가 로그함수라는 것을 실제로 증명하기 위해 자세히 살펴볼 것
$x_{i+1}$를 계산할 때 결과값이 실제로 이차적 수렴의 성질인지 확인
Error Analysis of Newton's Method
$x_n$은 n 번째 반복에서 가지는 오차를 의미하는데 a의 제곱근 값에 대한 오차
처음에는 크지만 점차 줄어갈 것
여기서 수렴하는 것을 보이고자 함
n이 커질수록 $\epsilon$이 0에 가까워짐 -> 얼마나 빨리 0에 가까워질까가 질문
$x_n$을 대입해서 열거
결과
$$\epsilon_{n+1} = {\epsilon_n^2 \over 2(1+\epsilon_n)}$$
수렴성을 띤다
= 결과적으로 d digits of precision d 자릿수의 정확도를 계산하기 위해서 log d만큼의 반복을 수행하면 된다.
2. Karatsuba : reduce 3 Multiplications $T(n) = 3T({n \over 2}) + \theta(n) = \theta(n^{log_2 3}) = \theta(n^{1.58...})$
3. Toom-Cook : Generalize Karatsuba $k \ge 2$
$x_2, x_1, x_0$, d/3 digits
$y_2, y_1, y_0$
Naive Method : 9 Multiplications
$T(n) = 5T({n \over 3}) + \theta(n) = \theta(n^{log_3 5}) = \theta(n^{1.465...})$
4. Schonhage-Strassen : 거의 선형적 시간을 가짐 : 고속 퓨리에 변환을 이용한 향상이 가능
$\theta(nlog_2(n) log_2( log_2( n)))$ time : FFT(Fast Fourier Transform)
Python - gmpy pacakage로 사용이 가능
이미 구현된 알고리즘을 강의 당시 2011년도에도 사용하고 있음
파이썬에서 긴 정수를 계산할 때 역시도 카라추바 알고리즘을 사용 단 n이 클 때
5. Furer
$\theta(n log (n) 2^{O(log * n)})$
$log * n$ : iterated logarithm 반복 로그 알고리즘 : 1보다 같거나 작은 값이 나올 때까지 반복적으로 로그를 계산해야하는 횟수
반복 로그 알고리즘은 굉장히 빠르게 크기가 작아짐
ex) $2^{50} -> log_2 50 \approx 7 -> log_2 7 \approx 2.xxxx$
4~5번으로 1보다 같거나 작은 값을 얻음
실제론 n이 10억 이상의 큰 수일 때 사용, 이것은 gmpy에 구현되지 않음(강의 당시 2011)
이제까지 나눗셈을 어떻게 하는지 설명하지 않음 : 지금부터 알아보자
High Precision Division
rep : representative
R을 이진법을 사용한 경우 시프트 연산으로 쉽게 나눗셈이 가능
나눗셈은 기본적으로 오른쪽으로 시프트시키는 것과 같다
최상위 비트가 오른쪽으로 이동하고 작은 값을 얻게됨
ex) 72를 100으로 나눈다면 0.72로 72가 오른쪽으로 이동
f(x)를 적절한 초기값으로 시작해서 결국에는 ${R \over b}$의 값을 구할 수 있도록 x를 설정
${R \over b}$ 소수점 버림값이 됨으로써 시프트 연산을 이용해 ${1 \over b}$을 구할 수 있음
뉴턴 방법으로 얻어낸 결과
$$x_{i+1} = x_i + x_i^2({1 \over x_i} - {b \over R}) = 2x_i - {bx_i^2 \over R}$$
기본적으로 곱셈(2나 제곱)은 걱정에 없고 쉬운 나눗셈이 되도록 R을 선택했기 때문에 이 역시 어렵지 않음
ex)
바라는 값 ${R \over b} = {2^{16} \over 5} = 13107.2$
시작 추측 값 : $x_0 = {R \over b} = {2^{16} \over 4} = 2^{14} = 16384$
$x_1 = 12288, x_2=13056, x_3=13107$점차 빠르게 수렴해가는 것을 확인 가능
제곱근에서 이차적 비유로 수렴했던 것과 나눗셈에 뉴튼 방법을 적용할 때 같다
$\epsilon_{n+1},\epsilon_n$간의 증명이 가능하지만 동일하지는 않다
정리
우리는 $\sqrt{2}$의 무리수를 구하기 위해 뉴턴 방법을 통해 구하고자 했다.
이 때 뉴턴 방법의 근사치에 ${a \over x_n}$ term이 존재하고
이 분모 모양의 해결을 위해 우리는 위와 같은 ${1 \over x}$의 근사치를 구하기 위한 뉴턴 방법을 또 사용했다.
결과적으로 무리수 $\sqrt{2}$를 구하기 위해 뉴턴 방법을 2번 사용하는 상황
max heapify를 통해 더 좋게 가능
d 자릿수를 얻기 위해서 작은 수의 정확도부터 시작
d digits of Precision in Division : 1 2 4 d - 총 $log(d)$ 길이, 1이 Initial multiplication, 뒤로 갈수록 연산이 많아짐
$c1^\alpha + c2^\alpha+ c3^\alpha \cdots + c{d \over 4}^\alpha+ c{d \over 2}^\alpha + cd^\alpha < 2cd^\alpha$ $c1^\alpha$은 1자릿수의 정확도만을 가지기 때문 나눗셈의 복잡도 Complexity of Division = Complexity of Multiplication Complexity of Computing Square Root $\sqrt{a}$ -> Newton's Method
Division : Newton's Method를 통한 많은 곱셈 연산
