(화이트데이 기념) 정수 FFT 돌리기 좋은 소수 모음

정수 FFT 관련해서는 여기에 아주 잘 설명해 놓은 글이 있어서 소개합니다.

https://algoshitpo.github.io/2020/05/20/fft-ntt/

정확도 높은 FFT와 NTT

 

높은 정확도의 convolution이 필요할 때 보통 다항식을 2^15진법 위에서 쪼개거나 NTT를 돌리거나 하는데, 저 같은 경우는 IEEE 754를 제대로 숙지하지 못한 탓인지(?) 첫 번째 방법의 구현이 잘 되지 않아서 그냥 NTT를 하기로 했습니다. NTT를 할 때에는 다른 사람들이 잘 사용하지 않는 힙한 소수를 사용하는 것이 중요합니다. 소수 몇 개를 소개합니다.

p = (1 << b) * a + 1	a	b	holdable n (근사치)	w
377 487 361	45	23	8.3M	7
595 591 169	71	23	8.3M	3
645 922 817	77	23	8.3M	3
880 803 841	105	23	8.3M	26
897 581 057	107	23	8.3M	3
998 244 353	119	23	8.3M	3
1 300 234 241	155	23	8.3M	3
1 484 783 617	177	23	8.3M	5
2 088 763 393	249	23	8.3M	5
754 974 721	45	24	16.7M	11
1 224 736 769	73	24	16.7M	3
2 130 706 433	127	24	16.7M	3
167 772 161	5	25	33.5M	3
1 107 296 257	33	25	33.5M	10
1 711 276 033	51	25	33.5M	29
2 113 929 217	63	25	33.5M	5
469 762 049	7	26	67.1M	3
1 811 939 329	27	26	67.1M	13
2 013 265 921	15	27	134.2M	31

이 표의 좋은 점은, b >= 23이면서 p < 2 147 483 647인 모든 소수를 포함한다는 점입니다.

holdable n 값은, convolution의 결과물 벡터의 길이가 n을 넘어가면 제대로 작동함이 보장되지 않는다는 뜻입니다. 정확한 값은 n = 2^b인데, FFT의 원리를 알면 당연한 결과일 것입니다.