Fast Fourier Transform

https://speakerdeck.com/wookayin/fast-fourier-transform-algorithm

http://cubelover.tistory.com/12

내가 개념을 설명하기에는 위의 링크로도 충분한 것 같아서 따로 설명을 하지는 않겠다. 특히 맨 처음 인용한 ppt 슬라이드가 엄청나게 이해하기가 쉬우니 보면서 따라가는 것이 좋을 것이다. 다만 생각의 흐름 정도를 정리하자면

 * 다항식을 표현하는 데 있어서는 sigma(ai * x^i) 형태의 coefficient representation과, {(x1, f(x1)), (x2, f(x2)), .. (xn, f(xn))} 형태의 point-value representation이 있다. lagrange interpolation theorem를 통해서 이것이 가능함을 이해하고 그것이 다항식 곱셈을 얼마나 간단하게 만드는지 생각하자 (link 1)

* discrete fourier transform이 무엇이고, 그것을 할 수 있다면 왜 coefficient representation을 point-value representation으로 바꿀 수 있는지 생각하자 (link 1 / 2)

* discrete fourier transform의 역변환 역시 discrete fourier transform의 형태로 가능함을 알고, 그것이 point-value representation을 coefficient representation으로 바꿀 수 있음을 생각하자 (link 2)

* 이제, discrete fourier transform을 빠르게 하는 알고리즘인 fast fourier transform을 배우자 (link 1)

나의 경우 https://github.com/koosaga/olympiad/blob/master/Library/ 내부 teamnote.tex 파일에 구현했다. (링크가 자주 바뀔 수 있는데 현재는 이렇다.) 비재귀 구현으로, 시중에 있는 구현중에는 상당히 빠른 편에 속한다. 내가 본 것중 가장 빠른 건 http://blog.myungwoo.kr/54 였는데 재보니 10^6 크기의 다항식 곱셈 시 대충 2배 정도 빠르다. 비트를 뒤집는게 마의 트릭인거 같은데, 코드가 직관적이기를 원했기에 나는 재귀만 풀고 직접적으로 구현했다.

+ Number Theoretic Transform (NTT) 라는 것 역시 존재하며 구현은 위 FFT와 동일한 위치에 있다. 큐브러버 블로그에도 설명이 나와 있다. 한정된 소수 p에 대해서, FFT mod p를 전부 정수로 할 수 있는 방법인데, 아이디어는 w ^ n == 1 (mod p) 이며, w^0 ... w^n-1 이 모두 서로 다른 w와 p의 쌍을 찾는 것이다. n이 적당히 큰 2 ^ k의 배수면 FFT에서 사용했던 복소수와 w의 역할이 완벽히 동일하다. 고로 똑같이 코딩하면 정수만으로 구현 가능하다.

w ^ (p-1) == 1 (mod p) 임이 잘 알려져 있다. p - 1이 적당히 큰 2^k의 배수여야 하니 보통 p = a * 2^b + 1의 형태로 잡는다. 이제 p의 primitive root w를 찾는다. primitive root는, w ^ x == 1 (mod p)를 만족하는 최소의 x > 0이 x = phi(p) = p-1 인 수를 뜻한다. w가 primitive root라면, w^0 .. w^n-1이 서로 다 다르고, w^(p-1) == 1 (mod p) 이니 복소수 대신 w ^ ((p-1) / N)을 사용해서 FFT를 돌릴 수 있다. 

NTT 자체는 실수 구현에 비해서 큰 메리트가 없다. mod p 조건 때문에 convolution 결과가 p 미만의 수여야 하며 이는 실수를 사용해서도 충분히 풀 수 있기 때문이다. 속도도 그렇게 빠르지 않다. 그럼에도 NTT로 실수 구현을 대체할 생각이 있다면, p = 119 * 2 ^ 23 + 1 = 998244353, w = 3을 쓰면 된다. 

NTT가 유용한 경우는, 보통 문제에서 이상한 modulo로 나눈 나머지를 출력하라고 할 때이다. FFT로 10^9 + 7 modulo 값을 출력하기에는 너무 번거롭고 어렵기 때문이다. (이 방법은 나도 잘 모르고 배우면 이후 내용 추가하겠다.) 모듈러가 이상하면, p = a * 2^b + 1 꼴의 모듈러인지를 한번 확인해보고, primitive root가 존재하는지 체크해보자. 보통 출제자가 primitive root가 대충 3이나 5 정도인 소수를 주니까 그냥 대충 컴퓨터에서 돌려보면 primitive root인지를 판별 가능하다. 위에 적은 998244353 역시 이러한 modulo의 굉장히 유명한 케이스 중 하나다.