고속 푸리에 변환2 (화이트데이 기념) 정수 FFT 돌리기 좋은 소수 모음 정수 FFT 관련해서는 여기에 아주 잘 설명해 놓은 글이 있어서 소개합니다. https://algoshitpo.github.io/2020/05/20/fft-ntt/ 정확도 높은 FFT와 NTT FFT에서는 실수 자료형을 사용하기 때문에 실수 오차가 발생할 수 있고, 이는 즐거운 PS생활에 큰 지장을 줄 수 있습니다. 특히 FFT 문제에서 수가 너무 크기 때문에 M으로 나눈 나머지를 출력한다. algoshitpo.github.io 높은 정확도의 convolution이 필요할 때 보통 다항식을 2^15진법 위에서 쪼개거나 NTT를 돌리거나 하는데, 저 같은 경우는 IEEE 754를 제대로 숙지하지 못한 탓인지(?) 첫 번째 방법의 구현이 잘 되지 않아서 그냥 NTT를 하기로 했습니다. NTT를 할 때에는 다.. 2023. 3. 14. 고속 푸리에 변환, 이론부터 구현까지 1. 구현하기 전에 필요한 지식 고속 푸리에 변환(Fast Fourier Transform; FFT)은 어떤 벡터의 이산 푸리에 변환을 \( O(n \log n) \) 안에 구할 수 있게 해주는 쉬우면서도 강력한 알고리즘이다. 푸리에 변환이라고 하니 굉장히 생소해 보이고, 신호 처리나 미분방정식 푸는 데 외에는 쓸데가 없어 보이지만, 사실 이걸 갖고 상당히 많은 일을 할 수가 있다. 예를 들자면 차수가 n인 두 다항식을 \( O(n \log n) \)에 곱한다. (가장 직관적인 방법으로 계산하면 \( O(n^2) \)이 나오게 된다.) 크기가 \( 10^n \) 정도인 두 자연수를 \( O(n \log n) \)에 곱한다. (마찬가지로 직관적으로 곱하면 \( O(n^2) \)이다.) 자연수 집합의 두 부.. 2023. 1. 2. 이전 1 다음
