[빠른곱셈-2][선행지식] DFT in bit operation

Ring

집합이 다음 조건을 만족하면 ring이라고 한다

 

1. 덧셈에 대해 닫혀있고 Abelian group이다

 

연산이 아래 규칙을 만족하면 Abelian group이다

- 결합법칙 성립

$(a+b)+c = a+(b+c)$

- 항등원(Identity element) 존재

$a+e = a$ 를 만족하는 e가 존재

- 역원(Identity element) 존재  

$a+b = e$ 를 만족하는 b가 존재 (e는 항등원)

- 교환법칙 성립

$a+b = b+a$

 

2. 곱셈에 닫혀있고 곱셈이 결합법칙 성립

 

3. 곱셈이 덧셈을 분배

$a\cdot (b+c) = a\cdot b + a\cdot c$

 

예를 들어, 정수 집합은 Ring이다

 

Rm

n,w를 2의 거듭제곱이라고 하고 Rm을 정수의 modulo-m의 Ring이라고 정의하면 ($w^{n/2}+1 = m$),

1. n의 곱셈에 대한 역원이 존재한다

2. w는 n-th primitive root of 1이다

 

증명

1. n의 곱셈에 대한 역원이 존재한다

$w^{n/2} = \alpha \cdot n$ 을 만족하는 $\alpha$ 존재 (그리고 $\alpha$는 정수이다)

${w^{n/2} = \alpha \cdot n \\
\rightarrow(w^{n/2}+1)-\alpha \cdot n = 1 \\
\rightarrow (w^{n/2}+1)-\alpha \cdot n = 1 (mod\,m)\\
\rightarrow -\alpha \cdot n=1 (mod\,m) \\
\rightarrow n^{-1}=-\alpha }$

 

2. w는 n-th primitive root of 1이다

claim1)

$\sum_{i=0}^{n-1}w^{i}=\prod_{i=0}^{k-1}(w^{2^{i}}+1)$, ($2^k=n$)

오른쪽 식을 풀어보면 식이 성립함을 쉽게 알 수 있다 (w가 primitive root of unity 일 때 뿐만 아니라 일반적으로 성립한다)

 

claim2)

$1+x^s$에서 s가 홀수라면 이는 $1+x$로 나누어 떨어진다

왜냐하면, $1+x^s=h(1+x)+r$ (note that r은 상수)

양변에 x=-1을 대입해주면 0=r

 

claim3)

[0,n-1] 범위의 모든 p에 대해 $w^p!=1 (mod\,m)$가 성립해야 n-th primitive root of 1이다

$w^p=1 (mod\,m)$라고 하고 모순됨을 보이자

$\sum_{i=0}^{n-1}w^{ip}=n(mod\,m)$ <---(1)

그리고,
$\sum_{i=0}^{n-1}w^{ip}=\prod_{i=0}^{k-1}((w^p)^{2^{i}}+1)$

p에서 홀수(s)만 분리해서 $p=s\cdot 2^t$로 표현할 수 있다

그러면, $(w^p)^{2^i}+1$에서 $(w^s)^{2^{k-1}}+1$인 항이 존재한다

따라서, $\sum_{i=0}^{n-1}w^{ip}$은 $(w^s)^{2^{k-1}}+1$로 나누어 떨어진다

또한, $(w^s)^{2^{k-1}}+1$는 $w^{2^{k-1}}+1$로 나누어 떨어진다 (claim2에 의해)

그러므로, $\sum_{i=0}^{n-1}w^{ip}=0(mod\,m)$이고 이는 (1)에 모순된다

-> w는 n-th primitive root of 1

 

DFT in bit operation

비트의 길이가 n이라고 하고,

각 비트를 L의 길이를 가진 B개의 비트로 나누자(n=BL, B : block, L : length)

또한 $n=2^k$라고 가정

$m=2^{l/2}+1$ (w는 $2^l$-th primitive root of 1)

이진수 a를 다음과 같이 $B$개로 자를 수 있다 (각 비트의 사이즈는 $l$)

$a=...|...x_{l}|...x_2x_1x_0$

각 쪼개진 비트를 작은 비트부터 $a_i$라고 하자

그리고 modulo-m을 해주면

${a=\sum_{i=0}^{b-1}a_i2^{il} \\
\Rightarrow a=\sum_{i=0}^{b-1}a_i(-1)^i(mod\,m)=a_{b-1}*(-1)^{b-1}+...+a_2-a_1+a_0(mod\,m)}$

 

naive 하게 계산했을 때의 시간복잡도는,

처음부터 순서대로 덧셈 뺄샘을 수행할 때 최대 B*L/2의 크기가 되고, B번 반복 연산을 하기 때문에,

$O(B^2L)=O(NB)$

 

FFT를 쓰자

아래는 [빠른곱셈-1] FFT 포스팅 때 썼던 코드

def fft(a,w):    
    if len(a)==1:
        return a
    a_even = a[::2]
    a_odd = a[1::2]
    A_even = fft(a_even, w*w)
    A_odd = fft(a_odd, w*w)
    A = []
    for i in range(len(A_even)):
        A.append(A_even[i]+(w**i)*A_odd[i])
        # w**i를 미리 계산하면 더 시간복잡도가 줄어듬
    for i in range(len(A_even)):
        A.append(A_even[i]-(w**i)*A_odd[i])
    return A

이전 포스팅에서 arithmetic operation만 따진다면 $O(nlogn)$이었다.

B blocks로 비트를 나눴기 때문에,

arithmetic operation는 O(BlogB)이다

또한, (w**i)*A_odd[i]를 계산할 때, 각 숫자의 크기가 $2^L$이다.

따라서, O(logL)이 추가로 수행필요하다 (이 부분 정확히 이해 못했습니다)

 

따라서,

T(n) = O(BlogB)O(L) = O(BLlogB) = O(NlogB)

 

 

 

출처

https://www.youtube.com/watch?v=t1jiDLc0sKQ&list=PLbMVogVj5nJTA6ZeVkqHEiUup_3ccdg_C&index=25 

https://psun.me/post/fft2/