很多时候,对 Cache 的友好性会带来巨大的常数提升。
同学的 Fast Fourier Transform 板子就因 Cache Miss 常数爆炸。
优化好的 FFT 并不比 NTT 慢多少,在做多项式乘法时还有着三次变两次的优势。
还能利用复数性质,将两次 DFT 合并为一次,在 MTT 中有相关应用。
很多时候,对 Cache 的友好性会带来巨大的常数提升。
同学的 Fast Fourier Transform 板子就因 Cache Miss 常数爆炸。
优化好的 FFT 并不比 NTT 慢多少,在做多项式乘法时还有着三次变两次的优势。
还能利用复数性质,将两次 DFT 合并为一次,在 MTT 中有相关应用。