쇤하게-슈트라센 곱셈법(Schönhage–Strassen multiplication algorithm)은 두 정수의 곱을 빠르게 셈하는 알고리즘으로, 1971년 아놀드 쇤하게(Arnold Schönhage)와 폴커 슈트라센(Volker Strassen)이 고안하였다. 이 곱셈법은 푸리에 변환을 이용한 방법으로 시간 복잡도는 [math]\displaystyle{ O(n\log n \log\log n) }[/math] 꼴이다. 이는 1960년대에 고안된 카라추바 곱셈법이나 톰-쿡 곱셈법보다 큰 수에서 훨씬 효율적이며, 로그 항을 제외하면 사실상 연산량은 자릿수에 거의 비례한다.
이 방식은 컴퓨터 연산에 큰 혁명을 가져왔다고 할 수 있으며, 2007년 퓌러 곱셈법, 2019년 하비-호븐 곱셈법이 나오기 전까지 가장 효율적인 큰 수의 곱셈법이었다. 물론 현재 컴퓨터에서 많이 다루는 범위의 큰 수, 또는 소수점 아래 자릿수가 많은 수에 대해서는 여전히 쇤하게-슈트라센 방식이 가장 실용적이다.
아이디어[편집 | 원본 편집]
- 참고: 이 문단에서는 쇤하게-슈트라센 곱셈법의 '기본 원리'를 중심으로 소개한다. 구체적인 알고리즘 설계나 최적화 방법에는 여러 방식이 있으며, 본 문서와 원문의 내용에는 다소 차이가 있다. Wikipedia:Schönhage–Strassen algorithm에서도 다른 방법을 알아볼 수 있다.
- 벡터의 성분 표기는 전산의 편의를 위해 첫 성분을 0으로 잡는다.
이 곱셈법은 기본적으로 자릿수 블록을 쪼개고 부분 곱셈을 시행한 뒤 합성하는 방식을 따르며, 카라추바 곱셈법이나 톰-쿡 곱셈법과 출발점이 같다.
어떤 큰 두 수를 일정 자릿수마다 블록을 쪼개고, 두 수에 대응하는 다항식을 세운다. [math]\displaystyle{ M=f(B), m_1=\lceil \log_B M \rceil, f(x)=\sum_{k=0}^{m_1-1} a_k x^k, N=g(B), m_2=\lceil \log_B N \rceil, g(x)=\sum_{k=0}^{m_2-1} b_k x^k }[/math][1] 여기서 [math]\displaystyle{ B }[/math]는 기수법에 따라 결정되는 값으로, 가령 이진법에서 블록 하나당 [math]\displaystyle{ r }[/math]자리를 담고 있다면 [math]\displaystyle{ B=2^r }[/math]이다.
그 다음 우리가 구할 다항식은 [math]\displaystyle{ h(x)=f(x)g(x)=\sum_{k=0}^{m_1+m_2-2} c_k x^k }[/math]이며, 구하려는 곱셈 결과는 [math]\displaystyle{ MN=h(B) }[/math]이다. 그렇다면 위에서 상정한 계수 [math]\displaystyle{ a_k, b_k, c_k }[/math]의 관계는 아래와 같이 합성곱의 형태로 써진다.
- [math]\displaystyle{ h(x)=\sum_{k=0}^{m_1-1} a_k x^k \sum_{k=0}^{m_2-1} b_k x^k = \sum_{k=0}^{m_1+m_2-2}(\sum_{l=0}^{k}a_l b_{k-l})x^m }[/math]
- [math]\displaystyle{ c_k=\sum_{l=0}^{k}a_l b_{k-l}, 0 \leq k \leq m_1+m_2-2 }[/math]
- 단, [math]\displaystyle{ m_1-1 \lt l \leq m_1+m_2-2 }[/math]인 경우 [math]\displaystyle{ a_l=0 }[/math]으로 간주한다. 마찬가지로 [math]\displaystyle{ m_2-1 \lt l \leq m_1+m_2-2 }[/math]인 경우 [math]\displaystyle{ b_l=0 }[/math]이다.
- 벡터 [math]\displaystyle{ a=(a_0, a_1, \cdots a_{m_1+m_2-2}) }[/math]를 정의하고 마찬가지로 [math]\displaystyle{ b, c }[/math]를 정의하면 [math]\displaystyle{ c= \operatorname{convolution}(a, b) }[/math]와 같이 표현된다.
그런데 벡터의 합성곱에서 벡터를 푸리에 변환하면 성분 별 곱셈으로 바뀐다. 즉 이산 푸리에 변환을 거친 벡터를 [math]\displaystyle{ \bar{a} =\operatorname{DFT}(a) \Leftrightarrow a =\operatorname{IDFT}(\bar{a}) }[/math]와 같이 표현하면 [math]\displaystyle{ \bar{c}_k=\bar{a}_k \bar{b}_k, c=\operatorname{IDFT}(\bar{c}) }[/math]이다.[2]
따라서 이 알고리즘은 "블록 쪼개기→푸리에 변환→블록 별 부분 곱셈→푸리에 역변환→블록 합치기" 순으로 진행한다.
모듈러 산술에서의 푸리에 변환[편집 | 원본 편집]
곱하려는 두 수의 블록 개수의 합을 [math]\displaystyle{ K }[/math]라 하면 전형적인 이산 푸리에 변환 및 역변환은 다음과 같이 써진다.
- [math]\displaystyle{ f(x)=\sum_{k=0}^{K-1} a_m x^m }[/math][3]
- [math]\displaystyle{ f(\omega^n)=\sum_{k=0}^{K-1} a_k \omega^{kn}, \omega=e^{2\pi i/K} }[/math]
- [math]\displaystyle{ a_k=\frac{1}{K}\sum_{n=0}^{K-1} f(\omega^n) \omega^{-kn} }[/math]
- [math]\displaystyle{ g(x)=\sum_{k=0}^{K-1} b_k x^k, h(x)=\sum_{k=0}^{K-1} c_k x^k }[/math]도 마찬가지 형태로 써진다.
계산 목표는 먼저 [math]\displaystyle{ f(\omega^n), g(\omega^n) }[/math]이고 이를 이용하여 [math]\displaystyle{ h(\omega)=f(\omega^n)g(\omega^n) }[/math]의 값을 구한다. 그렇게 해서 다항식 [math]\displaystyle{ h(x) }[/math]를 도출하고 [math]\displaystyle{ h(B) }[/math]의 값을 구하면 원하는 답이 나온다.
하지만 위 공식을 그대로 적용하기에는 무리가 있다. 푸리에 변환에 필요한 곱셈 인자인 [math]\displaystyle{ \omega }[/math]는 특수한 값을 제외하고는 기본적으로 실수부와 허수부 모두 무리수이다. 본 문서에서는 두 정수의 곱셈을 다루려는데, 공식 그대로의 변환은 사실상 무리수의 곱셈 및 덧셈을 다루는 것이다. 즉 계산 과정이 오히려 지저분해진다. 그 대신 모듈러 산술을 기준으로 공식을 다듬으면 정수의 연산 틀을 유지할 수 있다.
이산 푸리에 변환은 기본적으로 [math]\displaystyle{ \omega \neq 1, \omega^K=1, \sum_{k=0}^{K-1}\omega^{kn}=\begin{cases} K \text{ if } K \mid n \\ 0 \text{ otherwise} \end{cases} }[/math] 식을 바탕으로 세워진다. 그렇다면 모듈러 산술에서는 [math]\displaystyle{ t \neq 1, t^K \equiv 1 \pmod u }[/math]를 만족하는 정수 [math]\displaystyle{ t, u }[/math]로 대체한다. 그리고 푸리에 변환은 [math]\displaystyle{ \mathbb{C} }[/math] 대신 [math]\displaystyle{ \mathbb{Z}/u\mathbb{Z} }[/math] 위에서 이루어진다.
그러면 [math]\displaystyle{ f(t^n) \equiv \sum_{k=0}^{K-1} a_k t^{kn} \pmod p }[/math]과 같이 쓸 수 있고, [math]\displaystyle{ g(t^n), h(t^n) }[/math]역시 같은 형식으로 써진다.
이제 몇 가지 가정이 필요하다: 계산의 편의를 위해 [math]\displaystyle{ K=2K' }[/math]는 짝수로 두고, [math]\displaystyle{ t^{K'} \equiv -1 \pmod u }[/math]라고 가정한다.
그 다음 조건식 [math]\displaystyle{ \sum_{k=0}^{K-1} t^{kn} \equiv \begin{cases} K \text{ if } K \mid n \\ 0 \text{ otherwise} \end{cases} \pmod u }[/math]를 살펴볼 차례다. [math]\displaystyle{ t^K \equiv 1, t^n \not \equiv 1 \pmod u \text{ for } 0\lt n \lt K }[/math]를 만족하면 해당 조건식은 성립한다. 즉 법 [math]\displaystyle{ u }[/math]의 대한 [math]\displaystyle{ t }[/math]의 위수가 [math]\displaystyle{ K }[/math]와 일치하도록 하려고 한다. 이 조건을 맞추는 방법은 여러 가지가 있지만 컴퓨터가 다루기 쉬운 값은 [math]\displaystyle{ u=2^{K'}+1, t=2 }[/math]이다. [math]\displaystyle{ t^n=2^n }[/math]을 곱한다는 것은 비트를 왼쪽으로 [math]\displaystyle{ n }[/math]자리 미는 것과 같으며, [math]\displaystyle{ A=2^{K'}a+b }[/math]이면 [math]\displaystyle{ A \equiv -a+b \pmod{2^{K'}+1} }[/math]로 나머지 연산이 간결하기 때문이다.
또 하나, 앞서 언급한 식인 [math]\displaystyle{ M=f(B), N=g(B) }[/math]에 대해 [math]\displaystyle{ f(x), g(x) }[/math]의 계수는 모두 [math]\displaystyle{ 0 \leq a_k, b_k \lt B }[/math]이다. 또한 [math]\displaystyle{ h(x) }[/math]의 계수 공식 [math]\displaystyle{ c_k=\sum_{l=0}^{k}a_l b_{k-l} }[/math]에서 각 계수의 가능한 값의 범위를 파악해야 한다.
[math]\displaystyle{ M, N }[/math]의 블록의 개수를 [math]\displaystyle{ m_1, m_2 }[/math]라 하면 [math]\displaystyle{ a_l b_{k-l} \neq 0 }[/math]인 항의 최대 개수는 [math]\displaystyle{ \min(m_1, m_2) }[/math]이다. 그런데 [math]\displaystyle{ m_1+m_2 =K }[/math]이므로, 결국 0이 아닌 항의 최대 개수는 [math]\displaystyle{ K' }[/math]이라 할 수 있다. 그리고 [math]\displaystyle{ 0 \leq a_l, b_{k-l}\lt B }[/math]이므로 [math]\displaystyle{ 0 \leq a_l b_{k-l}\lt B^2 }[/math]이고, 이에 따라 [math]\displaystyle{ 0 \leq c_k \lt K'B^2 }[/math]임을 알 수 있다.
한편 [math]\displaystyle{ h(t^n) \equiv \sum_{k=0}^{K-1} c_k t^{kn} \pmod u }[/math]에서 [math]\displaystyle{ c'_k=c_k+u }[/math]라 하면 [math]\displaystyle{ h(t^n) \equiv \sum_{k=0}^{K-1} c'_k t^{kn} \pmod u }[/math] 식도 성립한다. 다시 말해 만약 [math]\displaystyle{ 0 \leq c_k, c'_k \lt K'B^2, c'_k-c_k=u }[/math]인 두 계수가 존재한다면 같은 [math]\displaystyle{ h(t^n) }[/math]에 대해 서로 다른 [math]\displaystyle{ c_k }[/math]의 해가 둘 이상 나오는 불상사가 발생한다. 원래 다항식 [math]\displaystyle{ h(x)=f(x)g(x) }[/math]의 계수들은 반드시 유일하게 나와야 하는데, 해가 여러 개이면 어떤 것이 우리가 찾고자 하는 해인지 구분할 수 없게 된다(즉 정보가 뭉개진다). 따라서 이를 방지하려면 [math]\displaystyle{ u \geq K'B^2 }[/math]으로 잡아야 하며, 이것이 계수의 범위를 사전에 체크하는 이유이다.
블록의 개수와 길이[편집 | 원본 편집]
이산 푸리에 변환은 블록의 개수가 2의 거듭제곱일 때 가장 효율적으로 계산할 수 있으며, 이 조건에서 고속 푸리에 변환을 도입한다.
두 수의 곱인 [math]\displaystyle{ MN }[/math]의 최대 비트 수는 [math]\displaystyle{ \ell=\lceil \log_2 M \rceil+\lceil \log_2 N \rceil }[/math]이다.[4] 블록 하나가 [math]\displaystyle{ r }[/math]비트이고 [math]\displaystyle{ K }[/math]개 블록이 위 곱셈 결과를 담으려면 [math]\displaystyle{ \ell \leq Kr }[/math]이어야 한다. 즉 [math]\displaystyle{ r=\left \lceil \frac{\ell}{K} \right \rceil }[/math]로 잡는다.
한편 블록 하나의 단위는 [math]\displaystyle{ B=2^r }[/math]이다. 블록은 [math]\displaystyle{ K=2^{d+1}, K'=2^d }[/math]으로 2의 거듭제곱 개수라 가정한다. 그러면 위 조건에 따라 [math]\displaystyle{ u=2^{2^d}+1 \geq K'B^2=2^{2r+d} }[/math]이어야 하며, 여기서 [math]\displaystyle{ r, d }[/math]는 자연수이므로 [math]\displaystyle{ 2r+d \leq 2^d }[/math]으로 쓸 수 있다. 아울러 위 문단의 [math]\displaystyle{ r }[/math]의 조건을 대입하면 [math]\displaystyle{ 2 \left \lceil \frac{\ell}{2^{d+1}} \right \rceil \leq 2^d-d }[/math]이다.
이에 따라 [math]\displaystyle{ \ell }[/math]을 기준으로 [math]\displaystyle{ d }[/math]를 결정할 수 있다.
[math]\displaystyle{ d }[/math] | [math]\displaystyle{ K }[/math] | [math]\displaystyle{ 2^d-d }[/math] | [math]\displaystyle{ \frac{\ell}{2^{d+1}} }[/math]의 최댓값 | [math]\displaystyle{ \ell }[/math]의 최댓값 |
---|---|---|---|---|
1 | 4 | 1 | 0 | 0 |
2 | 8 | 2 | 1 | 8 |
3 | 16 | 5 | 2 | 32 |
4 | 32 | 12 | 6 | 192 |
5 | 64 | 27 | 13 | 832 |
6 | 128 | 58 | 29 | 3712 |
7 | 256 | 121 | 60 | 15360 |
8 | 512 | 248 | 124 | 63488 |
9 | 1024 | 503 | 251 | 257024 |
10 | 2048 | 1014 | 507 | 1038336 |
수가 커짐에 따라 [math]\displaystyle{ d \approx \log_4 \ell }[/math] 꼴이 된다.
예를 들어 곱하려는 두 수가 81비트, 108비트라 하면 곱한 결과는 189비트라 예상하고, 위 표에서 [math]\displaystyle{ \ell }[/math]의 허용 범위를 보면 [math]\displaystyle{ d \geq 4 }[/math]일 때 알고리즘을 적용할 수 있음을 알 수 있다. [math]\displaystyle{ d=4 }[/math]를 택하면 [math]\displaystyle{ K=32, K'=16, u=2^{16}+1, r=\left \lceil \frac{189}{32} \right \rceil=6, B=2^6=64 }[/math]이다.
고속 푸리에 변환[편집 | 원본 편집]
바로 앞 문단에서 고속 푸리에 변환(FFT)을 위해 [math]\displaystyle{ K }[/math]를 2의 거듭제곱으로 가정하였다. [math]\displaystyle{ d, K, r, u }[/math]의 값을 정한 후에는 FFT를 실행할 차례다.
주어진 [math]\displaystyle{ f(x) }[/math]로부터 [math]\displaystyle{ f(t^n) \mod u }[/math]의 값을 셈하는데, 앞서 언급했듯이 컴퓨터에게는 [math]\displaystyle{ t=2 }[/math]가 가장 편리하다.
- [math]\displaystyle{ f(x)=\sum_{k=0}^{K-1} a_k x^k \Rightarrow f(2^n)=\sum_{k=0}^{K-1} (a_k \triangleleft nk) }[/math]
여기서 [math]\displaystyle{ a_k \triangleleft n = x\cdot 2^{n} \mod u }[/math]이다. 즉 [math]\displaystyle{ a_k }[/math]의 이진법 표기에서 왼쪽으로 [math]\displaystyle{ n }[/math]비트 밀고 [math]\displaystyle{ u }[/math]로 나눈 나머지를 셈하는 것이다.
고속 푸리에 변환은 이렇게 전개한다. 모든 벡터의 성분의 수는 2의 거듭제곱이며 [math]\displaystyle{ w=\bar{v} }[/math]를 도출하는 것이 목표다. 여기서 보조 인자가 하나 필요한데 초깃값은 [math]\displaystyle{ s=1 }[/math]이다.
- 계수들을 나열한 벡터 [math]\displaystyle{ v=(v_0, v_1, \cdots v_{n-1}) }[/math]을 입력 받고 벡터의 길이를 잰다. 만약 성분이 하나 뿐이라면 [math]\displaystyle{ w=v }[/math]를 반환한다.
- 성분이 둘 이상이면 벡터를 홀수 번째와 짝수 번째 성분으로 분리한다.
- [math]\displaystyle{ v^\oplus=(v_0, v_2, \cdots v_{n-2}), v^\ominus=(v_1, v_3, \cdots v_{n-1}) }[/math]
- 각각의 부분 벡터에 대해 보조 인자가 [math]\displaystyle{ 2s }[/math]인 FFT를 시행한다. 즉 부분벡터를 입력값으로 해서 처음으로 올라간다. (재귀함수 호출)
- [math]\displaystyle{ w^\oplus=\bar{v^\oplus}, w^\ominus=\bar{v^\ominus} }[/math]
- 두 변환 결과를 이용하여 하나로 합친다. 여기서 아까 언급했던 보조 인자 [math]\displaystyle{ s }[/math]가 쓰인다.
- [math]\displaystyle{ \begin{cases} w_j=w^\oplus_j + (w^\ominus_j \triangleleft js) \\ w_{j+n/2}=w^\oplus_j - (w^\ominus_j \triangleleft js) \end{cases} (0 \leq j \lt n/2) }[/math]
- 합친 결과인 [math]\displaystyle{ w }[/math]를 반환한다.
이 방법으로 계수 벡터 [math]\displaystyle{ a=(a_0, a_1, \cdots a_{K-1}), b=(b_0, b_1, \cdots b_{K-1}) }[/math]에 대해 푸리에 변환을 거친 [math]\displaystyle{ \bar{a}=(f(1), f(2), \cdots f(2^{K-1})), \bar{b}=(g(1), g(2), \cdots g(2^{K-1})) }[/math]를 셈한다. 그리고 두 벡터를 각 성분마다 곱하면 [math]\displaystyle{ \bar{c} (\bar{c}_k=h(2^k)=f(2^k)g(2^k) \mod u) }[/math]가 나오는데, 이번에는 고속 푸리에 역변환(IFFT)을 시행한다. 방법은 위와 거의 똑같다.
- [math]\displaystyle{ \bar{c}=(h(1), h(2), \cdots h(2^{K-1})) }[/math]에서 첫 번째를 제외한 성분들의 순서를 통째로 뒤집는다.
- [math]\displaystyle{ \bar{c}^\dagger=(h(1), h(2^{K-1}), \cdots h(2)) }[/math]
- [math]\displaystyle{ \bar{c}^\dagger }[/math]에 대해 위 방법(FFT)을 시행한다. 마찬가지로 보조 인자는 1에서 시작한다.
- [math]\displaystyle{ Kc=c'=\bar{\bar{c}^\dagger} }[/math]
- 각 성분을 [math]\displaystyle{ K }[/math]로 나눈다. 이때 합동식 [math]\displaystyle{ Kc_k \equiv c'_k \pmod u }[/math]를 풀어야 하는데, [math]\displaystyle{ K=2^{d+1}, u=2^{2^d}+1 }[/math]이므로 [math]\displaystyle{ c_k \equiv -2^{2^d-(d+1)}c'_k \pmod u }[/math]이다. 즉 [math]\displaystyle{ c_k = \begin{cases} 0\ (c'_k=0) \\ u-c'_k \triangleleft [2^d-(d+1)] \ (\text{o/w}) \end{cases} }[/math]
알고리즘[편집 | 원본 편집]
위 아이디어를 토대로 과정을 총정리하면 아래와 같다.
- 곱하고자 하는 두 수 [math]\displaystyle{ M, N }[/math]의 비트 수를 잰다.
- 비트 수의 합에 따른 블록의 수 [math]\displaystyle{ K }[/math]와 이에 따른 블록 하나의 비트 수 [math]\displaystyle{ r }[/math], 모듈러 산술에 필요한 [math]\displaystyle{ u=2^{K/2}+1 }[/math]을 결정한다.
- 두 수를 [math]\displaystyle{ r }[/math]비트마다 블록을 쪼개고, 가장 뒷자리부터 블록 별 값을 벡터로 적는다. 그 다음 각 벡터의 성분이 총 [math]\displaystyle{ K }[/math]개가 되도록 0을 이어붙인다.
- 각 벡터에 대해 FFT를 시행한다.
- 변환된 벡터의 성분 별로 곱해서 새로운 벡터를 도출한다.
- 새로운 벡터에 IFFT를 적용한다.
- 푸리에 역변환 후의 벡터의 성분들을 이어붙인다. 이때 맨 뒤 성분에서 시작하여 역순으로, 자리를 [math]\displaystyle{ r }[/math]비트씩 옮기면서 더해간다.
적용 예[편집 | 원본 편집]
두 수 [math]\displaystyle{ M=1734492765338661710171833, N=205295973898620029528272537868263 }[/math]의 곱을 위 문단에 소개된 방법으로 구해보자. 두 수는 이진법으로 각각 81비트, 108비트이며 곱셈 결과는 189비트로 예상한다.
블록은 총 [math]\displaystyle{ K=32 }[/math]개, 블록 하나당 [math]\displaystyle{ r=6 }[/math]비트, 블록 하나의 단위는 [math]\displaystyle{ B=2^6=64 }[/math], 모듈러스는 [math]\displaystyle{ u=2^{16}+1=65537 }[/math]로 잡는다. ('블록의 개수와 길이' 문단 참고)
두 수를 6비트마다 쪼개서 벡터로 표현하고, 성분이 32개가 되도록 0을 덧붙이면 아래와 같다. 이때 가장 나중 블록이 벡터의 첫 성분이고 자리 역순으로 써진 것에 유의한다.[5]
a=(57, 58, 56, 2, 28, 51, 47, 12, 13, 42, 48, 18, 47, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) b=(39, 31, 53, 56, 11, 2, 15, 8, 62, 63, 40, 44, 49, 5, 49, 12, 31, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
그 다음 각 벡터에 대해 FFT를 시행한다. (모든 연산은 법 65537에 대한 모듈러 산술로 진행한다.)
FFT(a)=(484, 23672, 37350, 64084, 48059, 4971, 19047, 11919, 31738, 62963, 16115, 15526, 34681, 57928, 23529, 28579, 108, 15027, 10605, 35996, 46652, 25123, 57809, 49642, 33787, 28348, 47724, 5385, 1662, 5659, 50321, 24849) FFT(b)=(610, 46882, 45564, 16308, 9523, 29188, 42423, 31306, 5411, 56950, 6213, 34544, 55361, 52264, 34647, 19840, 88, 44887, 50106, 19606, 5469, 10232, 16920, 45334, 60196, 62951, 55848, 49446, 61009, 20297, 10491, 49926)
변환 결과를 각 성분 별로 곱한다.
ab=(33092, 52683, 16121, 28870, 20986, 60167, 25208, 34073, 27378, 16969, 47496, 40873, 2889, 1740, 60057, 46773, 9504, 10145, 134, 35160, 4247, 22422, 54092, 60922, 32531, 27975, 31236, 55416, 11219, 39899, 17076, 61301)
그리고 이 벡터에다 IFFT를 시행한다.
c=IFFT(ab)=(2223, 4029, 7003, 8080, 7997, 6851, 6597, 7656, 11376, 13591, 14996, 14839, 18014, 16935, 17719, 14806, 14164, 14261, 15539, 12803, 12416, 12079, 9827, 7856, 6352, 3760, 5712, 3287, 2237, 2035, 200, 0)
이제 맨 끝 성분부터 시작해서 '왼쪽으로 블록 하나만큼 비트를 밀고 이전 성분을 더하기'를 반복하면 원하는 결과가 나온다. 이 예시에서는 블록 하나가 6비트이고 [math]\displaystyle{ B=64 }[/math]임을 확인한다.
- [math]\displaystyle{ x_1=c_{K-1}, x_k=x_{k-1}\cdot B+c_{K-k}, 1 \lt k \leq K }[/math]
- [math]\displaystyle{ MN=x_K }[/math]
Result: 356084381480311170312773728803907543171632357309247236079
이것으로 알고리즘은 끝난다. 이 결과는 [math]\displaystyle{ MN }[/math]을 전통적인 곱셈법으로 계산한 것과 일치한다.
실제로 컴퓨터는 저 정도 크기의 수는 바로 곱하는 편이 빠르지만, 만약 곱하고자 하는 두 수가 수만 비트 이상으로 거대하다면 쇤하게-슈트라센 곱셈법의 효력은 막강해진다.
참고 자료[편집 | 원본 편집]
각주
- ↑ 항의 수는 엄밀히는 [math]\displaystyle{ m_1=\lceil \log_{B}(M+1) \rceil }[/math]이다. 하지만 여기서는 [math]\displaystyle{ \log_B M }[/math]이 정수로 정확히 떨어지는 경우는 생각하지 않는다. [math]\displaystyle{ m_2, N }[/math]의 경우도 마찬가지.
- ↑ DFT: 이산 푸리에 번환(discrete Fourier transform), IDFT: 이산 푸리에 역변환
- ↑ 앞서 [math]\displaystyle{ f(x) }[/math]의 항이 [math]\displaystyle{ m_1 }[/math]개라 가정했지만 여기서는 [math]\displaystyle{ K }[/math]개까지 연장한다. 비어 있는 고차항들은 계수를 0으로 취급한다.
- ↑ [math]\displaystyle{ \ell=\lceil \log_2 MN \rceil }[/math]이 아닌 이유는 [math]\displaystyle{ MN }[/math]은 알고 있는 값이 아닌 알고 싶은 값이기 때문이다. 즉 알고리즘 실행 전에는 두 수의 비트를 각각 잰 다음 더하는 것이 옳다.
- ↑ 이를테면 이진법 표현인 "110111101001011"을 "110 111101 001011"과 같이 쪼갠다면 벡터는 (1011, 111101, 110)과 같이 뒤쪽 블록부터 적는다.
수론 알고리즘 |
|
---|---|
정수의 곱셈 | |
소수판정법 | |
소인수분해 | |
기타 알고리즘 |