MIT - Introduction to Algorithms
- Lecture 11. Integer Arithmetic, Karatsuba Multiplication 정수 산술, 카라추바 알고리즘 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/
예로 중성미자의 중량을 찾기 위한 고정밀 계산을 생각한다면 64bit는 충분하지 않다
만약에 $\sqrt{2}$를 컴퓨터로 백만자리까지 계산한다는 것 역시 마찬가지이다.
이런 내용들에 대해가볍게 수학적인 접근을 생각해보자
오늘은 뉴튼 방법을 이용한 무리수를 계산하는 방법을 배울 것
RSA 암호화와 관련된 응용법을 만나게 될 것
이 방법은 소수를 이용해 수천 비트 길이의 소수를 다루게 될 것 > 64bits
Irrational 무리수
정사각형의 대각선 길이는 정수비로 표현 불가
=> 피타고라스 신비주의 철학에서는 숫자가 전부라 칭할 정도로 숭배했지만 $\sqrt{2}$와 같은 무리수를 설명불가라 불렀다. 위협으로 느낌
무리수의 패턴을 찾아내려는 시도는 1조이상의 수를 다뤄야하기에 고정밀 계산이 필요한 이유이다.
본문에서 제시하는 조건들을 만족하는 형태를 재귀적으로 계속 얻어낼 수 있다
balanced : (), (()), ...
unbalanced : (, ((), ()), ...
ex) (())()() : 카탈랑 수
무한개로 증가
Enumerate 열거하게 될 때 $C_n$을 사용
$C_0=1$,empty string, $C_n = \sum_{i=0}^{n-1}C_iC_{n-1-i} for n \ge 1 = \sum_{i=0}^{n}C_iC_{n-i} for n \ge 0$
$C_2 = C_0C_1 + C_1C_0=2$
일종의 멋진 숫자를 생성하는 생성기
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 45950804324621742364, …
이를 통해 우리는 어떤 숫자를 보고 카탈란 수임을 알아챌 수 있게 되었다.
기하학적으로는 접선 원리
$f(x_i)$의 접선일 대 x축에 만나는 점이 $x_{i+1}$
접선 방정식은 $y=f(x_i) + f^\prime(x_i)(x-x_i)$일 때 x축과 만나는 점은 y=0이므로
$x_{i+1} = x_i - {f(x_i) \over f^\prime(x_i)}$
$f(x) = x^2 -a$
$x_{i+1} = x_i - {x_i^2-a \over 2x_i} = {x_i + {a \over x_i} \over 2}$
a=2일 때 우리는 $\sqrt{2}$를 구하는 것
x0 = 1:000000000 a = 2
x1 = 1:500000000
x2 = 1:416666666
x3 = 1:414215686
x4 = 1:414213562 etc
Quadratic Convergence 2차적 수렴
뉴턴 방법은 2차적 수렴 특성을 가진다.
정리
뉴턴 방법을 사용해서 우리는 $\sqrt{2}$의 근사치를 구하고 싶은 것이다. 이를 위해 f(x)에 대한 접선을 극한으로 넣어가며 값을 구하는 것이다.
ex) f(x) = x^2 - a에서 접선의 방정식을 구하고 y=0일 때 x축 위의 직선의 값을 다음 x로 지정한 다음 계속 무한 반복
이를 통해 우리는 $\sqrt{a}$의 근사치를 구하는 것이다.
때문에 f(x)
x1 = .5(1)
x2 = .41(2)
x3 = .4142(4)
x4 = .414213562(8) : 4자리수 정밀도
# digits가 정밀도의 2배
2,4,8,16과 같이 지수적으로 늘어가기 때문에 반복 횟수는 log번
그러므로 큰 자릿수라도 빠르게 계산
${a \over x_i}$에서 단지 자리 올림만 신경 쓰면 되기 때문에 의미있는 자리만 신경쓰면 됨
고정밀도 곱셈 계산을 위한 알고리즘을 다음 시간에 다룰 것
실제로 대부분의 나눗셈 알고리즘은 서브루틴으로 곱셈을 사용 > 나눗셈 사용 : 쉽고 빠름
다음 단원 Lecture 12에서 다룸
MIT - Introduction to Algorithms - Lecture 12. Square Roots, Newton's Method 제곱근과 뉴턴 방법 Review
가장 좋아하는 전략인 분할 정복 사용
왜냐하면 큰 수 n이 있기 때문에 쪼개서 64bits 숫자들을 얻게 되고 그것들을 곱셈을 수행함으로써 컴퓨터가 우리는 원하는 곱셈이 가능하도록 할 수 있다.
$z_2 = x_1y_1, z1=x_0y_1+x_1y_0, z0=x_0y_0$
ex) 0.123456...와 0.789012이라는 두 개의 숫자를 d=6인 6자리까지 알고싶다고 했을 때 123456.xxx와 789012.xxxx가 된 상태에서
r = 10 (10진법)
n = 6 (자릿 수)
x1=123, x0=456
y1=789, y0=012가 되는 것
n크기를 n/2 크기의 숫자들을 4번 곱셈으로 계산 -> $\theta(n^2)$ time
$T(n) = 4T(n/2) + \theta(n)$
$\theta(n^2) = \theta(n^{log_2 4})$
$z_2 = x_1y_1, z1=(x_0+x_1)(y_0+y_1)-z_0-z_2, z0=x_0y_0$
이렇게 함으로써 3번의 곱으로만 수행이 가능(원래는 4번의 곱) -> 시간이 감소
$T(n) = 3T(n/2) + \theta(n) = \theta(n^{log_2 3}) \approx \theta(n^{1.584906 \cdots})$
계산은 $\sqrt{2}$보다 더 정밀한 계산
$Q(x) = {1 \pm \sqrt{1-4x} \over 2x}$
$xQ(x)^2 - Q(x) + 1=0$의 형태에서 근의 공식으로 유도 가능
