정수 FFT와 관련하여 여기에 아주 잘 설명하는 기사가 있습니다.
https://algoshitpo.github.io/2020/05/20/fft-ntt/
고정밀 FFT 및 NTT
FFT는 실제 데이터 유형을 사용하기 때문에 실제 오류가 발생할 수 있으며 이는 편안한 PS 생활에 큰 영향을 미칠 수 있습니다.
특히, FFT 문제에서 숫자가 너무 크기 때문에 M으로 나눈 나머지가 출력된다.
algoshitpo.github.io
고정밀 컨벌루션이 필요한 경우 다항식은 보통 2^15를 밑으로 나누거나 NTT를 실행합니다.
NTT를 플레이할 때 다른 사람들이 자주 사용하지 않는 힙 프라임을 사용하는 것이 중요합니다.
몇 가지 소수 소개.
| p = (1 << b) * a + 1 | ㅏ | 비 | 내구성 n (대략) | 승 |
| 1 004 535 809 | 479 | 21 | 200만 | 삼 |
| 1 012 924 417 | 483 | 21 | 200만 | 5 |
| 1 092 616 193 | 521 | 21 | 200만 | 삼 |
| 880 803 841 | 105 | 23 | 830만 | 삼 |
| 998 244 353 | 119 | 23 | 830만 | 삼 |
| 1 107 296 257 | 33 | 25 | 3350만 | (찾고있는) |
| 1 711 276 033 | 51 | 25 | 3350만 | (찾고있는) |
| 2 113 929 217 | 63 | 25 | 3350만 | 5 |
| 469 762 049 | 7 | 26 | 6,710만 | 삼 |
| 2 013 265 921 | 15 | 27 | 1억 3,420만 | 31 |
n의 지속 가능한 값은 컨볼루션 결과 벡터의 길이가 n을 초과하는 경우 작동을 보장하지 않는다는 것을 의미합니다.
FFT의 원리를 이해하면 당연하지만 2^b의 값을 찾아보면 알 수 있다.
(에 추가)