곱셈을 빨리 하는 법

들어가기에 앞서 이 article은 사람이 곱셈을 빨리 하는 법이 절대 아니고,
컴퓨터가 곱셈을 빨리 하게 하는 법임을 밝힌다.

컴퓨터 과학Computer Science을 모르는 분들을 위한 배경지식

컴퓨터는 한 번에 처리할 수 있는 데이터에 한계가 있기 때문에,
수의 범위를 자연수 \(n\)에 대해 \(-2^{n} \leq x < 2^{n}\)로 제한시켜 계산한다.
이것은 음수의 이용을 편리하게 한다. 보통 \(\mathbb{Z}_{2^{n+1}} - 2^{n} = \left\{x\left|-2^{n} \leq x < 2^{n},\ x\in\mathbb{Z}\right.\right\}\) 위에서의
모듈러 환modular (communicative) ring으로 계산한다고 생각하면 된다. 이것을 \(2\)의 보수 표기법이라고 하기도 한다.
아주 큰 두 수를 곱하려고 하면 컴퓨터는 자연적으로 이를 모듈러 환으로 계산하기 때문에
원래 나오려고 하는 값을 초과해 버리게 되는데 이를 overflow라고 한다.
이러한 이유 때문에 두 큰 자연수를 얼마나 빨리 곱하냐는 정보과학에서 중요한 문제이다.
우리 모두 컴퓨터에서 큰 수의 계산은 적절치 못하다는 것을 알고 있으므로, 어떻게든 작은 수로 끊어야 한다는 것을 알고 있다.
이것을 수학적으로, 다음과 같이 정의한다:
Definition 1. (Partition) 자연수 \(N\)의 밑 \(b\in\mathbb{N}\)로의 partition은 다음을 만족시키는 (무한) 수열 \(\left\{x_{n}\right\}\)이다: \[x_{n} \equiv \left\lfloor \frac{N}{b^{n}}\right\rfloor\ (\mathrm{mod\ } b),\ 0 \leq x_{n} < b\]
정의에 따라 곧바로 \(N\)과 \(b\)가 결정되면 수열이 유일하게 결정됨을 안다.
이제 partition에서 자연수를 만드는 역변환을 정의한다:
Definition 2. (Natural transform) 정수열 \(\left\{x_{n}\right\}\)이\[\lim_{n \rightarrow \infty}x_{n} = 0\]일 때, 이 수열의 밑 \(b\in\mathbb{N}\)로의 natural transform은 다음을 만족하는 자연수 \(N\)이다:\[N = \sum_{n=0}^{\infty}{x_{n} \cdot b^{n}}\]
이것이 잘 정의됨well-definedness은 간단하게 보일 수 있다:
Definition 2의 well-definedness 증명 정수열 \(\left\{x_{n}\right\}\)이 \(0\)으로 수렴하므로,\[\forall m > M \Rightarrow x_{m} = 0\]이 되는 자연수 \(M\)이 존재한다. 이제\[\begin{align*}N &= \sum_{n=0}^{\infty}{x_{n} \cdot b^{n}}\\ &= \sum_{n=0}^{M}{x_{n} \cdot b^{n}} + \sum_{n=M+1}^{\infty}{x_{n} \cdot b^{n}}\\ &= \sum_{n=0}^{M}{x_{n} \cdot b^{n}} + \sum_{n=M+1}^{\infty}{0 \cdot b^{n}}\\ &= \sum_{n=0}^{M}{x_{n} \cdot b^{n}}\\ \end{align*}\]이므로 Definition 2의 무한합은 수렴한다. \(\quad\square\)